Gráfok izomorfiája
Ennek a témakörnek a képletei
Letöltöm az egész kurzus összes képletét:
LetöltömVálogass kedvedre a témakör képletei között:
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
Ennek a témakörnek a feladatai
Letöltöm az egész kurzus összes feladatát:
LetöltömVálogass kedvedre a témakör feladatai között:
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.
Próbáljuk meg kitalálni, hogy mely gráfok izomorfak egymással.
a)
b)
c)
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.
