Гомеоморфизм (теория графов) - Homeomorphism (graph theory)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обобщение, следующее из теоремы Робертсона – Сеймура , утверждает, что для каждого целого числа g существует конечное множество препятствий для графов, такое что граф H вложим на поверхность рода g тогда и только тогда, когда H не содержит гомеоморфной копии любого из . Например, состоит из подграфов Куратовского. ${\ Displaystyle L (г) = \ влево \ {G_ {я} ^ {(г)} \ вправо \}}$ ${\ Displaystyle G_ {я} ^ {(г)}}$ ${\ 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 гомеоморфны.

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

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

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

[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.

Languages

In other projects