Русская Википедия:Планарное накрытие

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Covering-graph-4.svg
Граф C является планарным накрытием графа H. Накрывающее отображение показано цветом вершин.

Планарное накрытие конечного графа G — это конечный накрывающий граф графа G, являющийся планарным графом. Любой граф, который может быть вложен в проективную плоскость, имеет планарное накрытие. Нерешённая гипотеза Сэйи Негами утверждает, что только эти графы и имеют планарные накрытияШаблон:Sfn.

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

Определение

Накрывающее отображение из одного графа C в другой граф H может быть описано функцией f из вершин C в вершины H, которая для каждой вершины v из C создаёт биекцию между окрестностью v и окрестностью f(v)Шаблон:Sfn. Если H является связным графом, каждая вершина H должна иметь одно и то же число вершин в прообразе CШаблон:Sfn. Это число называется числом слоёв отображения, а C называется накрывающим графом графа G. Если и C, и H конечны, а C является планарным графом, C называется планарным накрытием графа H.

Примеры

Файл:Dodecahedron.png
Отождествление пар противоположных вершин правильного двенадцатигранника даёт накрывающее отображение в графа Петерсена

Граф правильного двенадцатигранника имеет симметрию, которая отображает каждую вершину в антиподальную вершину. Набор антиподальных пар вершин и их смежностей можно рассматривать также как граф, граф Петерсена. Двенадцатигранник образует планарное накрытие этого непланарного графа[1]. Этот пример показывает, что не любой граф с планарным накрытием сам является планарным. Когда планарный граф накрывает непланарный, число слоёв должно быть чётнымШаблон:SfnШаблон:Sfn.

Файл:Dodecagonal prism.png
Шаблон:Не переведено 5 может образовать 2-слойное накрытие шестиугольной призмы, 3-слойное накрытие куба, или 4-слойное накрытие треугольной призмы.

Граф k-угольной призмы имеет 2k вершин и является планарным с двумя k-угольными гранями и k квадратными гранями. Если k = ab, <math>a \geqslant 2</math> и <math>b \geqslant 3</math>, то граф имеет a-слойное накрывающее отображение в b-стороннюю призму, в которой две вершины k-призмы отображаются в одну и ту же вершину b-призмы, если они обе принадлежат одной и той же k-угольной грани и расстояние от одной до другой кратно b. Например, Шаблон:Не переведено 5 может образовать 2-слойное накрытие шестиугольной призмы, 3-слойное накрытие куба или 4-слойное накрытие треугольной призмы. Эти примеры показывают, что граф может иметь много различных планарных накрытий, и могут быть планарным накрытием для многих графов. Кроме того, эти примеры показывают, что слой планарного накрытия может быть произвольно большим. Они не только накрывают призмы, например, шестиугольная призма может также накрывать непланарный коммунальный граф K3,3 путём отождествления антиподальных пар вершинШаблон:Sfn.

Сохраняющие накрытие операции

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

Поскольку графы с планарными накрытиями замкнуты относительно операции взятия миноров, из теоремы Робертсона — Сеймура следует, что их можно описать конечным набором запрещённых миноровШаблон:Sfn. Граф является запрещённым минором для этого свойства, если он не имеет планарного накрытия, но все его миноры имеют планарные накрытия. Это описание может быть использовано для доказательства существования алгоритма полиномиального времени, который проверяет существование планарного накрытия путём поиска каждого запрещённого минора и возвращает «планарное накрытие существует», если этот поиск не найдёт ни одного из нихШаблон:Sfn. Однако, поскольку точный набор запрещённых миноров для этого свойства не известен, это доказательство существования не конструктивно и не ведёт к явному описанию множества запрещённых миноров или алгоритму, основанному на них[2]

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

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

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

Шаблон:Unsolved Если граф H имеет вложение в проективную плоскость, то оно обязательно имеет планарное накрытие, заданное прообразом H в Шаблон:Не переведено 5 проективной плоскости, что есть сфера. НегамиШаблон:Sfn доказал обратное, что если связный граф H имеет двуслойное планарное накрытие, то H должен иметь вложение в проективную плоскостьШаблон:SfnШаблон:Sfn. Предположение, что H связан здесь необходимо, поскольку дизъюнктное объединение проективно планарных графов может не быть проективно-планарным[3], но остаются имеющими планарное накрытие, дизъюнктное объединение ориентируемых двойных накрытий.

