Гомеоморфизм (теория графов)

Concept in graph theory

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

Подразделение и сглаживание

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

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

можно разделить на два ребра, e ₁ и e ₂ , соединяющиеся с новой вершиной w степени -2 или степени вхождения -1 и степени исхода -1 для направленного ребра:

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

Реверсия

Обратная операция, сглаживание или сглаживание вершины w относительно пары ребер ( e ₁ , e ₂ ), инцидентных w , удаляет оба ребра, содержащие w , и заменяет ( e ₁ , e ₂ ) новым ребром, соединяющим другие конечные точки пары. Здесь подчеркивается, что сглаживаться могут только вершины степени -2 (т.е. 2-валентные). Предел этой операции реализуется графом, который больше не имеет вершин степени -2.

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

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

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

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

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

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

Конечный граф является планарным тогда и только тогда, когда _он не содержит подграфа, гомеоморфного K5 ( полный граф на пяти вершинах) или K3,3 ( полный двудольный граф на шести _{вершинах} , три из которых соединены с каждой из трех других).

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

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

Пример

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

Если G′ — это граф, созданный путем деления внешних ребер G , а H′ — это граф, созданный путем деления внутреннего ребра H , то G′ и H′ имеют схожий рисунок графа:

Следовательно, существует изоморфизм между G' и H' , то есть G и H гомеоморфны.

смешанный график

Следующие смешанные графы гомеоморфны. Направленные ребра показаны имеющими промежуточный наконечник стрелки.

Смотрите также

• Малая (теория графов)
• Сокращение края

Ссылки

1. Archdeacon, Dan (1996), "Топологическая теория графов: обзор", Surveys in graph theory (Сан-Франциско, Калифорния, 1995) , Congressus Numerantium, т. 115, стр. 5–54, CiteSeerX  10.1.1.28.1728 , MR  1411236, Название возникает потому, что и гомеоморфны как графы тогда и только тогда, когда они гомеоморфны как топологические пространства. ${\displaystyle G}$ ${\displaystyle H}$
2. Трудо, Ричард Дж. (1993). Введение в теорию графов. Довер. стр. 76. ISBN 978-0-486-67870-2. Получено 8 августа 2012 г. . Определение 20. Если к некоторым ребрам графа G добавляются новые вершины степени 2 , то полученный граф H называется расширением графа G.
3. Наиболее часто изучаемая в литературе проблема под названием проблемы гомеоморфизма подграфа заключается в том, является ли подразделение H изоморфным подграфу G . Случай, когда H является циклом с n вершинами, эквивалентен проблеме гамильтоновых циклов и, следовательно, является NP-полной. Однако эта формулировка эквивалентна только вопросу о том, является ли H гомеоморфным подграфу G , когда H не имеет вершин степени два, поскольку она не допускает сглаживания в H . Можно показать, что поставленная проблема является NP-полной с помощью небольшой модификации редукции гамильтонова цикла: добавить по одной вершине к каждой из H и G , смежной со всеми остальными вершинами. Таким образом, одновершинное увеличение графа G содержит подграф, гомеоморфный графу-колесу с ( n  + 1) вершинами , тогда и только тогда, когда G является гамильтоновым. О сложности проблемы гомеоморфизма подграфов см., например, LaPaugh, Andrea S. ; Ривест, Рональд Л. (1980), «Проблема гомеоморфизма подграфов», Журнал компьютерных и системных наук , 20 (2): 133–149, doi : 10.1016/0022-0000(80)90057-4 , hdl : 1721.1/148927 , MR  0574589.

Дальнейшее чтение

• Йеллен, Джей; Гросс, Джонатан Л. (2005), Теория графов и ее приложения , Дискретная математика и ее приложения (2-е изд.), Chapman & Hall/CRC, ISBN 978-1-58488-505-4