Двойное покрытие циклами

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Kochol, Martin. Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani (англ.) : journal. — 2009a. — Vol. 5417. — P. 319—323.
• Kochol, Martin. Polyhedral embeddings of snarks in orientable surfaces (англ.) // Proceedings of the American Mathematical Society : journal. — 2009b. — Vol. 137, no. 05. — P. 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.

Эта страница в последний раз была отредактирована 24 мая 2021 в 22:08.