Циклическая двойная крышка

Нерешенная задача по математике :

Есть ли в каждом графе без мостов мультимножество циклов, покрывающее каждое ребро ровно дважды?

(еще нерешенные задачи по математике)

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

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

Это нерешенная проблема, поставленная У.Т. Тутте . Иттай и Роде, Джордж Секерес и Пол Сеймур и известная как гипотеза о двойном покрытии цикла , имеет ли каждый граф без мостов двойное покрытие цикла. Гипотеза может быть эквивалентно сформулирована в терминах вложений графов , и в этом контексте она также известна как гипотеза кругового вложения .

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

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

Снижение до снарков

См. также: снарк (теория графов)

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

Джагер (1985) отмечает, что в любом потенциально минимальном контрпримере к гипотезе о двойном покрытии цикла все вершины должны иметь три или более инцидентных ребра. Ибо вершина, имеющая только одно инцидентное ребро, образует мост, а если два ребра инцидентны вершине, можно сжать их, образуя меньший граф, так что любое двойное покрытие меньшего графа продолжается до одного из исходного графа. С другой стороны, если вершина v имеет четыре или более инцидентных ребра, можно «отделить» два из этих ребер, удалив их из графа и заменив их одним ребром, соединяющим две другие конечные точки, сохраняя при этом отсутствие мостов полученный график. Опять же, двойное покрытие полученного графа может быть прямым образом расширено до двойного покрытия исходного графа: каждый цикл расщепленного графа соответствует либо циклу исходного графа, либо паре циклов, встречающихся в точках в . Таким образом, каждый минимальный контрпример должен быть кубическим. Но если кубический граф может иметь трехцветные ребра (скажем, красного, синего и зеленого цветов), то подграф красных и синих ребер, подграф синих и зеленых ребер и подграф красных и зеленых ребер каждый из них образует набор непересекающихся циклов, которые вместе дважды покрывают все ребра графа. Следовательно, каждый минимальный контрпример должен быть кубическим графом без мостов, не раскрашиваемым в 3 ребра, то есть снарком.

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

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

К сожалению, доказать гипотезу о двойном накрытии цикла, используя конечное множество приводимых конфигураций, невозможно. Каждая приводимая конфигурация содержит цикл, поэтому для любого конечного множества S приводимых конфигураций существует число γ такое, что все конфигурации в наборе содержат цикл длины не более γ. Однако существуют снарки со сколь угодно большим обхватом, т. е. со сколь угодно высокими границами длины их кратчайшего цикла. Снарк G с обхватом больше γ не может содержать ни одну из конфигураций из множества S , поэтому сокращения в S недостаточно сильны, чтобы исключить возможность того, что G может быть минимальным контрпримером.

Гипотеза о круговом вложении

Если граф имеет циклическое двойное покрытие, циклы покрытия можно использовать для формирования 2-клеток графа, вложенного в двумерный клеточный комплекс . В случае кубического графа этот комплекс всегда образует многообразие . Говорят, что граф вложен по кругу в многообразие, поскольку каждая грань вложения представляет собой простой цикл в графе. Однако цикловое двойное покрытие графа степени больше трёх может не соответствовать вложению на многообразии: клеточный комплекс, образованный циклами покрытия, может иметь в своих вершинах немногообразную топологию. Гипотеза кругового вложения или сильная гипотеза вложения утверждает, что каждый 2-связный граф имеет круговое вложение в многообразие. Если да, то граф также имеет двойное покрытие цикла, образованное гранями вложения.

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

Если круговое вложение существует, оно может не находиться на поверхности минимального рода: Нгуен Хуй Сюонг описал 2-связный тороидальный граф, ни одно из круговых вложений которого не лежит на торе.

Более сильные гипотезы и связанные с ними проблемы

Более сильная версия гипотезы о круговом вложении, которая также рассматривалась, — это гипотеза о том, что каждый 2-связный граф имеет круговое вложение на ориентируемом многообразии . С точки зрения гипотезы о двойном покрытии цикла это эквивалентно гипотезе о том, что существует двойное покрытие цикла и ориентация каждого из циклов в покрытии, такая, что для каждого ребра e два цикла, покрывающие e, ориентированы в противоположные направления через e .

