Homeomorfizm grafów – relacja równoważności w zbiorze grafów, wiążąca grafy jednokształtne.
Dwa grafy
i
są homeomorficzne jeśli można je otrzymać z pewnego grafu
poprzez skończoną sekwencję operacji elementarnego podpodziału. Pojedyncza operacja elementarnego podpodziału dla krawędzi
polega na dodaniu do zbioru wierzchołków grafu nowego wierzchołka
dodaniu do zbioru krawędzi
i
oraz usunięcie krawędzi
w wyniku czego otrzymujemy:
Inaczej: Dwa grafy
i
są homeomorficzne, jeśli można je oba otrzymać z pewnego grafu
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.
Najważniejsze pojęcia |
|
---|
Wybrane klasy grafów |
|
---|
Algorytmy grafowe |
|
---|
problemy grafowe |
|
---|
Inne zagadnienia |
|
---|