![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/1/15/Graph_subdivision_step1.svg/langpl-640px-Graph_subdivision_step1.svg.png&w=640&q=50)
Homeomorfizm grafów
Z Wikipedii, wolnej encyclopedia
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.