- Kombinatorika
- Gráfelméleti alapok
- Gráfok izomorfiája és síkbarajzolhatósága
- Gráfok bejárása és gráfalgoritmusok
- Kromatikus szám, klikk, perfekt gráfok
- Gráfparaméterek, párosítások
- Hálózatok
- Irányított gráfok, gráfalgoritmusok irányított gráfokban
- Menger tételei, többszörös összefüggőség
- Páros gráfok, párosítások
Gráfok izomorfiája és síkbarajzolhatósága
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.
Gráf komplementere
Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.
Gráfok izomorfiája
A $G(V(G),E(G))$ gráf izomorf a $G'(V(G'), E(G'))$ gráffal, ha van egy bijekció a $V(G)$ és $V'(G)$ között, amire teljesül, hogy $G$-ben pontosan akkor szomszédos két pont, ha $G'$-ben a nekik megfelelő pontok szomszédosak, és szomszédos pontpárok esetén ugyanannyi él fut közöttük.
Topologikus izomorfia
Egy gráfban topologikusan ekvivalens átalakításnak nevezzük azt, ha egy élt egy másodfokú csúcs beiktatásával két élre bontunk, vagy ha egy 2 fokú csúcsra illeszkedő éleket egybeolvasztunk, és a csúcsot elhagyjuk.
Két gráf akkor topologikusan izomorf, ha topologikusan ekvivalens lépések egymás utáni alkalmazásával el tudjuk érni, hogy a két gráf izomorf legyen.
Gráfok izomorfiájának vizsgálata
A titkos recept gráfok izomorfiájának vizsgálatához:
1) Fokszámok vizsgálata
2) Utak hossza
3) Van-e kör?
4) Milyen hosszúak a körök?
5) Élek vizsgálata
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 \)
a) Egy 24 csúcsú G egyszerű gráfban 12 csúcs foka 5, a másik 12 csúcs foka pedig 16. Összefüggő-e a G gráf komplementere?
b) Egy összefüggő egyszerű gráfnak 40 csúcsa és 42 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző kör. Két kör akkor különböző, ha van legalább egy olyan él, amelyiket az egyik kör tartalmazza, de a másik nem.
c) Egy összefüggő egyszerű gráfnak 1000 csúcsa és 1000 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző feszítőfa. Két feszítőfa akkor különböző, ha van legalább egy olyan él, amelyiket az egyik feszítőfa tartalmazza, de a másik nem.
a) Egy 1000 pontú gráfról tudjuk, hogy 50 csúcs mindegyikének a foka legfeljebb 7 a másik 50 csúcs foka pedig legalább 56. Hány éle van ennek a gráfnak?
b) Egy konferencián 60-an vesznek részt. A résztvevők közül 20-an már legalább 27 emberrel kezetfogtak, a többiek pedig még csak legfeljebb 4 emberrel. Hány kézfogás történt eddig?
c) Bizonyítsuk be, hogy egy G gráf és a komplementere közül legalább az egyik összefügő.
a) Bizonyítsuk be, hogy minden egyszerű, síkbarajzolható gráfban van olyan csúcs, melynek foka legfeljebb 5.
b) Legyen G egy 13 pontú egyszerű gráf. Bizonyítsuk be, hogy G és a komplementere közül legalább az egyik nem síkbarajzolható.
c) Létezik-e olyan 4, 5, illetve 6 csúcsú gráf, amely izomorf a saját komplementerével?
d) Az 1000 csúcsú G gráf nem tartalmaz kört, a komponenseinek száma 8. Hány éle van G-nek?
e) Egy fában csak két különböző fokszám fordul elő: az egyik fajta 7-szer, a másik 44-szer. Mi a szóban forgó két fokszám?
a) Hány csúcsa van egy síkbarajzolható 3-reguláris gráfnak, ha a síkbarajzolás során 20 tartomány keletkezik?
b) Egy versenyre 6 különböző országból érkeztek versenyzők. Bizonyítsuk be, hogy van köztük két olyan versenyző, akiknek az országa nem határos egymással.
c) Egy versenyre különböző országból érkeztek versenyzők. Legfeljebb hány országból indulhattak a versenyzők, ha bármelyik két versenyző szomszédos országból érkezett?
d) Egy 20 csúcsú, 3 komponensű gráfnak 18 éle van. Mutassuk meg, hogy a komponensek közül pontosan kettő fa.
e) Egy 100 csúcsú egyszerű gráfban minden pont foka legalább 33. Mutassuk meg, hogy a gráfhoz hozzá lehet venni egyetlen új élt úgy, hogy a kapott gráf összefüggő legyen.
f) Mutassuk meg, hogy minden összefüggő gráfban van olyan csúcs, melyet a gráfból elhagyva (az összes rá illeszkedő éllel együtt) összefüggő gráfot kapunk.
g) Rajzoljuk le az összes 3, 4, illetve 5 pontú fát. (Az izomorfakat csak egyszer)
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…
Itt van ez a 6 csúcsú egyszerű gráf.
Biztosra mentünk, és minden csúcsot mindegyikkel összekötöttük.
Vagyis ez itt egy K6.
Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.
Ebben a gráfban mindenki mindenkivel szomszédos…
így aztán a komplementer ez.
Ha néhány csúcs van csak összekötve…
akkor a komplementerben is néhány csúcs lesz összekötve.
Azok, akik eredetileg nem.
Nem túl meglepő, hogy egy gráf és komplementere együtt kiadja a teljes gráfot.
Hiszen egy él vagy az eredeti gráfban van behúzva…
vagy, ha ott nincs, akkor a komplementerben.
Most pedig nézzünk egy nagyon hasznos dolgot.
Van ez a gráf, és válasszuk ki néhány csúcsát.
Mondjuk, válasszuk ki ezeket itt.
Ezek a csúcsok ötödfokú csúcsok.
De csak hárman vannak, ezért csúcsonként csak 2 fokszámnyi élt tudnak egymás közt elpasszolni…
a maradék többi él kénytelen valamilyen más csúcsba vezetni.
Itt vannak aztán ezek a csúcsok is.
Egymás közt itt sem túl sok él megy.
A maradék többi él itt is kénytelen másfelé szerencsét próbálni.
És éppen ugyanannyi elvándorló él van az egyik halmaz csúcsainál, mint a másiknál.
Így aztán nagy az öröm az egymásra találásnál.
Most nézzük, mi a helyzet ezzel az egyszerű gráffal.
Annyit tudunk róla, hogy van 3 ötödfokú csúcsa és 3 elsőfokú csúcsa.
Lássuk a gráf éleit.
Egyáltalán nem biztos, hogy itt mindenki mindenkivel össze van kötve.
De most képzeljük azt egy pillanatra, hogy igen.
A csúcsok fokszáma 5, így aztán még van jónéhány él, ami kivezet az A-n kívülre.
Amíg ezeket az éleket a többi csúcs képes fogadni, nincs is semmi baj.
De most úgy tűnik, hogy nagy baj van.
Sajnos a B halmaz legfeljebb 3 élt tud fogadni.
És az A-ból legalább 9 él indul.
Ha nincs mindenki mindenkivel összekötve, akkor még több is.
De a 9 él az biztos.
Így aztán nem lesz egyezség. Ilyen gráf nem létezhet.
Ha persze G nem egyszerű gráf, úgy könnyű…
De a megadott tulajdonságokkal rendelkező egyszerű gráf…
nem létezik.
Egy 24 csúcsú G egyszerű gráfban 12 csúcs foka 5, a másik 12 csúcs foka pedig 16. Összefüggő-e a G gráf komplementere?
A 12 csúcs, ahol mindenkinek a fokszáma 16 meglehetősen brutális.
Ha minden csúcs minden másikkal össze van kötve…
már az is elképesztően sok él.
És akkor itt minden csúcs fokszáma még csak 11.
Úgy jön ki a 16, ha van még csúcsonként plusz 5 él.
Most nézzük, a B halmaz mennyit képes közülük fogadni.
Pont ennyit.
Vagyis az A halmazból csúcsonként legalább 5 él kell, hogy kivezessen, a B pedig csúcsonként maximum ennyit képes fogadni.
Ez azt jelenti, hogy pontosan tudjuk, hogyan néz ki a gráf.
Van benne egy K12 és annak minden csúcsa össze van kötve a B halmaz 5 különböző csúcsával.
Most nézzük, hogy mi lesz ennek a gráfnak a komplementere.
Itt senki senkivel nem lesz összekötve, az egyszer biztos.
Aztán a csúcsonkénti 5 él helyett a többi csúcsba megy 7 él.
B-ben meg jó sok él be lesz húzva, de a lényeg…
ezek az élek.
Ez garantálja, hogy B-ben bármely két csúcs között vezet út.
Mivel pedig A-nak bármely csúcsa össze van kötve legalább egy B-beli csúccsal, így bármely két A-beli csúcs között is vezet út.
Így aztán a G gráf komplementere összefüggő.
Egy összefüggő egyszerű gráfnak 40 csúcsa és 42 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző kör. Két kör akkor különböző, ha van legalább egy olyan él, amelyiket az egyik kör tartalmazza, de a másik nem.
Nem fogunk itt bajlódni 40 darab csúccsal.
Azt kell megérteni, hogy lehetne 50 csúcsú és 52 élű is a gráf, vagy 1000 csúcsú és 1002 élű, a lényeg itt nem ez.
A lényeg itt az, hogy egy n csúcsú összefüggő gráfnak minimum n-1 darab éle van.
Ebben az esetben a gráf körmentes, hiszen fa.
Ha hozzáveszünk az n-1 darab élhez még egyet, akkor valahol kör keletkezik.
Ha még egy élt hozzáveszünk, akkor még egy kör keletkezik, ami biztosan különbözik az előző körtől, hiszen abban nem szerepelhetett az az él, amit most vettünk hozzá a gráfhoz.
És még egy él hozzávételével még egy kör keletkezik.
Az állítást bizonyítottuk, ráadásul nem csak a 40 csúcs 42 él esetre, hanem általánosan.
Még azon is el lehet filozofálni, hogy összesen hány kör keletkezik.
Van úgy, hogy csak 3…
Aztán lehet benne 4 kör is.
És maximum 6.
Egy összefüggő egyszerű gráfnak 1000 csúcsa és 1000 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző feszítőfa. Két feszítőfa akkor különböző, ha van legalább egy olyan él, amelyiket az egyik feszítőfa tartalmazza, de a másik nem.
Vegyük a gráfnak egy feszítőfáját. A feszítőfának 999 éle van.
Ha ezek után hozzávesszük az ezredik élt, akkor keletkezik egy kör.
Nem tudjuk, hogy a kör hány élt tartalmaz…
De három különböző élt egészen biztosan.
Bármelyiket elhagyva a gráfnak egy-egy különböző feszítőfáját kapjuk.
Van itt ez a három gráf…
ami valójában csak egy.
Ez a három gráf ugyanannak a gráfnak a három különböző vizualizációja.
A három gráf egymással
Van itt ez a három gráf…
ami valójában csak egy.
Ez a három gráf ugyanannak a gráfnak a három különböző vizualizációja.
A három gráf egymással izomorf.
A G(V(G), E(G)) gráf izomorf a G’(V(G’), E(G’)) gráffal, ha van egy bijekció a V(G) és V(G’) között…
amire teljesül, hogy G-ben pontosan akkor szomszédos két pont, ha G’-ben a nekik megfelelő pontok szomszédosak…
és szomszédos pontpárok esetén ugyanannyi él fut közöttük.
Szemléletesen két gráf akkor izomorf, ha mindkettőt ugyanúgy le tudjuk rajzolni.
De sajnos az izomorfia eldöntése sokszor igencsak nehéz feladat tud lenni.
Erről hamarosan személyesen is meggyőződhetünk.
Ha egy lépést hátrább lépünk…
És a gráfban csak az élek hálózatára koncentrálunk…
Akkor eljutunk egy másik fogalomhoz, amit topológiai izomorfiának neveznek.
Ez a két gráf topológiailag izomorf.
Sőt ez a három is.
Egy gráfban topologikusan ekvivalens átalakításnak nevezzük azt, ha egy élt egy másodfokú csúcs beiktatásával két élre bontunk…
vagy ha egy 2 fokú csúcsra illeszkedő éleket egybeolvasztunk, és a csúcsot elhagyjuk.
Két gráf akkor topologikusan izomorf, ha topologikusan ekvivalens lépések egymás utáni alkalmazásával el tudjuk érni, hogy a két gráf izomorf legyen.
Most pedig elérkezett az idő, hogy lássunk néhány trükköt…
aminek a segítségével el tudjuk dönteni, hogy két gráf izomorf-e vagy sem.
Van itt ez a néhány gráf.
És próbáljuk meg kitalálni, hogy melyek izomorfak egymással.
Titkos recept az izomorfia vizsgálatához.
A legegyszerűbb dolog, amit érdemes megnézni, a csúcsok fokszáma.
A másodfokú csúcsokból kicsit sok van, de nézzük a harmadfokú és negyedfokú csúcsokat.
Negyedfokú csúcs csak G4-ben van, így aztán ez nem izomorf semelyik másik gráffal sem.
Aztán itt van ez a G6, amiben két harmadfokú csúcs is van, a többiben csak egy.
Nyilvánvalóan ő sem lehet izomorf semelyik másikkal.
Nézzük, mit kezdhetnénk a megmaradt gráfokkal.
Számoljuk meg, a harmadfokú csúcsra milyen hosszú utak csatlakoznak.
2) Utak hossza
Egyetlen él hosszúságú út G1-en és G3-on van.
A megmaradt gráfokon pedig két darab 2 hosszú út indul.
Egy kis nézelődés után látni, hogy ezek izomorfak.
És ezek is.
Most pedig nézzük, hogy milyen fortélyok vannak még az izomorfia eldöntésénél.
Derítsük ki, hogy melyek izomorfak ezek közül a gráfok közül:
Kezdjük a fokszámokkal.
Mindenhol harmadfokú csúcsok vannak, kivéve a G3-ban.
Úgyhogy a G3-nak annyi…
Most nézzük, van-e kör.
3) Van-e kör?
Hát igen, csak az van.
Úgyhogy nézzük meg a körök hosszát.
4) Milyen hosszúak a körök?
Itt a G1-ben van 3 hosszú kör.
De G2-ben és G4-ben nincs, ott minden kör legalább 4 hosszú.
Vagyis G1 nem lehet izomorf sem G2-vel, sem G4-gyel.
A dolog most kezd érdekes lenni…
Egyre inkább valószínű, hogy ezek a gráfok izomorfak.
De valahogyan be kell ezt bizonyítani.
A két gráf akkor izomorf, ha tudunk létesíteni a csúcsaik között bijekciót.
Hát, próbáljuk meg.
Induljunk ki egy tetszőleges csúcsból a G2 gráfban.
És vegyük, mondjuk ezt a 4 hosszú kört.
Szép, egészséges harmadfokú csúcsok vannak rajta.
Éppen úgy, mint ezen.
Kezdjük el megalkotni a bijekciót.
Még két csúcs hiányzik.
Az egyik A6 harmadik szomszédja, aki nincs rajta a körön.
Neki B1 harmadik szomszédja felel meg.
Végül az utolsó csúcs kizárásos alapon…
Egyetlen dolgunk van még: a szomszédokat tesztelni.
És a többi csúcs is stimmelni fog.
Vagyis ezek a gráfok izomorfak.
Amit immár vizuálisan is igazoltunk.
Végül itt jön egy igazi rémtörténet.
Nézzük, ezek a gráfok izomorfak-e.
A fokszámok vizsgálatával nem jutunk túl messzire: sajna minden gráf minden csúcsa negyedfokú.
Ide komolyabb eszközök kellenek…
Ugorjunk egyből a 4-es pontra.
Figyeljük a 3 hosszúságú köröket.
G1-ben találni olyan szomszédos pontokat, akikhez három különböző kör is tartozik.
G2-ről és G3-ról ez nem mondható el.
Próbáljuk meg valahogyan földeríteni a 3 hosszú köröket a gráfokban.
Nézzük meg, hogy egy adott él hány különböző 3 hosszú körben szerepel.
5) Élek vizsgálata
Színekkel fogjuk jelölni, hogy egy adott él hány darab 3 hosszú körben vesz részt.
G1-ben hat darab 3 hosszú kör van.
Most nézzük, mi a helyzet G2-vel.
És G3-mal.
Úgy tűnik G2 és G3 izomorf.
Jó lenne mondjuk találni köztük egy bijekciót.
Végül teszteljük, hogy minden rendben van-e a szomszédokkal…
Aki még nem unja, nézze meg a többit is.
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…
Egy 100 pontú gráfról tudjuk, hogy 50 csúcs mindegyikének a foka legfeljebb 7 a másik 50 csúcs foka pedig legalább 56.
Kérdés: hány éle van ennek a gráfnak?
Ezek azok a feladatok, amiért az ember nagyon utálja a gráfelméletet…
vagy épp nagyon szereti.
Lássuk, mit kezdhetnénk az ilyen megfoghatatlannak tűnő kérdésekkel.
Az első fontos észrevétel, hogy egy egyszerű gráfban a csúcsok foka azért nem lehet olyan hatalmas.
K6-ban például minden csúcs foka 5.
És K50-ben minden csúcs foka 49.
Ezt már föl sem tudjuk rajzolni…
És nyilván ez a sötét gondolat motiválta a feladat készítőjét is.
Rajzolgatás helyett gondolkodnunk kell.
Ennek az 50 csúcsnak a fokszáma olyan nagy…
hogy csúcsonként csak 49 élt tudnak egymás közt elpasszolni.
a maradék 56-49=7 él kénytelen valamilyen más csúcsba vezetni.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K50 lakozik és minden csúcs pontosan 56 fokú, akkor pontosan 350 él hagyja el az A halmazt.
De az is lehet, hogy ez az 50 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak további élek, amik kivezetnek A-ból.
A másik 50 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 7. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 350 éltől akar megszabadulni…
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 350 lesz a végső egyezség.
Van tehát ez a 350 él.
B-ben további élek már nem lehetnek.
A-ban pedig még ezen a 350 élen kívül minden csúcs mindegyikkel össze van kötve:
Ez így akkor összesen annyi, mint 350+1225=1575 él.
Hát, ennyi éle van a gráfnak.
Nézzünk még egy ilyet.
Egy konferencián 60-an vesznek részt. A résztvevők közül 20-an már legalább 27 emberrel kezetfogtak, a többiek pedig még csak legfeljebb 4 emberrel.
Hány kézfogás történt eddig?
Ez a történet valahonnan nagyon ismerősnek tűnik…
Ja igen, ezt a feladatot oldottuk meg az előbb.
Van ez a 20 ember azzal a rengeteg kézfogással…
Ha itt mindenki mindenkivel kezetfog, akkor ez egy K20.
K20-ban a csúcsok fokszáma 19, de itt a csúcsok fokszáma 27, vagyis csúcsonként legalább 27-19=8 él kivezet a halmazból.
Hívjuk a csúcsoknak ezen halmazát A halmaznak.
Ha az A halmazban valóban egy K20 lakozik és minden csúcs pontosan 27 fokú, akkor pontosan 160 él hagyja el az A halmazt.
De az is lehet, hogy ez az 20 csúcs nem egy teljes gráfot alkot.
Ilyenkor vannak még további élek, amik kivezetnek A-ból.
A másik 40 csúcs halmaza legyen a B halmaz.
Ebben a B halmazban a csúcsok foka legfeljebb 4. Ha a halmazon belül semelyik két csúcs között nem vezet él, akkor...
legfeljebb ennyi él vezethet kívülről a B halmazba.
Ha az egyik halmaz legalább 160 éltől akar megszabadulni...
a másik pedig legfeljebb ennyit tud fogadni, akkor valami azt súgja, hogy itt a 160 lesz a végső egyezség.
Van tehát ez a 160 él.
B-ben további élek már nem lehetnek.
Ők a kockák. Elmennek úgy egy konferenciára, hogy még csak kezet se fognak egymással.
Az A-ban vannak a hiperaktívak, már mindenki mindenkivel kezetfogott, ami egy K20:
És már elkezdtek barátkozni a kockákkal is, 8 kézfogás/fő sebességgel.
Ez így akkor annyi mint 190+160=250 darab kézfogás.
Ennyi kézfogás történt eddig.
Végül nézzünk meg egy nagyon izgalmas ügyet.
Bizonyítsuk be, hogy egy G gráf és a komplementere közül legalább az egyik összefüggő.
Ha az eredeti G gráf összefüggő, akkor nincsen semmi baj.
Az állítás igaz.
Ha az eredeti G gráf nem összefüggő, akkor több komponensből áll.
Nézzük először azt az esetet, amikor kettőből.
Arról nem rendelkezünk információval, hogy a komponenseken belül mely csúcsok szomszédosak.
De az biztos, hogy a gráf komplementerében az A komponens egy tetszőleges csúcsa össze lesz kötve B minden csúcsával.
Mert a komplementerben minden olyan élt be kell húznunk, ami most nincs behúzva.
És mivel az A komponens bármely csúcsa össze lesz kötve B minden csúcsával…
az így keletkező gráf biztosan összefüggő.
Hiszen ennek a gráfnak részgráfja egy A és B pontosztályú páros gráf.
Ha pedig az eredeti G gráfnak több komponense van…
akkor az iménti gondolatmenet bármely két komponensre igaz.
Így a komplementer gráfban bármely két csúcsosztály pontjai összefüggő részgráfot alkotnak.
És emiatt a komplementer gráf összefüggő.
