В теоретико-графовой математике циклическое двойное покрытие — это набор циклов в неориентированном графе , которые вместе включают каждое ребро графа ровно дважды. Например, для любого полиэдрального графа грани выпуклого многогранника , представляющего граф, обеспечивают двойное покрытие графа: каждое ребро принадлежит ровно двум граням.
Это нерешенная проблема , поставленная У. Т. Туттом , [1] Итаи и Родехом, [2] Джорджем Секерешем [3] и Полом Сеймуром [4] и известная как гипотеза о двойном покрытии цикла , имеет ли каждый граф без мостов двойное покрытие цикла. Гипотеза может быть эквивалентно сформулирована в терминах вложений графов , и в этом контексте также известна как гипотеза о круговом вложении .
Обычная формулировка гипотезы о двойном покрытии цикла спрашивает, имеет ли каждый неориентированный граф без мостов набор циклов, такой что каждое ребро графа содержится ровно в двух циклах. Требование, чтобы граф был без мостов, является очевидным необходимым условием для существования такого набора циклов, поскольку мост не может принадлежать ни одному циклу. Набор циклов, удовлетворяющий условию гипотезы о двойном покрытии цикла, называется двойным покрытием цикла . Некоторые графы, такие как графы циклов и графы кактусов без мостов , могут быть покрыты только путем использования одного и того же цикла более одного раза, поэтому такой вид дублирования допускается в двойном покрытии цикла.
Снарк — это особый случай графа без мостов, обладающий дополнительными свойствами, что каждая вершина имеет ровно три инцидентных ребра (то есть граф является кубическим ) и что невозможно разбить ребра графа на три совершенных паросочетания (то есть граф не имеет 3- реберной раскраски и по теореме Визинга имеет хроматический индекс 4). Оказывается, что снарк образует единственный сложный случай гипотезы о двойном покрытии цикла: если гипотеза верна для снарксов, то она верна для любого графа. [5]
Jaeger (1985) замечает, что в любом потенциальном минимальном контрпримере к гипотезе о двойном покрытии цикла все вершины должны иметь три или более инцидентных ребер. Так как вершина с инцидентным только одним ребром образует мост, в то время как если вершине инцидентны два ребра, их можно сжать, чтобы сформировать меньший граф таким образом, что любое двойное покрытие меньшего графа будет расширяться до одного из исходного графа. С другой стороны, если вершина v имеет четыре или более инцидентных ребер, можно «отделить» два из этих ребер, удалив их из графа и заменив их одним ребром, соединяющим две их другие конечные точки, при этом сохраняя отсутствие мостов в результирующем графе. Опять же, двойное покрытие результирующего графа может быть расширено простым способом до двойного покрытия исходного графа: каждый цикл отщепленного графа соответствует либо циклу исходного графа, либо паре циклов, встречающихся в v . Таким образом, каждый минимальный контрпример должен быть кубическим. Но если кубический граф может иметь свои ребра, раскрашенные в 3 цвета (скажем, в красный, синий и зеленый), то подграф красных и синих ребер, подграф синих и зеленых ребер и подграф красных и зеленых ребер каждый образует набор непересекающихся циклов, которые вместе покрывают все ребра графа дважды. Следовательно, каждый минимальный контрпример должен быть не-3-ребровым-раскрашиваемым безмостиковым кубическим графом, то есть снарком. [5]
Одной из возможных атак на проблему двойного покрытия цикла было бы показать, что не может существовать минимального контрпримера, доказав, что любой граф содержит приводимую конфигурацию , подграф, который может быть заменен меньшим подграфом таким образом, чтобы сохранить существование или несуществование двойного покрытия цикла. Например, если кубический граф содержит треугольник, преобразование Δ-Y заменит треугольник одной вершиной; любое двойное покрытие цикла меньшего графа может быть расширено обратно до двойного покрытия цикла исходного кубического графа. Следовательно, минимальный контрпример к гипотезе двойного покрытия цикла должен быть графом без треугольников , исключая некоторые снарки, такие как граф Титце , который содержит треугольники. Благодаря компьютерным поискам известно, что каждый цикл длиной 11 или меньше в кубическом графе образует приводимую конфигурацию, и, следовательно, любой минимальный контрпример к гипотезе двойного покрытия цикла должен иметь обхват не менее 12. [6]
К сожалению, невозможно доказать гипотезу о двойном покрытии цикла, используя конечный набор приводимых конфигураций. Каждая приводимая конфигурация содержит цикл, поэтому для каждого конечного набора S приводимых конфигураций существует число γ такое, что все конфигурации в наборе содержат цикл длины не более γ. Однако существуют снарки с произвольно большим обхватом, то есть с произвольно высокими границами длины их кратчайшего цикла. [7] Снарки G с обхватом больше γ не могут содержать ни одну из конфигураций в наборе S , поэтому сокращения в S недостаточно сильны, чтобы исключить возможность того, что G может быть минимальным контрпримером.
Если граф имеет циклическое двойное покрытие, циклы покрытия можно использовать для формирования 2-клеток графа, вложенного в двумерный клеточный комплекс . В случае кубического графа этот комплекс всегда образует многообразие . Говорят, что граф циклически вложен в многообразие, в том смысле, что каждая грань вложения является простым циклом в графе. Однако циклическое двойное покрытие графа со степенью больше трех может не соответствовать вложению в многообразие: клеточный комплекс, образованный циклами покрытия, может иметь не многообразную топологию в своих вершинах. Гипотеза о круговом вложении или сильная гипотеза о вложении [5] утверждает, что каждый 2-вершинно-связный граф имеет круговое вложение в многообразие. Если это так, то граф также имеет циклическое двойное покрытие, образованное гранями вложения.
Для кубических графов 2-вершинная связность и отсутствие мостов эквивалентны. Поэтому гипотеза о круговом вложении, очевидно, по крайней мере столь же сильна, как гипотеза о двойном покрытии цикла. [5]
Если круговое вложение существует, оно может не находиться на поверхности минимального рода: Нгуен Хюи Сыонг описал тороидальный граф с двумя вершинами, ни одно из круговых вложений которого не лежит на торе. [5]
Более сильная версия гипотезы о круговом вложении, которая также рассматривалась, — это гипотеза о том, что каждый граф с 2 вершинами имеет круговое вложение на ориентируемом многообразии . В терминах гипотезы о двойном покрытии циклов это эквивалентно гипотезе о том, что существует двойное покрытие циклов и ориентация для каждого из циклов в покрытии, такая, что для каждого ребра e два цикла, которые покрывают e, ориентированы в противоположных направлениях относительно e . [5]
В качестве альтернативы также рассматривались усиления гипотезы, включающие раскраски циклов в покрытии. Наиболее сильной из них является гипотеза о том, что каждый граф без мостов имеет круговое вложение на ориентируемом многообразии, в котором грани могут быть раскрашены в 5 цветов. Если это правда, это будет означать гипотезу В. Т. Тутта о том, что каждый граф без мостов имеет нигде не нулевой 5-поток . [5]
Более сильным типом вложения, чем круговое вложение, является полиэдральное вложение , вложение графа на поверхности таким образом, что каждая грань является простым циклом, а каждые две грани, которые пересекаются, делают это либо по одной вершине, либо по одному ребру. (В случае кубического графа это можно упростить до требования, чтобы каждые две грани, которые пересекаются, делали это по одному ребру.) Таким образом, ввиду сведения гипотезы о двойном покрытии цикла к снаркам, интересно исследовать полиэдральные вложения снарков. Не сумев найти такие вложения, Бранко Грюнбаум предположил, что их не существует, но Кохоль (2009a, 2009b) опроверг гипотезу Грюнбаума, найдя снарка с полиэдральным вложением.
{{citation}}: CS1 maint: дата и год ( ссылка ).{{citation}}: CS1 maint: дата и год ( ссылка ).