Регулярное накрытие графа H — это накрытие, получающееся из группы симметрий его накрывающего графа — прообразы каждой вершины из H составляют орбиту группы. НегамиШаблон:Sfn доказал, что любой связный граф с планарным регулярным накрытием может быть вложен в проективную плоскостьШаблон:SfnШаблон:Sfn. Основываясь на этих двух результатах, он высказал гипотезу, что на самом деле любой связный граф с планарным накрытием является проективнымШаблон:SfnШаблон:Sfn. На 2013 год гипотеза оставалась нерешённой Шаблон:Sfn. Она известна также как «<math>1-2-\infty</math> гипотеза Негами», поскольку её можно переформулировать как утверждение, что минимум слоёв планарного накрытия, если такое существует, должно быть либо 1, либо 2Шаблон:Sfn.

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

Подобно графам с планарными накрытиями графы с вложениями в проективную плоскость могут быть описаны запрещёнными минорами. В этом случае точное множество запрещённых миноров известно, их 35. 32 из них связны и один из этих 32 графов обязательно появляется в качестве минора в любом связном непроективном планарном графеШаблон:Sfn[4]. Когда Негами высказал свою гипотезу, было доказано, что 31 из этих 32 запрещённых миноров либо не имеют планарных накрытий, либо могут быть сведены с помощью преобразования звезда-треугольник к более простым графам из этого спискаШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn Шаблон:Sfn. Единственный оставшийся граф, для которого это ещё не сделано, это K1,2,2,2, верхушечный граф с семью вершинами, который образует остов четырёхмерной Шаблон:Не переведено 5. Если показать, что K1,2,2,2 не имеет планарных накрытий, это будет полным доказательством гипотезы. С другой стороны, если гипотеза не верна, K1,2,2,2 будет минимальным контрпримеромШаблон:Sfn.

Связанная гипотеза Майкла Феллоуза, уже решённая, касается планарных эмуляторов, обобщения планарных накрытий, когда отображаются окрестности графа сюръективно, а не биективноШаблон:SfnШаблон:SfnШаблон:Sfn. Графы с планарными эмуляторами, подобно графам с планарными накрытиями, замкнуты относительно миноров и преобразований звезда-треугольник Шаблон:Sfn[5] В 1988 году независимо от Негами Феллоуз высказал гипотезу, что графы с планарными эмуляторами, это в точности графы, которые можно вложить в проективную плоскостьШаблон:Sfn. Гипотеза верна для регулярных эмуляторов, происходящих их автоморфизмов низлежащего накрывающего графа аналогично результату Негами Шаблон:Sfn для регулярных планарных накрытийШаблон:Sfn. Однако оказалось, что некоторые из 32 связных запрещённых миноров для проективно планарных графов имеют планарные эмуляторыШаблон:SfnШаблон:SfnШаблон:Sfn. Поэтому гипотеза Феллоуза не верна. Нахождение полного набора запрещённых миноров для существования планарных эмуляторов остаётся открытой проблемойШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

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

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

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

Шаблон:Refend Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvtxt: «Это построение проиллюстрировано на рисунке 1, где двенадцатигранник показан как планарное двойное накрытие графа Петерсена.»
  2. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt. Неконструктивность алгоритмической проверки существования k-кратных планарных накрытий показали в качестве примера Феллоуз и Коблиц.
  3. ↑ Например, два графа Куратовского проективно планарны, любое объединение двух из них таковым не является Шаблон:Harv.
  4. ↑ Список запрещённых проективно планарных миноров можно найти в статье Шаблон:Harvtxt. Негами Шаблон:Harvtxt утверждал соответствующее наблюдение для 103 неприводимых непроективных планарных графов из статьи Шаблон:Harvtxt.
  5. ↑ Глиненый приписывает этот факт Феллоузу и пишет, что его доказательство не тривиально
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Планарное_накрытие&oldid=10598474