Homeomorfizm grafów

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

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

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

Inaczej: Dwa grafy $G_1$ i $G_2$ są homeomorficzne, jeśli można je oba otrzymać z pewnego grafu $G$ przez zastępowanie krawędzi grafu łańcuchami prostymi.

Bibliografia

• Ralph P. Grimaldi: Discrete and Combinatorial Mathematics, Pearson Education, 2004, s. 542–543. Szablon:ISBN.