Плоское покрытие - Planar cover

График C плоское покрытие графа ЧАС. Покрывающая карта обозначается цветами вершин.

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

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

Определение

А карта покрытия из одного графика C к другому графику ЧАС может быть описан функцией ж из вершин C на вершины ЧАС что для каждой вершины v из C, дает биекция между соседи из v и соседи ж(v).[3] Если ЧАС это связный граф, каждая вершина ЧАС должно иметь такое же количество предварительных изображений в C;[2] это число называется слой карты, и C называется покрывающий граф из грамм. Если C и ЧАС оба конечны, и C это планарный граф, тогда C называется плоским покрытием ЧАС.

Примеры

Выявление пар противоположных вершин додекаэдр дает карту покрытия Граф Петерсена

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

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

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

Покровосохраняющие операции

Если график ЧАС имеет плоское покрытие, как и все граф минор из ЧАС.[2] Несовершеннолетний грамм из ЧАС может быть сформирован путем удаления ребер и вершин из ЧАС, и за счет стягивания краев ЧАС. Граф покрытия C могут быть преобразованы таким же образом: для каждого удаленного ребра или вершины в ЧАС, удалите его прообраз в C, и для каждого сжатого ребра или вершины в ЧАС, сократите его прообраз в C. Результат применения этих операций к C является несовершеннолетним из C это покрывает грамм. Поскольку каждый минор планарного графа сам по себе является плоским, это дает плоское покрытие минорного графа. грамм.

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

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

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

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

Вопрос, Web Fundamentals.svgНерешенная проблема в математике:
Всякий ли связный граф с плоским покрытием имеет вложение в проективную плоскость?
(больше нерешенных задач по математике)

Если график ЧАС имеет встраивание в проективная плоскость, то он обязательно имеет плоское покрытие, заданное прообразом ЧАС в ориентируемая двойная крышка проективной плоскости, которая является сферой.Негами (1986) доказано, наоборот, что если связный граф ЧАС имеет двухслойное плоское покрытие, тогда ЧАС должен иметь вложение в проективную плоскость.[10] Предположение, что ЧАС здесь необходимо, потому что несвязное объединение проективно-планарных графов само не может быть проективно-планарным.[11] но все же будет иметь плоское покрытие - несвязное объединение ориентируемых двойных покрытий.

А обычное покрытие графа ЧАС это тот, который исходит из группа симметрий его покрывающего графа: прообразы каждой вершины в ЧАС являются орбита группы. Негами (1988) доказал, что любой связный граф с плоским регулярным покрытием вкладывается в проективную плоскость.[12] Основываясь на этих двух результатах, он предположил, что на самом деле каждый связный граф с плоским покрытием проективен.[13]По состоянию на 2013 год эта гипотеза остается нерешенной.[14] Она также известна как «гипотеза 1-2-∞» Негами, потому что ее можно переформулировать как утверждающую, что минимальный слой плоского покрытия, если он существует, должен быть либо 1, либо 2.[15]

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

Как и графы с планарными покрытиями, графы с вложениями проективных плоскостей могут быть охарактеризованы запрещенными минорами. При этом известен точный набор запрещенных несовершеннолетних: их 35. 32 из них связаны, и один из этих 32 графов обязательно появляется как минор в любом связном непроективно-планарном графе.[16] Поскольку Негами высказал свою гипотезу, было доказано, что 31 из этих 32 запрещенных миноров либо не имеют плоских покрытий, либо могут быть уменьшены с помощью Y-Δ преобразований до более простого графа из этого списка.[17] Один оставшийся график, для которого это еще не было сделано, это K1,2,2,2, семивершина вершина графика образующий каркас четырехмерного восьмигранная пирамида. Если K1,2,2,2 можно было бы показать, что у него нет плоских покрытий, это завершит доказательство гипотезы. С другой стороны, если гипотеза неверна, K1,2,2,2 обязательно будет его наименьшим контрпримером.[18]

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

Примечания

  1. ^ Глинены (2010), п. 1
  2. ^ а б c d Глинены (2010), Предложение 1, с. 2
  3. ^ Глинены (2010), Определение, стр. 2
  4. ^ Инкманн и Томас (2011): «Эта конструкция проиллюстрирована на рисунке 1, где додекаэдр показан как плоское двойное покрытие графа Петерсена».
  5. ^ Архидьякон и Рихтер (1990); Негами (2003).
  6. ^ Зелинка (1982)
  7. ^ Робертсон и Сеймур (2004)
  8. ^ Робертсон и Сеймур (1995)
  9. ^ Товарищи и Лэнгстон (1988); Товарищи и Коблиц (1992). Неконструктивность алгоритмической проверки существования k-кратные плоские накрытия явно приведены в качестве примера Феллоузом и Коблицем.
  10. ^ Негами (1986); Глинены (2010), Теорема 2, с. 2
  11. ^ Например, два Графики Куратовского являются проективно-планарными, но любое объединение двух из них не является (Архидиакон 1981 г. ).
  12. ^ Негами (1988); Глинены (2010), Теорема 3, с. 3
  13. ^ Негами (1988); Глинены (2010), Гипотеза 4, с. 4
  14. ^ Chimani et al. (2013)
  15. ^ Хунеке (1993)
  16. ^ Глинены (2010), п. 4; список запрещенных проективно-планарных миноров из Архидьякон (1981). Негами (1988) вместо этого сформулировал соответствующее наблюдение для 103 неприводимых непроективно-планарных графов, заданных формулой Гловер, Хунеке и Ван (1979).
  17. ^ Негами (1988); Хунеке (1993); Глинены (1998); Архидьякон (2002); Глинены (2010), стр. 4–6
  18. ^ Глинены (2010), стр. 6–9
  19. ^ Товарищи (1985); Китакубо (1991); Глинены (2010), Определение, стр. 9
  20. ^ Глинены (2010), Предложение 13, с. 9. Глинени приписывает это Fellows и пишет, что его доказательство нетривиально.
  21. ^ Глинены (2010), Гипотеза 14, с. 9
  22. ^ Китакубо (1991).
  23. ^ Глинены (2010), стр. 9–10; Рик и Ямасита (2010); Chimani et al. (2013)
  24. ^ Глинены (2010), п. 10

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

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

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

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

Вспомогательная литература