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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Розбиття[ред.ред. код]

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

Graph subdivision step1.svg

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

Graph subdivision step2.svg

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

Приклад[ред.ред. код]

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


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

G', H' graph G

Джерела[ред.ред. код]

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