Русская Википедия:Двойное покрытие циклами
Двойное покрытие циклами в теории графов — множество циклов в неориентированном графе, которое включает в себя каждое ребро ровно два раза. Например, любой полиэдральный граф образован из вершин и рёбер выпуклого многогранника, грани же при этом образуют двойное покрытие циклами: каждое ребро принадлежит ровно двум граням.
Дьёрдь Секереш[1] и Пол Сеймур[2] выдвинули гипотезу о двойном покрытии циклами, согласно которой для любого графа без мостов существует двойное покрытие циклами. Эту гипотезу можно эквивалентно переформулировать в терминах вложений графов, и в этой области она также известна как гипотеза о круговом вложении (Шаблон:Lang-en или Шаблон:Lang-en2).
Формулировка
Обычно гипотезу формулируют следующим образом: верно ли, что в любом графе без мостов есть набор простых циклов, для которого каждое ребро содержится ровно в двух циклах этого набора? Требование отсутствия в графе мостов является необходимым, поскольку никакой из мостов не может принадлежать какому-либо из циклов. Набор циклов, который удовлетворяет условию гипотезы, называется двойным покрытием циклами. Некоторые графы, типа циклических или кактусов, могут быть покрыты только с повторным использованием некоторых циклов, поэтому такого рода повторения циклов разрешены в двойном покрытии циклами.
Сведение к снаркам
У снарка (кубического графа без мостов, в котором рёбра нельзя покрасить в три цвета так, чтобы два ребра одного цвета не сходились в одной вершине) по теореме Визинга будет хроматический индекс 4. Снарки являются самыми сложными графами для двойного покрытия циклами: если гипотеза справедлива для снарков, то она будет верна для всех графов без мостов[3].
Действительно: если в графе есть вершина степени 1, то её ребро образует мост. Если есть вершина степени 2, то можно выкинуть эту вершину из графа, а её ребра объединить в одно. Если допустить, что в графе есть вершина <math>v</math> степени 4 или больше, тогда можно[4] найти два таких ребра <math>e_1</math> и <math>e_1</math>, смежных с этой вершиной, что их можно удалить, а вместо них добавить ребро, соединяющее концы этих рёбер, отличные от <math>v</math>, сохранив при этом свойство, что в графе нет мостов. Из двойного покрытия нового графа легко получить двойное покрытие для старого графа.
Если у кубического графа при этом хроматический индекс 3, то легко строится двойное покрытие циклами: в первый цикл попадают все рёбра первого и второго цвета, во второй цикл — все рёбра первого и третьего цвета, а в третий цикл — все рёбра второго и третьего цвета.
Сводимые конфигурации
На сегодняшний день было предложено несколько подходов к решению гипотезы. Один из таких подходов заключается в том, что мы покажем, что не существует минимального контрпримера, а именно, будем искать сводимые конфигурации в каждом графе. Сводимая конфигурация — это подграф, который можно заменить меньшим подграфом так, что мы сохраним свойство наличия или отсутствия двойного покрытия циклами (подобный подход был с успехом применён в доказательстве теоремы о четырёх красках). Например, если в графе найдётся треугольник (три вершины, соединённые друг с другом), то мы сможем провести преобразование треугольник-звезда, тем самым уменьшив число вершин на 2; при этом любое двойное покрытие циклами меньшего графа преобразуется в покрытие для изначального большего графа. Таким образом, в минимальном контрпримере к гипотезе мы не сможем обнаружить подграф в виде треугольника. Также, например, с помощью компьютера было показано, что в минимальном контрпримере (который будет кубическим графом) не может быть цикла длиной 11 или меньше, то есть обхват такого графа будет как минимум 12.[5]
К сожалению, в отличие от вышеупомянутой теоремы о четырёх красках, для гипотезы о двойном покрытии циклами не существует конечного набора сводимых конфигураций. Например, в каждой сводимой конфигурации найдётся какой-нибудь цикл, поэтому для любого конечного набора сводимых конфигураций найдётся такое число γ, что в любой конфигурации есть цикл длиной меньшей γ. Но известно, что существуют снарки с произвольно высоким обхватом (длиной минимального цикла).[6] Такой снарк не получится уменьшить, так как ни одна из конфигураций в нём не содержится, и наша стратегия будет неприменима к данному примеру.
Гипотеза о цепном вложении
Примечания
Литература
Ссылки
- Cycle double cover conjecture, circular embedding conjecture, и Grünbaum’s conjecture, с сайта Open Problem Garden.
- The Cycle Double Cover Conjecture, Dan Archdeacon.
- Шаблон:Mathworld
