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

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

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

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

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

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

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

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

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

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

Барицентрическое подразделение разбивает каждое ребро графа. Это специальный вид подразделения, дающий всегда двудольный граф . Эту процедуру можно повторять, так что 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 гомеоморфны.

См. также

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

Примечания

Литература

• Richard J. Trudeau. Определение 20. If some new vertices of degree 2 are added to some of the edges of a graph G , the resulting graph H is called an expansion of G . // Introduction to Graph Theory. — Corrected, enlarged republication.. — New York, 1993. — С. 76. — ISBN 978-0-486-67870-2 .
• Andrea S. LaPaugh, Ronald L. Rivest. The subgraph homeomorphism problem // Journal of Computer and System Sciences. — 1980. — Т. 20 , вып. 2 . — С. 133–149 . — doi : .
• Jay Yellen, Jonathan L. Gross. Graph Theory and Its Applications. — 2nd. — Boca Raton: Chapman & Hall/CRC, 2005. — (Discrete Mathematics and Its Applications). — ISBN 978-1-58488-505-4 .
• Яблонский С.В. Введение в дискретную математику. — М. : Наука, 1986.