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

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

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

СОДЕРЖАНИЕ

  • 1 Деление и сглаживание
    • 1.1 Барицентрические подразделения
  • 2 Вложение на поверхность
  • 3 Пример
  • 4 См. Также
  • 5 ссылки
  • 6 Дальнейшее чтение

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

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

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

Подразделение графика step1.svg

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

Подразделение графика step2.svg

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

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

Подразделение графика step2.svg

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

Подразделение графика step1.svg

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

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

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

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

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

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

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

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

Пример

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

График G График H

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

График G ', H'

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

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

Рекомендации

  1. ^ Архидиакон, Dan (1996), "Теория топологического графа: обзор", Исследования в теории графов (Сан - Франциско, Калифорния, 1995), Congressus Numerantium, 115., С 5-54, MR   1411236, возникает потому, что имя и являются гомеоморфны как графы тогда и только тогда, когда они гомеоморфны как топологические пространства грамм {\ displaystyle G} ЧАС {\ displaystyle H}
  2. ^ Трюдо, Ричард Дж. (1993). Введение в теорию графов (исправленное, расширенное переиздание. Ред.). Нью-Йорк: Dover Pub. п. 76. ISBN   978-0-486-67870-2. Проверено 8 августа 2012 года. Определение 20. Если некоторые новые вершины степени 2 добавляются некоторые из ребер графа G, полученный граф Н называется расширением из G.
  3. ^ Более широко изучены проблемы в литературе, под названием проблемы подграф гомеоморфизму, является ли подразделение H изоморфна подграфа G. Случай, когда H является n- вершинным циклом, эквивалентенпроблеме гамильтонова цикла и, следовательно, является NP-полным. Однако эта формулировка эквивалентна только к вопросу о том, H гомеоморфно подграфа G при H не имеет степени-две вершины, потому что она не позволяет сглаживанию H. NP-полную поставленную задачу можно показать с помощью небольшой модификации редукции гамильтонова цикла: добавить по одной вершине к каждой из H и G, смежных со всеми остальными вершинами. Таким образом, одновершинное увеличение графа G содержит подграф, гомеоморфный ( n  + 1) -вершинному графу-колесу, тогда и только тогда, когда G гамильтонов. О сложности проблемы гомеоморфизма подграфов см., Например, LaPaugh, Andrea S. ; Ривест, Ronald L. (1980), "Проблема подграф гомеоморфизм", журнал компьютерных и системных наук, 20 (2): 133-149, DOI : 10,1016 / 0022-0000 (80) 90057-4, MR   0574589.

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

  • Йеллен, Джей; Гросс, Джонатан Л. (2005), Теория графов и ее приложения, Дискретная математика и ее приложения (2-е изд.), Бока-Ратон: Chapman amp; Hall / CRC, ISBN   978-1-58488-505-4
Последняя правка сделана 2023-04-16 08:28:15
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте