Topologikus izomorfia

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, illetve gráfhomeomorfizmusnak nagy jelentősége van a síkba rajzolható gráfoknál.

Példa

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

G

H

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'

tehát G és H topologikusan izomorfak.

Síkba rajzolás

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 K₅ teljes ötpontú gráffal vagy a K_3,3 páros gráffal topologikusan izomorf részgráfot.

A Kuratowski-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 K₅ és K_3,3.