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.