Topologikus izomorfia

A Wikipédiából, a szabad enciklopédiából

A gráfelméletben két gráf akkor topologikusan izomorf, ha csúcsoknak az élekről való ismételt elhagyásával és/vagy felvételével izomorf gráfokba transzformálhatók. Csúcsok elhagyása alatt azt értjük, hogy egy 2 fokszámú csúcsot törlünk, és az addig hozzá kapcsolódó két csúcsot egymással kötjük össze. Csúcsok felvétele ennek a fordítottja. (Például ez a két él topologikusan izomorf: •——• és •—•—•.)

A topologikus izomorfiának nagy jelentősége van a síkba rajzolható gráfoknál.

Példa[szerkesztés | forrásszöveg szerkesztése]

A G és a H gráfok topologikusan izomorfak:

G graph H

H graph G

Ha ugyanis G' az a gráf, ami a G gráfból a külső élek felosztásából keletkezik, és H' az a gráf, ami a H belső élének felosztásából keletkezik, akkor G' és H' izomorfak lesznek:

G', H' graph G

tehát G és H topologikusan izomorfak.

Síkba rajzolás[szerkesztés | forrásszöveg szerkesztése]

Könnyen látható, hogy egy gráf felosztása megőrzi a síkba rajzolhatóságot. A Kuratowski-tétel szerint egy véges gráf síkba rajzolható akkor és csak akkor, ha nem tartalmaz a K5 teljes ötpontú gráffal vagy a K3,3 páros gráffal topologikusan izomorf részgráfot.

A Kuratowsi-tétel egy általánosítása a Robertson–Seymour tétel, ami szerint minden egész g-re van véges sok gráf, amiket ha nem tartalmaz egy gráf, akkor beágyazható egy g genuszú felületbe. Például, ha g=0, akkor ezek éppen a fenti K5 és K3,3.