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

Не следует путать с Гомоморфизмом графов.

Два графа ${\displaystyle G}$ и ${\displaystyle G'}$ гомеоморфны, если существует изоморфизм некоторого подразделения графа ${\displaystyle G}$ и некоторого подразделения графа ${\displaystyle G'}$^[1]. Если рёбра графа понимать как отрезки, соединяющие вершины (как обычно рисуется на иллюстрациях), то два графа гомеоморфны в контексте теории графов, когда они гомеоморфны в топологическом смысле.

Подразделение и исключение

В общем случае подразделение графа G (иногда используется термин расширение^[2] или подразбиение) — это граф, полученный делением рёбер в G. Деление некоторого ребра e с конечными вершинами {u,v} даёт граф, содержащий новую вершину w и два ребра {u,w} и {w,v} вместо ребра e^[1].

Например, ребро e с концами {u,v}:

может быть разделено на два ребра, e₁ и e₂:

Обратная операция, исключение вершины w с инцидентными ей рёбрами (e₁ ,e₂), заменяет смежные вершине w оба ребра (e₁ ,e₂) на новое ребро, соединяющее конечные точки пары. Следует подчеркнуть, что данная операция применима только к вершинам, инцидентным в точности двум рёбрам.

Например, простой связный граф с двумя рёбрами e₁ {u,w} и e₂ {w,v}:

имеет вершину (с именем w), которая может быть исключена, в результате получим:

Определение, гомеоморфен ли граф H подграфу G, является NP-полной задачей^[3].

Барицентрические подразделения

Барицентрическое подразделение разбивает каждое ребро графа. Это специальный вид подразделения, дающий всегда двудольный граф. Эту процедуру можно повторять, так что n-ое барицентрическое подразделение является барицентрическим подразделением подразделения n-1. Второе такое подразделение всегда является простым графом.

Вложение в поверхность

Очевидно, что подразделение графа сохраняет планарность. Теорема Понтрягина — Куратовского утверждает, что

конечный граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного K₅ (полный граф с пятью вершинами), или K_3,3 (полный двудольный граф с шестью вершинами, из которых три соединены с каждой из оставшихся трёх).

Фактически, граф, гомеоморфный K₅ или K_3,3, называется подграфом Куратовского.

Обобщение, следующее из теоремы Робертсона — Сеймура, утверждает, что для любого целого g существует конечное препятствующее множество графов ${\displaystyle L(g)=\{G_{i}^{(g)}\}}$, такое, что граф H вложим в поверхность рода g тогда и только тогда, когда H не содержит копии, гомеоморфной какому-либо графу ${\displaystyle G_{i}^{(g)}}$. Например, ${\displaystyle L(0)=\{K_{5},K_{3,3}\}}$ состоит из подграфов Куратовского.

Пример

В следующем примере графы G и H гомеоморфны.

G

H

Если граф G' создан подразделением внешних рёбер графа G, а граф H' создан подразделением внутренних рёбер графа H, то G' и H' имеют похожие графические представления:

G', H'

Таким образом, существует изоморфизм между графами G' и H', что и означает, что G и H гомеоморфны.

См. также

• Минор графа
• Стягивание ребра