Русская Википедия:Гомеоморфизм графов
Два графа <math>G</math> и <math>G'</math> гомеоморфны, если существует изоморфизм некоторого подразделения графа <math>G</math> и некоторого подразделения графа <math>G'</math>Шаблон:Sfn. Если рёбра графа понимать как отрезки, соединяющие вершины (как обычно рисуется на иллюстрациях), то два графа гомеоморфны в контексте теории графов, когда они гомеоморфны в топологическом смысле.
Подразделение и исключение
В общем случае подразделение графа G (иногда используется термин расширениеШаблон:Sfn или подразбиение) — это граф, полученный делением рёбер в G. Деление некоторого ребра e с конечными вершинами {u,v} даёт граф, содержащий новую вершину w и два ребра {u,w} и {w,v} вместо ребра eШаблон:Sfn.
Например, ребро e с концами {u,v}:
| Файл:Graph subdivision step1.svg |
может быть разделено на два ребра, e1 и e2:
| Файл:Graph subdivision step2.svg |
Обратная операция, исключение вершины w с инцидентными ей рёбрами (e1 ,e2), заменяет смежные вершине w оба ребра (e1 ,e2) на новое ребро, соединяющее конечные точки пары. Следует подчеркнуть, что данная операция применима только к вершинам, инцидентным в точности двум рёбрам.
Например, простой связный граф с двумя рёбрами e1 {u,w} и e2 {w,v}:
| Файл:Graph subdivision step2.svg |
имеет вершину (с именем w), которая может быть исключена, в результате получим:
| Файл:Graph subdivision step1.svg |
Определение, гомеоморфен ли граф H подграфу G, является NP-полной задачей[1].
Барицентрические подразделения
Барицентрическое подразделение разбивает каждое ребро графа. Это специальный вид подразделения, дающий всегда двудольный граф. Эту процедуру можно повторять, так что n-ое барицентрическое подразделение является барицентрическим подразделением подразделения n-1. Второе такое подразделение всегда является простым графом.
Вложение в поверхность
Очевидно, что подразделение графа сохраняет планарность. Теорема Понтрягина — Куратовского утверждает, что
- конечный граф является планарным тогда и только тогда, когда он не содержит подграфа, гомеоморфного K5 (полный граф с пятью вершинами), или K3,3 (полный двудольный граф с шестью вершинами, из которых три соединены с каждой из оставшихся трёх).
Фактически, граф, гомеоморфный K5 или K3,3, называется подграфом Куратовского.
Обобщение, следующее из теоремы Робертсона — Сеймура, утверждает, что для любого целого g существует конечное препятствующее множество графов <math>L(g) = \{G_{i}^{(g)}\}</math>, такое, что граф H вложим в поверхность рода g тогда и только тогда, когда H не содержит копии, гомеоморфной какому-либо графу <math>G_{i}^{(g)}</math>. Например, <math>L(0) = \{K_{5}, K_{3,3}\}</math> состоит из подграфов Куратовского.
Пример
В следующем примере графы G и H гомеоморфны.
| G Граф H | H Граф G |
Если граф G' создан подразделением внешних рёбер графа G, а граф H' создан подразделением внутренних рёбер графа H, то G' и H' имеют похожие графические представления:
G', H' Подразделённые графы
Таким образом, существует изоморфизм между графами G' и H', что и означает, что G и H гомеоморфны.
См. также
Примечания
Литература
- ↑ Более широко изучаемая в литературе задача с именем «задача гомеоморфизма подграфов» спрашивает, изоморфно ли подразделение графа H подграфу G. Если H является циклом с n вершинами, задача эквивалентна задаче нахождения гамильтонова цикла, а потому NP-полна. Однако эта формулировка эквивалентна только вопросу, гомеоморфен ли граф H подграфу G, когда H не содержит вершин степени два, поскольку это не позволяет исключения в H. Можно показать, что поставленная задача NP-полна путём небольшой модификации гамильтонова цикла — добавляем по одной вершине в H и G, смежные всем другим вершинам. Тогда увеличенный на одну вершину граф G содержит подграф, гомеоморфный колесу с (n + 1) вершинами, тогда и только тогда, когда G гамильтонов. По поводу сложности задачи гомеоморфизма подграфа смотрите статью ЛаПауга и Ривеста Шаблон:Harv.