В качестве альтернативы также рассматривались усиления гипотезы, связанные с раскраской циклов в покрытии. Самая сильная из них — гипотеза о том, что каждый граф без мостов имеет круговое вложение на ориентируемое многообразие, грани которого могут быть пятицветными. Если это правда, это будет означать гипотезу У. Т. Тутта о том, что каждый граф без мостов имеет нигде ненулевой 5-поток .

Более сильный тип вложения, чем круговое вложение, — это многогранное вложение , вложение графа на поверхность таким образом, что каждая грань представляет собой простой цикл, а каждые две пересекающиеся грани делают это либо в одной вершине, либо в одном ребре. . (В случае кубического графа это можно упростить до требования, чтобы каждые две пересекающиеся грани пересекались по одному ребру.) Таким образом, ввиду сведения гипотезы о двойном покрытии цикла к снаркам, это представляет интерес исследовать полиэдрические вложения снарков. Не сумев найти такие вложения, Бранко Грюнбаум предположил, что их не существует, но Кохоль ( 2009a , 2009b ) опроверг гипотезу Грюнбаума, обнаружив снарк с многогранным вложением.

См. также

• Гипотеза Петерсена о раскраске

Ссылки

• Флейшнер, Герберт (1976), «Общая основа теории эйлеровых графов и теорема Петерсена», Monthly Books for Mathematics , 81 (4): 267–278, doi : 10.1007/BF01387754 , S2CID   118767538 .
• Итай, А.; Роде, М. (1978), «Покрытие графа схемами», Автоматы, языки и программирование. ICALP 1978. , Конспекты лекций по информатике (Аузиелло, Г., Бём, К. (ред.)), vol. 62, Springer, стр. 289–299, номер документа : 10.1007/3-540-08860-1_21 , ISBN.  978-3-540-08860-8 {{citation}}: CS1 maint: дата и год ( ссылка ) .
• Хак, А. (2000), «Приводимые конфигурации для гипотезы о двойном покрытии цикла», Discrete Applied Mathematics , 99 (1–3): 71–90, doi : 10.1016/S0166-218X(99)00126-2 .
• Джагер, Ф. (1985), «Обзор гипотезы о двойном покрытии цикла», Annals of Discrete Mathematics 27 – Cycles in Graphs , North-Holland Mathematics Studies, vol. 27, стр. 1–12, doi : 10.1016/S0304-0208(08)72993-1 , ISBN.  978-0-444-87803-8 .
• Кохол, Мартин (1996), «Снарки без малых циклов», Журнал комбинаторной теории, серия B , 67 (1) (1-е изд.): 34–47, doi : 10.1006/jctb.1996.0032 .
• Кохоль, Мартин (2009a), «3-регулярные графы, не раскрашиваемые в 3-ребра, с многогранными вложениями в ориентируемые поверхности», Graph Drawing 2008, Редакторы: И. Г. Толлис, М. Патриньяни , Конспекты лекций по информатике, том. 5417, стр. 319–323 .
• Кохол, Мартин (2009b), «Многогранные вложения снарков в ориентируемые поверхности», Труды Американского математического общества , 137 (5) (5 изд.): 1613–1619, doi : 10.1090/S0002-9939-08-09698- 6 .
• Сеймур, П.Д. (1979), «Суммы схем», в Бонди, Дж.А.; Мерти, USR (ред.), Теория графов и смежные темы , Нью-Йорк: Academic Press, стр. 342–355, ISBN  978-0121143503 {{citation}}: CS1 maint: дата и год ( ссылка ) .
• Секерес, Г. (1973), «Многогранное разложение кубических графов», Бюллетень Австралийского математического общества , 8 (3): 367–387, doi : 10.1017/S0004972700042660 .
• Тутте, WT (1987), Личная переписка с Х. Фляйшнером (22 июля 1987 г.) .
• Чжан, Цунь-Цюань (1997), Целочисленные потоки и циклические покрытия графов , CRC Press, ISBN  978-0-8247-9790-4 .
• Чжан, Цунь-Цюань (2012), Двойная обложка графиков , Cambridge University Press, ISBN  978-0-5212-8235-2 .

Внешние ссылки

• Гипотеза циклического двойного покрытия , гипотеза кругового вложения и гипотеза Грюнбаума из Сада открытых проблем.
• Гипотеза о двойной обложке цикла. Архивировано 5 декабря 2008 г. в Wayback Machine , Дэн Арчдикон .
• Вайсштейн, Эрик В. , «Гипотеза о двойном покрытии цикла» , MathWorld