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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

↑ Szekeres, G. Polyhedral decomposition of cubic graphs (неопр.) // Bulletin of the Australian Mathematical Society. — 1973. — Т. 8, № 03. — С. 367—387. — doi:10.1017/S0004972700042660.
↑ Seymour, P. D. Disjoint paths in graphs (неопр.) // Discrete Mathematics. — 1980. — Т. 29, № 3. — С. 293—309. — doi:10.1016/0012-365X(80)90158-2.
↑ Jaeger, F. A survey of the cycle double cover conjecture (неопр.) // Annals of Discrete Mathematics. — 1985. — Т. 27. — С. 1—12. — doi:10.1016/S0304-0208(08)72993-1.
↑ Fleischner, Herbert. Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen (нем.) // Monatshefte für Mathematik^[англ.] : magazin. — 1976. — Bd. 81, Nr. 4. — S. 267—278. — ISSN 1436-5081/e 0026-9255; 1436-5081/e. — doi:10.1007/BF01387754.
↑ Huck, A. Reducible configurations for the cycle double cover conjecture (англ.) // Discrete Applied Mathematics^[англ.] : journal. — 2000. — Vol. 99, no. 1—3. — P. 71—90. — doi:10.1016/S0166-218X(99)00126-2.
↑ Kochol, Martin. Snarks without small cycles (англ.) // Journal of Combinatorial Theory, Series B : journal. — 1996. — Vol. 67, no. 1. — P. 34—47. — doi:10.1006/jctb.1996.0032.

Литература

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.

[1] Szekeres, G. Polyhedral decomposition of cubic graphs (неопр.) // Bulletin of the Australian Mathematical Society. — 1973. — Т. 8, № 03. — С. 367—387. — doi:10.1017/S0004972700042660.

[2] Seymour, P. D. Disjoint paths in graphs (неопр.) // Discrete Mathematics. — 1980. — Т. 29, № 3. — С. 293—309. — doi:10.1016/0012-365X(80)90158-2.

[3] Jaeger, F. A survey of the cycle double cover conjecture (неопр.) // Annals of Discrete Mathematics. — 1985. — Т. 27. — С. 1—12. — doi:10.1016/S0304-0208(08)72993-1.

[4] Fleischner, Herbert. Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen (нем.) // Monatshefte für Mathematik^[англ.] : magazin. — 1976. — Bd. 81, Nr. 4. — S. 267—278. — ISSN 1436-5081/e 0026-9255; 1436-5081/e. — doi:10.1007/BF01387754.

[5] Huck, A. Reducible configurations for the cycle double cover conjecture (англ.) // Discrete Applied Mathematics^[англ.] : journal. — 2000. — Vol. 99, no. 1—3. — P. 71—90. — doi:10.1016/S0166-218X(99)00126-2.

[6] Kochol, Martin. Snarks without small cycles (англ.) // Journal of Combinatorial Theory, Series B : journal. — 1996. — Vol. 67, no. 1. — P. 34—47. — doi:10.1006/jctb.1996.0032.

[1]

[2]

[3]

[4]

[5]

[6]