Гомеоморфізм графів
Гомеоморфізм графів — відношення еквівалентності на множині графів. Два графи називаються гомеоморфними, якщо кожен з них може бути одержаний розбиттям деякого графа. Еквівалентно два графа G і G' є гомеоморфними, якщо існують розбиття графа G і розбиття графа G', що є ізоморфними між собою.
Розбиття [ред.]
Розбиттям графа називається граф, що отримується послідовним застосуванням розбиття ребер до даного графа. При розбитті ребро e з вершинами {u,v} перетворюється на граф, що містить нову вершину w і два ребра {u,w} і {w,v}. Наприклад ребро:
 |
переходить в граф:
 |
Послідовне застосування такого процесу еквівалентне заміні деяких ребер графа певними простими шляхами.
Приклад [ред.]
Графи зображені на рисунках гомеоморфні:
-
Граф H
-
Граф G
Справді кожен з них може бути розбитий до наступного графа:
G', H' 
Джерела [ред.]
- Р. Уилсон. Введение в теорию графов. М.: Мир, 1977
