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

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

Подразделение и сглаживание [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример [ править ]

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

График Ж

График Н

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

Граф G' , H'

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

См. также [ править ]

Ссылки [ править ]

^ Архидиакон, Дэн (1996), «Топологическая теория графов: обзор», Обзоры по теории графов (Сан-Франциско, Калифорния, 1995) , Congressus Numerantium, vol. 115, стр. 5–54, CiteSeerX 10.1.1.28.1728 , MR 1411236 , Название возникает потому, что $G$ и $H$ гомеоморфны как графы тогда и только тогда, когда они гомеоморфны как топологические пространства
^ Трюдо, Ричард Дж. (1993). Введение в теорию графов . Дувр. п. 76. ИСБН 978-0-486-67870-2 . Проверено 8 августа 2012 г. Определение 20. Если к некоторым ребрам графа G то полученный граф H называется расширением G. добавляются новые вершины степени 2 ,
^ Более часто изучаемая проблема в литературе под названием проблемы гомеоморфизма подграфа заключается в том, изоморфно ли подразделение H подграфу G . Случай, когда H является n -вершинным циклом, эквивалентен задаче о гамильтоновом цикле и, следовательно, является NP-полным. Однако эта формулировка эквивалентна только вопросу о том, гомеоморфен ли H подграфу G , когда H не имеет вершин второй степени, поскольку она не допускает сглаживания в H . Можно показать, что сформулированная задача является NP-полной, если внести небольшую модификацию редукции гамильтонова цикла: добавить по одной вершине к каждой из H и G , смежной со всеми остальными вершинами. Таким образом, одновершинное пополнение графа G содержит подграф, гомеоморфный с ( n + 1) вершинами графу-колесу , тогда и только тогда, когда G гамильтонов. О сложности проблемы гомеоморфизма подграфов см., например, ЛаПо, Андреа С .; Ривест, Рональд Л. (1980), «Проблема гомеоморфизма подграфов», Journal of Computer and System Sciences , 20 (2): 133–149, doi : 10.1016/0022-0000(80)90057-4 , MR 0574589 .

Дальнейшее чтение [ править ]

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

[1] Архидиакон, Дэн (1996), «Топологическая теория графов: обзор», Обзоры по теории графов (Сан-Франциско, Калифорния, 1995) , Congressus Numerantium, vol. 115, стр. 5–54, CiteSeerX 10.1.1.28.1728 , MR 1411236 , Название возникает потому, что $G$ и $H$ гомеоморфны как графы тогда и только тогда, когда они гомеоморфны как топологические пространства

[2] Трюдо, Ричард Дж. (1993). Введение в теорию графов . Дувр. п. 76. ИСБН 978-0-486-67870-2 . Проверено 8 августа 2012 г. Определение 20. Если к некоторым ребрам графа G то полученный граф H называется расширением G. добавляются новые вершины степени 2 ,

[3] Более часто изучаемая проблема в литературе под названием проблемы гомеоморфизма подграфа заключается в том, изоморфно ли подразделение H подграфу G . Случай, когда H является n -вершинным циклом, эквивалентен задаче о гамильтоновом цикле и, следовательно, является NP-полным. Однако эта формулировка эквивалентна только вопросу о том, гомеоморфен ли H подграфу G , когда H не имеет вершин второй степени, поскольку она не допускает сглаживания в H . Можно показать, что сформулированная задача является NP-полной, если внести небольшую модификацию редукции гамильтонова цикла: добавить по одной вершине к каждой из H и G , смежной со всеми остальными вершинами. Таким образом, одновершинное пополнение графа G содержит подграф, гомеоморфный с ( n + 1) вершинами графу-колесу , тогда и только тогда, когда G гамильтонов. О сложности проблемы гомеоморфизма подграфов см., например, ЛаПо, Андреа С .; Ривест, Рональд Л. (1980), «Проблема гомеоморфизма подграфов», Journal of Computer and System Sciences , 20 (2): 133–149, doi : 10.1016/0022-0000(80)90057-4 , MR 0574589 .

[1]

[2]

[3]