Homeomorfizm grafów

Homeomorfizm grafów – relacja równoważności w zbiorze grafów, wiążąca grafy jednokształtne.

Dwa grafy ${\displaystyle G_{1}}$ i ${\displaystyle G_{2}}$ są homeomorficzne jeśli można je otrzymać z pewnego grafu ${\displaystyle G}$ poprzez skończoną sekwencję operacji elementarnego podpodziału. Pojedyncza operacja elementarnego podpodziału dla krawędzi ${\displaystyle e=\{u,v\}}$

polega na dodaniu do zbioru wierzchołków grafu nowego wierzchołka ${\displaystyle w,}$ dodaniu do zbioru krawędzi ${\displaystyle \{u,w\}}$ i ${\displaystyle \{w,v\}}$ oraz usunięcie krawędzi ${\displaystyle \{u,v\},}$ w wyniku czego otrzymujemy:

Inaczej: Dwa grafy ${\displaystyle G_{1}}$ i ${\displaystyle G_{2}}$ są homeomorficzne, jeśli można je oba otrzymać z pewnego grafu ${\displaystyle G}$ przez zastępowanie krawędzi grafu łańcuchami prostymi.

Bibliografia

• Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, Pearson Education, 2004, s. 542–543. ISBN 0-201-72634-3.