- Gráfelméleti alapok
- Kuratowski gráfok, síkbarajzolhatóság
- Gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózati folyamok
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Oszthatóság
- Euklideszi algoritmus & Diofantoszi egyenletek
- Kongruenciák, RSA kódolás
- Boole-algebra alapjai
Kuratowski gráfok, síkbarajzolhatóság
Gráf (precizen)
A $G$ gráf csúcsainak halmazát $V(G)$-vel jelöljük. Itt a $V$ az angol vertex = csúcs szóra utal.
A $G$ gráf éleinek halmazát $E(G)$-vel jelöljük. Itt $E$ az angol edge = él.
A $G$ gráf egy $( V(G), E(G) )$ rendezett pár, ahol $V(G)$ egy nem üres halmaz, $E(G)$ pedig a $V(G)$-ből képezhető párok egy halmaza.
Út
Ha a gráf egy csúcsából elindulunk, és teszünk egy sétát a gráfon, akkor egy élsorozatot kapunk.
Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször, útnak nevezzük.
Körséta
Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük.
Csúcsok fokszámainak összege és az élek száma közti összefüggés
Minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese:
\( \sum d(V_n) = 2e \)
Fa
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
Egy $n$ csúcsú fának mindig $n-1$ darab éle van.
Síkbarajzolható gráf
Egy gráf síkbarajzolható, ha lerajzolható úgy, hogy élei csak a csúcspontokban találkozzanak.
Kuratowski-tétel
A Kuratowski-tétel szerint egy gráf pontosan akkor nem síkbarajzolható, ha tartalmaz $K_{3,3}$-mal vagy $K_5$-tel topológiailag izomorf részgráfot.
Euler-féle poliéder tétel
Azt mondja az Euler-féle poliéder-tétel, hogy ha egy konvex poliéder csúcsainak száma $V$, lapjainak száma $F$ és éleinek száma $E$, akkor
\( V + F = E + 2 \)
Síkbarajzolhatóság szükséges feltétele
Ha egy egyszerű gráfban minden kör legalább $k$ hosszú, akkor a síkbarajzolhatóság szükséges feltétele:
\( (k-2) \cdot E \leq k\cdot V - 2k \)
Egyszerű gráfok síkbarajzolhatóságának szükséges feltétele
Ha egy egyszerű gráf síkbarajzolható, akkor meg kell felelnie ennek a feltételnek:
\( E \leq 3V -6 \)
Itt az ideje, hogy egy kicsit precízebben is elkezdjünk foglalkozni a gráfokkal. A G gráf csúcsainak halmazát V(G)-vel jelöljük. Itt a V az angol vertex=csúcs szóra utal. A G gráf éleinek halmazát E(G)-vel jelölünk. Itt E az angol edge=él. Teljesen tudományosan megfogalmazva a G gráf egy (V(G), E(G)) rendezett pár, ahol V(G) egy nem üres halmaz, E(G) pedig a V(G)-ből képezhető párok egy halmaza. Ha a gráf egyik csúcsából elindulunk, és teszünk egy sétát a gráfon… akkor egy élsorozatot kapunk. Azokat az élsorozatokat, amelyek a gráf semelyik pontján nem haladnak át többször útnak nevezzük. Ez itt nem egy út, mert V10-en kétszer is áthaladunk. Ez viszont igen. Ha egy élsorozat ugyanabból a csúcsból indul, mint ahova érkezik, akkor körsétának nevezzük. Ez itt például egy körséta. Egy gráfban körnek nevezünk egy olyan utat, amely csupa különböző csúcsokon és éleken haladva visszavezet a kiinduló csúcsba. Íme, itt egy kör. Egy gráf összefüggő, ha bármely csúcsából bármelyikbe vezet út. Ha ez nincs így, akkor a gráf több különböző komponensből áll. Idáig ez nem túl bonyolult. Ennyire még Piroska néni, a jósnő is járatos a gráfokban. De az izgalmak csak most jönnek. Egy csúcs fokszáma azt mondja meg, hogy hány él vezet az adott csúcsba. Ennek a csúcsnak itt, a fokszáma például három. Ennek pedig kettő. És ennek itt egy. Egy tetszőleges V csúcs fokszámát d(V)-vel jelöljük. Ha egy gráfban megszámoljuk a csúcsok fokszámait, akkor minden élt pontosan kétszer számolunk meg. Egyszer az egyik csúcsnál… aztán a másiknál. Vagyis minden gráfban a csúcsok fokszámainak összege az élek számának a kétszerese. Egy gráfot egyszerű gráfnak nevezünk, ha nincsen benne hurokél… és nincsen benne párhuzamos él. HUROKÉL PÁRHUZAMOS ÉL A csillagképek mindig egyszerű gráfok. Mert nincs olyan őrült csillagász, aki előállna azzal, hogy ugyanazt a két csillagot kétszer is összekösse. Vagy éppen egyetlen csillagot sajátmagával. A gráfelméletben viszont nem ritkák az olyan gráfok, ahol van hurokél, vagy párhuzamos él. Annyira nem, hogy a világ legelső gráfjában is voltak párhuzamos élek. Ezt a híres gráfot Leonhard Euler alkotta meg a königsbergi hidak problémájának megfejtésekor. A Königsberg nevű városka lakóit az a kérdés nyugtalanította, hogy körbe tudnak-e sétálni a város hídjain úgy, hogy minden hídon pontosan egyszer haladnak át és a séta végén visszaérnek a kiindulópontra. A kérdés úgy fogalmazható át, hogy létezik-e ebben a gráfban olyan körséta, amely minden élen pontosan egyszer halad át. Az ilyen körsétákat Euler-körnek (helyesen Euler-körsétának) nevezik. Euler bebizonyította, hogy egy gráfban pontosan akkor létezik Euler-körséta, ha minden csúcs fokszáma páros. Így aztán a königsbergieket el kellett keserítenie. A gráfokkal való ismerkedésünket néhány speciális gráffal fogjuk folytatni.
Ha egy gráfban nincs kör, de maga a gráf összefüggő, akkor fának nevezzük.
A fa egy olyan gráf, ahol a lehető legkevesebb él felhasználásával kötjük össze a csúcsokat.
És bármely csúcsból bármely másik csúcsba pontosan egy út vezet.
A másik véglet, ha bármely csúcsból bármelyik másik csúcsba közvetlen él is vezet.
Ezeket a gráfokat teljes gráfnak nevezzük.
Ez egy négypontú teljes gráf:
Ez pedig egy ötpontú teljes gráf:
FA
TELJES GRÁF
Egy n csúcsból álló fának mindig n-1 darab éle van.
Az n pontú teljes gráf éleinek száma:
Ezek az információk később még jól jöhetnek…
Például olyan esetekben, amikor egyik ismerősünk előáll azzal, hogy tegnap látott egy olyan 8 pontú összefüggő gráfot, aminek 6 darab éle van.
Biztosak lehetünk benne, hogy az illető hazudik.
Azért hazudik, mert a 8 pontból álló összefüggő gráfok közül a legkevesebb éle a fának van.
Egy 8 pontból álló fának pedig 8-1=7 éle van.
Íme, itt van néhány gráf.
Lássuk, melyik milyen...
Körmentes
Összefüggő
Fa
Mivel minden fa összefüggő és körmentes, ezért a helyzet
valójában valahogy így néz ki:
Az összefüggő gráfok közül a legösszefüggőbbek a teljes gráfok.
Íme, itt a teljes kollekció:
A nem összefüggő körmentes gráfok neve erdő.
Ez itt például egy erdő:
Végül itt jön még egy vicces dolog.
Nézzük meg ezt a gráfot.
Ezt a gráfot páros gráfnak nevezzük.
Miért hívjuk így?
Ezért.
A gráf csúcsai két csoportra oszthatók.
Az egyik csoportban is olyan csúcsok vannak, melyek között nem vezet él…
és a másikban is.
A legegyszerűbb páros gráf ez:
Aztán itt jön egy bonyolultabb:
De azért még ezt is túl lehet élni…
Ez még érdekesebb:
Így persze már nehezebb róla megállapítani, hogy ez egy páros gráf…
Csomagoljuk szépen vissza.
Ha minden csúcs az egyik oldalon össze van kötve minden csúccsal a másik oldalon…
Akkor ez egy K2,2 teljes páros gráf.
A dolog még tovább fokozható:
Őrület!
Most pedig jó lenne tudni, hogy ezek a gráfok tulajdonképpen mire jók a valóságban.
Mégis mi értelme van gráfokkal foglalkozni?
Lássunk erre néhány példát.
Ez a vasúti hálózat például egy gráf.
Megmutatja, hogy mely állomások között vezetnek vasútvonalak.
Ha ellátjuk az éleket súlyokkal…
Akkor az is kiderül, hogy milyen hosszúak az állomások közötti szakaszok.
Vagy hány percig tart a két állomás közötti út.
Vagy éppen mennyi pénzbe kerül a vasútvonal rekosntrukciója.
Ha például a rekonstrukció elvégzése során kezdetben elegendő az, hogy minden állomásról bármelyik másikra el lehessen jutni felújított vasútvonalon…
akkor a gráfnak egy feszítőfáját kapjuk.
Feszítőfából általában több is van.
És egészen biztosan van köztük egy olyan, ahol a költségek minimálisak…
Réges-régen, egy messzi-messzi galaxisban létezett egy bolygó, amin különös lények éltek. Egy gátrendszert építettek a bolygó felszínére, a gátak végein tornyokkal. Ezekben a tornyokban laktak a fura lények, minden toronyban egy. A gátak medencékre osztották a bolygó felszínét. Mindegyik medence teljesen száraz volt, kivéve egyet, amiben viszont az egész bolygó felszínére elegendő víz volt. A fura lények egyszer elhatározták, hogy elárasztják bolygójukat vízzel. A terv az volt, hogy felrobbantják a medencéket elválasztó gátakat. És így medencéről medencére haladva szétterítik a vizet. A lények szerettek átjárni egymáshoz vendégségbe a tornyokat összekötő utakon. Az utak a gátak tetején vezettek. Így aztán a robbantások során vigyázniuk kellett, nehogy olyan gátat is felrobbantsanak, ami az egyik lény lakótornyát végleg elszigeteli. Arra jöttek rá, hogy ha mindig csak olyan gátat robbantanak föl, aminek az egyik oldalán víz van a másik oldalán szárazföld, akkor minden lakótorony megközelíthető marad. Legfeljebb nagyobb kört kell megtenni. A lények azt is kiszámolták, hogy ha a bolygón F darab medence van, akkor F-1 darab gátat kell felrobbantaniuk ahhoz, hogy mindent elárasszanak vízzel. Medencék száma: F Lakótornyok száma: V Gátak száma: E Felrobbantott gátak száma: F-1 Megmaradt gátak száma: V-1 V+F=E+2 Most nézzük, hogy hány darab gát marad meg. Amikor végeznek a robbantásokkal, a megmaradt gátak egy körmentes gráfot alkotnak. Ha ugyanis lenne benne kör, akkor lenne olyan rész, ahova még nem folyt volna be a víz. Ez a körmentes gráf egyben összefüggő is, mert a robbantásokat mindig úgy végzik, hogy ne szigeteljék el egyik lény lakótornyát sem. Vagyis a megmaradt gátak hálózata egy összefüggő körmentes gráf, tehát egy fa. Egy n csúcsú fának n-1 darab éle van. Ha a lakótornyok száma V, akkor a fel nem robbantott gátak száma V-1. A bolygón lévő E darab gát közül F-1 darabot felrobbantottak, V-1 darabot pedig nem, tehát: Ezt a képletet Euler-féle poliéder-tételnek hívjuk. Azt mondja az Euler-féle poliéder-tétel, hogy ha egy konvex poliéder csúcsainak száma V, lapjainak száma F és éleinek száma E… akkor csúcsok száma lapok száma élek száma Ez a tétel érvényes minden gömbre rajzolt gráfra is. Itt V a gráf csúcsainak a száma, E az élek száma, F pedig azoknak a tartományoknak a száma, amelyre a gráf felszabdalja a gömb felszínét. A gömbre rajzolt gráfot síkra tudjuk vetíteni egy ügyes kis trükk segítségével. Ezt sztereografikus vetítésnek nevezzük. A dolog oda-vissza működik, vagyis a gömb pontjait síkra tudjuk vetíteni, a sík pontjait pedig gömbre. Ez azt jelenti, hogy az Euler-tétel nem csak a gömbön, hanem a síkon is igaz. Azzal az apró kis módosítással, hogy a síkon a sok korlátos tartomány mellett létezik egy olyan tartomány is, amelyik nem korlátos. Mindez arra jó, hogy megpróbálhatunk találni néhány szabályt, hogy egy gráf mikor síkbarajzolható. Kezdjük az egyszerű gráfokkal. Ha egy gráf egyszerű gráf, legkevesebb 3 élre van szüksége ahhoz, hogy egy tartományt határoljon. Az is lehet, hogy többre, de 3 él mindenképpen kell. Ez azt jelenti, hogy Na persze egy él két tartományhoz is felhasználható. A helyzet tehát egy kicsit jobb. Ha egy egyszerű gráf síkbarajzolható, akkor meg kell felelnie ennek a feltételnek. Sajnos ez csak egy szükséges feltétel, tehát abból, hogy ez teljesül, még nem következik, hogy a gráf síkbarajzolható. Síkbarajzolható gráfok szükséges feltétele: Próbáljuk ki. Itt van K5. K5 nem teljesíti a feltételt, ezért nem síkbarajzolható. Most nézzük mi a helyzet K3,3-mal. Tudjuk, hogy ez sem síkbarajzolható, de lássuk, mit ad rá a kritérium. Hát, a kritérium K3,3-at átengedi… Ettől persze K3,3 továbbra sem síkbarajzolható. Ebből is látszik, hogy ez a kritérium csak szükséges feltétele a síkbarajzolhatóságnak, de nem elégséges. Ha még rémlik valami, a kritériumot úgy gyártottuk, hogy 3 hosszú körökkel számol. K3,3-ban, viszont minden kör 4 hosszú. Ez az oka annak, hogy nem működik itt. Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a tartományok száma így becsülhető felülről: És mivel egy él két tartományhoz is tartozik… Ha egy egyszerű gráfban minden kör legalább k hosszú, akkor a síkbarajzolhatóság szükséges feltétele: Gyorsan próbáljuk is ki ezt az új képletet. Lássuk, mi a helyzet K3,3-mal. Azért csak kijött, hogy K3,3 sem síkbarajzolható.
Egyszerű gráfok síkbarajzolhatóságnak szükséges feltételei:
ha minden kör hossza legalább k:
Van itt ez a gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Nézzük, hátha van benne K5.
K5-ben minden csúcs negyedfokú. Vagyis F nem illik a képbe.
Az eredeti gráf tartalmaz egy K5-tel topologikusan izomorf részgráfot.
Így aztán nem síkbarajzolható.
Van itt aztán ez a másik gráf. Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
Úgy tűnik hiába fáradoztunk…
Maradt bent egymást keresztező él.
És bármelyiket rakjuk is ki, akkor kint fog gondot okozni.
Így aztán jó lenne találnunk a gráfban K5-öt vagy K3,3-at.
K5-re azért ne nagyon számítsunk, mert nem sok negyedfokú csúcs van.
És egy dolgot nagyon jegyezzünk meg.
K3,3 valójában egy hatszög három átlóval.
Hát persze, hogy akkor ez a részgráf kell…
Ez topologikusan izomorf K3,3-mal, így aztán az eredeti gráf nem síkbarajzolható.
Most lássuk, mi a helyzet ezzel. Legalább hány élt kell törölnünk ebből a gráfból, hogy a megmaradt gráf síkbarajzolható legyen?
Ez egy páros gráf, így minden kör hossza legalább 4.
Lássuk, milyen kritérium lenne jó ide.
A jelek szerint két élt egészen biztosan törölnünk kell.
És valószínűleg nem ezeket az ártatlan kis éleket…
Hanem ezeket a brutális éleket, akik keresztülgázolnak mindenkin.
A megmaradt gráfra már teljesül ez a kritérium.
Nagy kár, hogy ez csak egy szükséges feltétel.
Vagyis hiába teljesül, az még nem bizonyítja a síkbarajzolhatóságot.
Ha be akarjuk bizonyítani, hogy a megmaradt gráf síkbarajzolható, akkor nincs mese, síkba kell rajzolni.
Bárcsak mindennel így lenne szerencsénk…
