Плоское покрытие

Граф C является плоским покрытием графа H . Карта покрытия обозначается цветами вершин.

В теории графов плоское покрытие конечного графа G — это конечный покрывающий граф G , который сам является плоским графом . Каждый граф, который можно вложить в проективную плоскость, имеет плоское покрытие; нерешенная гипотеза Сейи Негами утверждает, что это единственные графы с плоскими покрытиями.

Существование плоского покрытия является свойством минорно-замкнутого графа , и поэтому может характеризоваться конечным числом запрещенных миноров , но точный набор запрещенных миноров неизвестен. По той же причине существует полиномиальный алгоритм проверки того, имеет ли данный граф плоское покрытие, но явное описание этого алгоритма неизвестно.

Определение

Карта покрытия одного графа C в другой граф H может быть описана функцией f из вершин C в вершины H , которая для каждой вершины v графа C дает взаимно однозначное соответствие между соседями v и соседями f. ( в ). Если H — связный граф , каждая вершина H должна иметь одинаковое количество прообразов в C ; называется слоем отображения, а C называется покрывающим графом G это число . Если C и H оба конечны и — планарный граф , то C называется плоским покрытием H. C

Примеры

Идентификация пар противоположных вершин додекаэдра дает карту покрытия графа Петерсена.

Граф додекаэдра обладает симметрией , которая отображает каждую вершину в антиподальную вершину. Множество антиподальных пар вершин и их смежностей само по себе можно рассматривать как граф, граф Петерсена . Додекаэдр образует плоское покрытие этого непланарного графа. Как показывает этот пример, не каждый граф с плоским покрытием сам по себе является планарным. Однако, когда планарный граф покрывает непланарный, количество слоев должно быть четным .

Двенадцатиугольная призма может образовывать двухслойное покрытие шестиугольной призмы , трехслойное покрытие куба или четырехслойное покрытие треугольной призмы .

Граф k -угольной призмы имеет 2 k вершин и является плоским с двумя k -угольными гранями и k четырехугольными гранями. Если k = ab , с a ≥ 2 и b ≥ 3, то оно имеет a -слойное накрытие в b -фональную призму, в котором две вершины k -призмы отображаются в одну и ту же вершину b -призмы. если они оба принадлежат одной и той же k -угольной грани и расстояние от одного до другого кратно b . Например, двенадцатиугольная призма может образовывать двухслойное покрытие шестиугольной призмы , трехслойное покрытие куба или четырехслойное покрытие треугольной призмы . Эти примеры показывают, что граф может иметь множество различных плоских покрытий и может быть плоским покрытием для многих других графов. Кроме того, они показывают, что слой плоского покрытия может быть сколь угодно большим. Это не единственные покрытия, включающие призмы: например, шестиугольная призма может также покрывать неплоский граф, граф полезности K _3,3 , идентифицируя антиподальные пары вершин.

Операции по сохранению покрытия

Если граф H имеет плоское покрытие, то же самое имеет и каждый граф H минорный . Меньший G из H может быть образован удалением ребер и вершин из H и сжатием ребер H . Покрывающий граф C можно преобразовать таким же образом: для каждого удаленного ребра или вершины в H удалить его прообраз в C а для каждого сжатого ребра или вершины в H сжать его прообраз в C. , Результатом применения этих операций к C является минор C который покрывает G. , дает плоское покрытие минора G. Поскольку каждый минор планарного графа сам по себе планарен, это

Поскольку графы с плоскими покрытиями замкнуты относительно операции взятия миноров, из теоремы Робертсона–Сеймура следует , что они могут характеризоваться конечным набором запрещенных миноров . Граф является запрещенным минором для этого свойства, если он не имеет плоского покрытия, но все его миноры имеют плоские покрытия. Эту характеристику можно использовать для доказательства существования алгоритма с полиномиальным временем , который проверяет существование плоского покрытия, выполняя поиск каждого из запрещенных миноров и возвращая, что плоское покрытие существует только в том случае, если этот поиск не может найти ни одного из них. Однако, поскольку точный набор запрещенных миноров для этого свойства неизвестен, это доказательство существования является неконструктивным и не приводит к явному описанию набора запрещенных миноров или основанного на них алгоритма.

Другая операция над графом, сохраняющая существование плоского покрытия, — это преобразование Y-Δ , которое заменяет любую вершину третьей степени графа H треугольником, соединяющим трех его соседей. Однако обратное этому преобразованию, преобразование Δ-Y, не обязательно сохраняет плоские покрытия.

