WikiSort.ru - Не сортированное

Нерешённые проблемы математики: Для любого ли графа без мостов существует мультимножество простых циклов, покрывающих каждое ребро графа в точности два раза?

Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.

Дьёрдь Секереш^[1] и Пол Сеймур (англ. Paul Seymour)^[2] выдвинули гипотезу о двойном покрытии циклами, согласно которой для любого графа без мостов существует двойное покрытие циклами. Эту гипотезу можно эквивалентно переформулировать в терминах вложений графов, и в этой области она также известна как гипотеза о круговом вложении (англ. circular embedding conjecture или strong embedding conjecture). По состоянию на 2016 год гипотеза не доказана.

Формулировка

Обычно гипотезу формулируют следующим образом: верно ли, что в любом графе без мостов есть набор простых циклов, для которого каждое ребро содержится ровно в двух циклах этого набора? Требование отсутствия в графе мостов является необходимым, поскольку никакой из мостов не может принадлежать какому-либо из циклов. Набор циклов, который удовлетворяет условию гипотезы, называется двойным покрытием циклами. Некоторые графы, типа циклических или кактусов, могут быть покрыты только с повторным использованием некоторых циклов, поэтому такого рода повторения циклов разрешены в двойном покрытии циклами.

Сведение к снаркам

У снарка (кубического графа без мостов, в котором рёбра нельзя покрасить в три цвета так, чтобы два ребра одного цвета не сходились в одной вершине) по теореме Визинга будет хроматический индекс 4. Снарки являются самыми сложными графами для двойного покрытия циклами: если гипотеза справедлива для снарков, то она будет верна для всех графов без мостов^[3].

Действительно: если в графе есть вершина степени 1, то её ребро образует мост. Если есть вершина степени 2, то можно выкинуть эту вершину из графа, а её ребра объединить в одно. Если допустить, что в графе есть вершина ${\displaystyle v}$ степени 4 или больше, тогда можно^[4] найти два таких ребра ${\displaystyle e_{1}}$ и ${\displaystyle e_{1}}$ , смежных с этой вершиной, что их можно удалить, а вместо них добавить ребро, соединяющее концы этих рёбер, отличные от ${\displaystyle v}$ , сохранив при этом свойство, что в графе нет мостов. Из двойного покрытия нового графа легко получить двойное покрытие для старого графа.

Если у кубического графа при этом хроматический индекс 3, то легко строится двойное покрытие циклами: в первый цикл попадают все рёбра первого и второго цвета, во второй цикл — все рёбра первого и третьего цвета, а в третий цикл — все рёбра второго и третьего цвета.

Сводимые конфигурации

На сегодняшний день было предложено несколько подходов к решению гипотезы. Один из таких подходов заключается в том, что мы покажем, что не существует минимального контрпримера, а именно, будем искать сводимые конфигурации в каждом графе. Сводимая конфигурация — это подграф, который можно заменить меньшим подграфом так, что мы сохраним свойство наличия или отсутствия двойного покрытия циклами (подобный подход был с успехом применён в доказательстве теоремы о четырёх красках). Например, если в графе найдётся треугольник (три вершины, соединённые друг с другом), то мы сможем провести преобразование треугольник-звезда, тем самым уменьшив число вершин на 2; при этом любое двойное покрытие циклами меньшего графа преобразуется в покрытие для изначального большего графа. Таким образом, в минимальном контрпримере к гипотезе мы не сможем обнаружить подграф в виде треугольника. Также, например, с помощью компьютера было показано, что в минимальном контрпримере (который будет кубическим графом) не может быть цикла длиной 11 или меньше, то есть обхват такого графа будет как минимум 12.^[5]

К сожалению, в отличие от вышеупомянутой теоремы о четырёх красках, для гипотезы о двойном покрытии циклами не существует конечного набора сводимых конфигураций. Например, в каждой сводимой конфигурации найдётся какой-нибудь цикл, поэтому для любого конечного набора сводимых конфигураций найдётся такое число γ, что в любой конфигурации есть цикл длиной меньшей γ. Но известно, что существуют снарки с произвольно высоким обхватом (длиной минимального цикла).^[6] Такой снарк не получится уменьшить, так как ни одна из конфигураций в нём не содержится, и наша стратегия будет неприменима к данному примеру.

Гипотеза о цепном вложении

Этот раздел статьи ещё не написан. Согласно замыслу одного или нескольких участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел. Эта отметка установлена 30 ноября 2016 года.

Примечания

Литература

• Kochol, Martin (2009a). “Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani”. Lecture Notes in Computer Science. 5417: 319—323. Параметр |contribution= пропущен (справка на английском)
• Kochol, Martin (2009b). “Polyhedral embeddings of snarks in orientable surfaces”. Proceedings of the American Mathematical Society (5 ed.). 137 (05): 1613—1619. DOI:10.1090/S0002-9939-08-09698-6.
• Zhang, Cun-Quan. Integer Flows and Cycle Covers of Graphs. — CRC Press, 1997. — ISBN 978-0-8247-9790-4.
• Zhang, Cun-Quan. Circuit Double Cover of Graphs. — Cambridge University Press, 2012. — ISBN 978-0-5212-8235-2.

Ссылки

• Cycle double cover conjecture, circular embedding conjecture, и Grünbaum’s conjecture, с сайта Open Problem Garden.
• The Cycle Double Cover Conjecture, Dan Archdeacon.
• Weisstein, Eric W. Cycle Double Cover Conjecture (англ.) на сайте Wolfram MathWorld.