Гомеоморфізм графів

Гомеоморфізм графів — відношення еквівалентності на множині графів. Два графи називаються гомеоморфними, якщо кожен з них може бути одержаний розбиттям деякого графу. Еквівалентно два графу G і G' є гомеоморфними, якщо існують розбиття графу G і розбиття графу G', що є ізоморфними між собою.

Розбиття

Розбиттям графу називається граф, що отримується послідовним застосуванням розбиття ребер до даного графу. При розбитті ребро e з вершинами {u, v} перетворюється на граф, що містить нову вершину w і два ребра {u, w} і {w, v}. Наприклад ребро:

переходить в граф:

Послідовне застосування такого процесу еквівалентне заміні деяких ребер графу певними простими шляхами.

Приклад

Графи зображені на рисунках гомеоморфні:


Справді кожен з них може бути розбитий до наступного графу:

G', H' graph G

Джерела

  • Р. Уилсон. Введение в теорию графов. М.: Мир, 1977