Кроме того, непересекающееся объединение двух графов, имеющих покрытия, также будет иметь покрытие, образованное как непересекающееся объединение покрывающих графов. Если две обложки имеют один и тот же слой, то это также будет слой их соединения.

Гипотеза Негами

Нерешенная задача по математике :

Всякий ли связный граф с плоским покрытием имеет вложение в проективную плоскость?

(еще нерешенные задачи по математике)

Если граф H имеет вложение в проективную плоскость , то он обязательно имеет плоское накрытие, заданное прообразом H в ориентируемом двойном накрытии проективной плоскости, которое является сферой. Негами (1986) доказал, наоборот, что если связный граф H имеет двухслойное плоское покрытие, то H должно иметь вложение в проективную плоскость. Предположение о связности H здесь необходимо, поскольку дизъюнктное объединение проективно-планарных графов само по себе не может быть проективно-планарным. но все равно будет иметь плоское накрытие, представляющее собой непересекающееся объединение ориентируемых двойных накрытий.

Регулярное покрытие графа H — это покрытие, полученное из группы симметрий его графа покрытия: прообразы каждой вершины в H являются орбитой группы. Негами (1988) доказал, что любой связный граф с плоским регулярным покрытием можно вложить в проективную плоскость. На основании этих двух результатов он предположил, что на самом деле каждый связный граф с плоским покрытием проективен. По состоянию на 2013 год эта гипотеза остается нерешенной. Она также известна как «гипотеза 1-2-∞» Негами, поскольку ее можно переформулировать так, что минимальный слой плоского покрытия, если он существует, должен быть либо 1, либо 2.

K _1,2,2,2 , единственный возможный минимальный контрпример к гипотезе Негами.

Как и графы с плоскими покрытиями, графы с вложениями проективных плоскостей могут характеризоваться запрещенными минорами. В этом случае известен точный набор запрещенных несовершеннолетних: их 35. 32 из них связны, и один из этих 32 графов обязательно появляется как минор в любом связном непроективно-планарном графе. С тех пор, как Негами выдвинул свою гипотезу, было доказано, что 31 из этих 32 запрещенных миноров либо не имеют плоских покрытий, либо могут быть сведены преобразованиями Y-Δ к более простому графу из этого списка. Единственный оставшийся граф, для которого это еще не было сделано, — это K _1,2,2,2 с семью вершинами , вершинный граф , образующий скелет четырехмерной октаэдрической пирамиды . Если бы можно было показать, что K _1,2,2,2 не имеет плоских покрытий, это завершило бы доказательство гипотезы. С другой стороны, если гипотеза неверна, K _1,2,2,2 обязательно будет ее наименьшим контрпримером.

Связанная с этим гипотеза Майкла Феллоуза , теперь решенная, касается плоских эмуляторов , обобщения плоских покрытий, которое отображает окрестности графа сюръективно, а не биективно. Графы с плоскими эмуляторами, как и с плоскими покрытиями, замкнуты относительно миноров и преобразований Y-Δ. В 1988 году, независимо от Негами, Феллоуз предположил, что графы с планарными эмуляторами — это именно те графы, которые можно встроить в проективную плоскость. Гипотеза верна для регулярных эмуляторов, исходя из автоморфизмов основного графа покрытия, в силу результата, аналогичного результату Негами (1988) для регулярных плоских покрытий. Однако некоторые из 32 связных запрещенных миноров проективно-планарных графов имеют планарные эмуляторы. Следовательно, гипотеза Феллоуза неверна. Нахождение полного набора запрещенных миноров для существования планарных эмуляторов остается открытой проблемой.

Ссылки

Вторичные источники о гипотезе Негами

• Хлинены, Петр (2010), «20 лет гипотезы Негами о плоском накрытии» (PDF) , Graphs and Combinatorics , 26 (4): 525–536, doi : 10.1007/s00373-010-0934-9 , MR   2669457 , S2CID   121645 . Номера страниц в примечаниях относятся к препринтной версии.
• Хунеке, Джон Филип (1993), «Гипотеза в топологической теории графов», Теория структуры графов (Сиэтл, Вашингтон, 1991) , Contemporary Mathematics, vol. 147, Провиденс, Род-Айленд: Американское математическое общество, стр. 387–389, doi : 10.1090/conm/147/01186 , MR   1224718 .

