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

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

Двойное покрытие циклами графа Петерсена , соответствующее его вложению в проективную плоскость в виде полудодекаэдра .

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Szekeres, G. Polyhedral decomposition of cubic graphs (неопр.) // Bulletin of the Australian Mathematical Society. — 1973. — Т. 8 , № 03 . — С. 367—387 . — doi : .
Seymour, P. D. Disjoint paths in graphs (неопр.) // Discrete Mathematics. — 1980. — Т. 29 , № 3 . — С. 293—309 . — doi : .
Jaeger, F. A survey of the cycle double cover conjecture (неопр.) // Annals of Discrete Mathematics. — 1985. — Т. 27 . — С. 1—12 . — doi : .
Fleischner, Herbert. Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen (нем.) // (англ.) ( : magazin. — 1976. — Bd. 81 , Nr. 4 . — S. 267—278 . — ISSN . — doi : .
Huck, A. Reducible configurations for the cycle double cover conjecture (англ.) // (англ.) ( : journal. — 2000. — Vol. 99 , no. 1—3 . — P. 71—90 . — doi : .
Kochol, Martin. Snarks without small cycles (англ.) // Journal of Combinatorial Theory, Series B : journal. — 1996. — Vol. 67 , no. 1 . — P. 34—47 . — doi : .

Литература

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 : .
Zhang, Cun-Quan. (неопр.) . — 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 .