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

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

Розбиття

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

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

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

Приклад

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

Граф H
Граф G

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

G', H'

Джерела

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.