Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Граф С представляет собой плоскую крышку графа H . Покрывающая карта обозначена цветами вершин.

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

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

Определение [ править ]

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

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

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

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

Двенадцатиугольные призмы могут образовывать 2-слойную крышку гексагональной призмы , 3-слойную крышки кубы , или 4-слойной крышку треугольной призмы .

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

Операции по сохранению покровов [ править ]

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

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

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

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

Гипотеза Негами [ править ]

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

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

(больше нерешенных задач по математике)

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

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

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

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

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

Заметки [ править ]

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

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

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

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

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

  • Архидиакон, Dan (2002), "Две графы без плоских покрытий", Журнал теории графов , 41 (4): 318-326, DOI : 10.1002 / jgt.10075 , MR  1936947 CS1 maint: обескураженный параметр ( ссылка ).
  • Архидиакон, Дан ; Рихтер, Р. Брюс (1990), "О четности плоских покрытий" , Журнал теории графов , 14 (2): 199-204, DOI : 10.1002 / jgt.3190140208 , МР  1053603.
  • Чимани, Маркус; Дерка, Мартин; Глинены, Петр; Клусачек, Матей (2013), «Как не характеризовать плоско-эмулируемые графы», Успехи в прикладной математике , 50 (1): 46–68, arXiv : 1107.0176 , doi : 10.1016 / j.aam.2012.06.004 , MR  2996383.
  • Глинены, Петр (1998), « K 4,4  -  e не имеет конечного плоского покрытия», Журнал теории графов , 27 (1): 51–60, DOI : 10.1002 / (SICI) 1097-0118 (199801) 27: 1 <51 :: AID-JGT8> 3.3.CO; 2-S , MR  1487786.
  • Инкманн, Торстен; Томас, Робин (2011), «Минор-минимальные плоские графы четной ширины ветвления», Комбинаторика, вероятность и вычисления , 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), "Перечень проекционно-плоских вложений графов", дискретная математика , 62 (3): 299-306, DOI : 10.1016 / 0012-365X (86) 90217-7 , МР  0866945.
  • Негами, Сейя (1988), «Сферический род и практически плоские графы», Дискретная математика , 70 (2): 159–168, DOI : 10.1016 / 0012-365X (88) 90090-8 , MR  0949775.
  • Негами, Seiya (2003), "Композиционные плоские покрытия графов", Дискретная математика , 268 (1-3): 207-216, DOI : 10.1016 / S0012-365X (02) 00689-1 , MR  1983279.
  • Рик, Йоав; Ямасита, Ясуши (2010), «Конечные плоские эмуляторы для K 4,5  - 4 K 2 и K 1,2,2,2 и гипотеза стипендиатов», European Journal of Combinatorics , 31 (3): 903–907, arXiv : 0812.3700 , DOI : 10.1016 / j.ejc.2009.06.003 , МР  2587038 , S2CID  36777608.

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

  • Архидиакон, Dan (1981), "Теорема Kuratowski для проективной плоскости" , Журнал теории графов , 5 (3): 243-246, DOI : 10.1002 / jgt.3190050305 , MR  0625065
  • Стипендиаты, Майкл Р. (1985), Кодирование графов в графах , доктор философии. диссертация, Univ. Калифорнии, Сан-Диего.
  • Товарищи, Майкл Р .; Коблиц, Нил (1992), "Самостоятельно свидетелями сложности за полиномиальное время и разложение на простые множители", Designs, коды и криптография , 2 (3): 231-235, DOI : 10.1007 / BF00141967 , MR  1181730 , S2CID  3976355.
  • Товарищи, Майкл Р .; Langston, Майкл А. (1988), "Неконструктивные инструменты для доказательства полиномиальной разрешимости", Журнал ACM , 35 (3): 727-739, DOI : 10,1145 / 44483,44491 , S2CID  16587284.
  • Гловер, Генри H .; Huneke, John P .; Ван Чин Сан (1979), "103 граф, которые неприводимые для проективной плоскости", Журнал комбинаторной теории , серии B, 27 (3): 332-370, DOI : 10.1016 / 0095-8956 (79) 90022-4 , Руководство по ремонту  0554298.
  • Робертсон, Нил ; Seymour, Paul (1995), "Graph Несовершеннолетних 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.