10. Gráfok izomorfizmusa

Question 1

Gráfok izomorfizmusa:

Answer 1

A $G=(V,E)$ és $H=(W,F)$ gráfokat izomorfaknak nevezzük, és ezt $G \simeq H$ -evel jelöljük, ha létezik olyan $f:V→W$ bijekció a két csúcshalmaz között, amely éltartó, vagyis tetszőleges $x,y∈ V$ csúcsok esetén

${x, y} ∈ E ⇔ {f(x), f(y)} ∈F$ $∀x, y ∈V$

és többszörös élek esetén az élek multiplicitása a két gráfban ugyanannyi. Az f izomorf leképezést más szóval izomorzmusnak hívjuk.
Állítás: Két tetszőleges egyszerű gráf pontosan akkor izomorf ha komplementereik is izomorfak.
ÉV: Van algoritmus. $|V|=|W|=n$, összes függvény bijektív, $n! \approx \frac{n^n}{e^n}$ (Stirling formula), ell: $n^2, n!*n^2$

Question 2

A triviális algoritmus sebessége

Answer 2

Fontos kérdés az adott (tetszőleges) gráfok közötti izomorfizmus létezését eldöntő, vagy esetleg egy izomorfizmust megkereső algoritmus problémája. Bár az általános tetszőleges gráfok izomorfiája problémájának NP-teljessége ugyan nem ismert, de polinomiális algoritmust sem találtak még eddig.

A legegyszerűbb, az összes $(n!)$ permutációt végigvizsgáló algoritmus triviálisan lassú, hiszen minden sorrakerülő $f: V → W$ bijekció éltartóságának ellenőrzése $O(n^2)$ idő, vagyis algoritmusunk $O(n!*n^2)$ ideig fut.

Question 3

Invariáns tulajdonságok:

Answer 3

Gráfok egy $Φ$ tulajdonságát (gráf-)invariánsnak nevezzük, ha tetszőleges G és H izomorf gráfokra G pontosan akkor rendelkezik a $Φ$ tulajdonsággal amikor H. Állítás: Egy $Φ$ tulajdonság pontosan akkor és csak akkor gráfinvariáns ha a tagadása $¬Φ$ is gráfinvariáns. Ha van egy $Φ$ invariáns tulajdonság, amely a két adott gráf egyike rendelkezik de a másik nem, akkor a két gráf nem izomorf.

Question 4

A következő tulajdonságok gráfinvariánsak:

Answer 4

• csúcsok elemszáma
• az élek száma, multiplicitása
• csúcsok fokszámai
• élek végpontjainak fokszámai
• komponensek száma
• gráf összefüggősége
• van/nincs a gráfban k hosszúságú kör/út, általában a gráfban levő k hosszúságú körök/utak száma
• a gráf páros, általában a gráf t-pólusú
• gráfban van/nincs Euler/Hamilton -kör Nincs teljes lista, megszámlálhatóan végtelen (alef0) hosszú a lista

Question 5

Babai-Reed:

Answer 5

• Tétel: Gyökereztetett fák izomorfiája $O(n)$ (azaz lineáris) időben eldönthető, így tetszőleges fák izomorfiája $O(n^2)$ időben eldönthető.
• Algoritmus részletek nélkül: Legyenek adottak $T=(V,E)$ és $R=(W,F)$ azonos magasságú gyökerezett fák $x_0 ∈ V$ ill. $y_0 ∈ W$ gyökerekkel Olyan $f : V → W$ izomorfizmust keresünk, amelyre $f(x_0) = y_0$ és f szintenként képez, azaz f : $V_i → W_i (i ≤ ht(T))$ vagyis a T fa mindegyik szintjének képe éppen az R fa megfelelő szintje. (Megj.: ht=height)