Первоисточники о плоских покрытиях

• Архидьякон, Дэн (2002), «Два графа без плоских покрытий», Journal of Graph Theory , 41 (4): 318–326, doi : 10.1002/jgt.10075 , MR   1936947 .
• Архидиакон Дэн ; Рихтер, Р. Брюс (1990), «О четности плоских покрытий» , Журнал теории графов , 14 (2): 199–204, doi : 10.1002/jgt.3190140208 , MR   1053603 .
• Чимани, Маркус; Дерка, Мартин; Хлинень, Питер; Клусачек, Матей (2013), «Как не характеризовать планарно-эмулируемые графы», Успехи в прикладной математике , 50 (1): 46–68, arXiv : 1107.0176 , doi : 10.1016/j.aam.2012.06.004 , MR   2996383 .
• Хлиненый, Петр (1998), « K _4,4 − e не имеет конечного плоского покрытия», Journal of Graph Theory , 27 (1): 51–60, doi : 10.1002/(SICI)1097-0118(199801)27: 1<51::AID-JGT8>3.3.CO;2-S , MR   1487786 .
• Инкманн, Торстен; Томас, Робин (2011), «Минор-минимальные плоские графы с четной шириной ветвей», Combinatorics, Probability and Computing , 20 (1): 73–82, arXiv : 1007.0373 , doi : 10.1017/S0963548310000283 , MR   2745678 , S2CID   9093660 .
• Китакубо, Сигэру (1991), «Плоские разветвленные покрытия графов», Yokohama Mathematical Journal , 38 (2): 113–120, MR   1105068 .
• Негами, Сейя (1986), «Перечисление проективно-планарных вложений графов», Discrete Mathematics , 62 (3): 299–306, doi : 10.1016/0012-365X(86)90217-7 , MR   0866945 .
• Негами, Сейя (1988), «Сферический род и практически плоские графы», Discrete Mathematics , 70 (2): 159–168, doi : 10.1016/0012-365X(88)90090-8 , MR   0949775 .
• Негами, Сейя (2003), «Композитные плоские покрытия графов», Discrete Mathematics , 268 (1–3): 207–216, doi : 10.1016/S0012-365X(02)00689-1 , MR   1983279 .
• Рик, Йоав; Ямашита, Ясуши (2010), «Конечные плоские эмуляторы для K _4,5 - 4 K ₂ и K _1,2,2,2 и гипотеза Феллоуза», European Journal of Combinatorics , 31 (3): 903–907, arXiv : 0812.3700 , дои : 10.1016/j.ejc.2009.06.003 , MR   2587038 , S2CID   36777608 .

Дополнительная литература

• Архидьякон, Дэн (1981), «Теорема Куратовского для проективной плоскости» , Журнал теории графов , 5 (3): 243–246, doi : 10.1002/jgt.3190050305 , MR   0625065
• Стипендиаты, Майкл Р. (1985), Кодирование графов в графах , доктор философии. диссертация, ун. Калифорнии, Сан-Диего .
• Товарищи, Майкл Р .; Коблиц, Нил (1992), «Самоочевидная сложность полиномиального времени и простая факторизация», Designs, Codes and Cryptography , 2 (3): 231–235, doi : 10.1007/BF00141967 , MR   1181730 , S2CID   3976355 .
• Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1988), «Неконструктивные инструменты для доказательства разрешимости за полиномиальное время», Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491 , S2CID   16587284 .
• Гловер, Генри Х.; Хунеке, Джон П.; Ван, Чин Сан (1979), «103 графа, неприводимых для проективной плоскости», Журнал комбинаторной теории , серия B, 27 (3): 332–370, doi : 10.1016/0095-8956(79)90022-4 , МР   0554298 .
• Робертсон, Нил ; Сеймур, Пол (1995), «Незначительные графы. XIII. Проблема непересекающихся путей», Журнал комбинаторной теории , серия B, 63 (1): 65–110, doi : 10.1006/jctb.1995.1006 .
• Робертсон, Нил ; Сеймур, Пол (2004), «Незначительные графы. XX. Гипотеза Вагнера», Журнал комбинаторной теории , серия B, 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001 .
• Зелинка, Богдан (1982), «О двойных покрытиях графов» , Mathematica Slovaca , 32 (1): 49–54, MR   0648219 .