Каждый ли граф без мостов имеет мультимножество циклов, покрывающее каждое ребро ровно дважды?
В теоретико-графовой математике двойное покрытие цикла - это набор циклов в неориентированном графе, которые вместе включают каждое ребро графа ровно дважды. Например, для любого многогранного графа грани выпуклого многогранника , представляющего граф, обеспечивают двойное покрытие графа: каждое ребро принадлежит ровно двум граням.
Это нерешенная проблема, поставленная Джорджем Секересом [1] и Полом Сеймуром [2] и известная как гипотеза о циклическом двойном покрытии , имеет ли каждый граф без мостов циклическое двойное покрытие. Гипотеза может быть эквивалентно сформулирована в терминах вложения графов , и в этом контексте также известна как гипотеза кругового вложения .
Формулировка [ править ]
Обычная формулировка гипотезы о двойном покрытии циклов спрашивает, имеет ли каждый неориентированный граф без мостов набор циклов , каждое ребро графа содержится ровно в двух из этих циклов. Требование, чтобы граф был без мостов, является очевидным необходимым условием для существования такого набора циклов, потому что мост не может принадлежать ни одному циклу. Набор циклов, удовлетворяющий условию гипотезы о двойном покрытии цикла, называется двойным покрытием цикла . Некоторые графы, такие как графы циклов и графы кактусов без мостов, могут быть покрыты только за счет использования одного и того же цикла более одного раза, поэтому такое дублирование разрешено в двойном покрытии цикла.
Редукция к снаркам [ править ]
Снарк является частным случаем bridgeless графа, имеющим дополнительные свойства , что каждая вершина имеет ровно три падающие краев (то есть, граф кубический ) , и что это не возможно для разделения ребер графа на три совершенные паросочетания ( то есть граф не имеет 3- краевой раскраски и по теореме Визинга имеет хроматический индекс 4). Оказывается, что снарки являются единственным трудным случаем гипотезы о циклическом двойном покрытии: если гипотеза верна для снарков, то она верна для любого графа. [3]
Jaeger (1985) отмечает, что в любом потенциальном минимальном контрпримере к гипотезе о циклическом двойном покрытии все вершины должны иметь три или более инцидентных ребра. В самом деле, вершина с инцидентным только одним ребром образует мост, в то время как если два ребра инцидентны вершине, их можно сжать, чтобы сформировать меньший граф, так что любое двойное покрытие меньшего графа продолжается до одного из исходных графов. С другой стороны, если вершина vимеет четыре или более инцидентных ребра, можно «отщепить» два из этих ребер, удалив их из графа и заменив их одним ребром, соединяющим их две другие конечные точки, сохраняя при этом отсутствие мостов в результирующем графе. Опять же, двойное покрытие результирующего графа может быть расширено прямым способом до двойного покрытия исходного графа: каждый цикл отщепленного графа соответствует либо циклу исходного графа, либо паре циклов, пересекающихся в v. Таким образом, каждый минимальный контрпример должен быть кубическим. Но если кубический граф может иметь ребра трехцветного цвета (скажем, красного, синего и зеленого цветов), тогда подграф красных и синих ребер, подграф синих и зеленых ребер и подграф красных и зеленых ребер каждый из них образует набор непересекающихся циклов, которые вместе покрывают все ребра графа дважды. Следовательно, каждый минимальный контрпример должен быть кубическим графом без мостов, не раскрашиваемым по 3 ребрам, то есть снарком. [3]
Редуцируемые конфигурации [ править ]
Одна из возможных атак на проблему двойного покрытия цикла могла бы состоять в том, чтобы показать, что не может существовать минимального контрпримера, путем доказательства того, что любой граф содержит приводимую конфигурацию , подграф, который может быть заменен меньшим подграфом таким образом, чтобы сохранить существование или отсутствие двойной крышки цикла. Например, если кубический граф содержит треугольник, преобразование Δ-Y заменит треугольник одной вершиной; любое двойное покрытие цикла меньшего графа может быть расширено до двойного покрытия цикла исходного кубического графа. Следовательно, минимальный контрпример к гипотезе о циклическом двойном покрытии должен быть графом без треугольников , исключающим некоторые снарки, такие как граф Титце.которые содержат треугольники. Благодаря компьютерному поиску известно, что каждый цикл длины 11 или меньше в кубическом графе образует приводимую конфигурацию, и поэтому любой минимальный контрпример к гипотезе о двойном покрытии цикла должен иметь обхват не менее 12. [4]
К сожалению, невозможно доказать гипотезу о циклическом двойном покрытии, используя конечный набор приводимых конфигураций. Каждая приводимая конфигурация содержит цикл, поэтому для каждого конечного множества S приводимых конфигураций существует такое число γ, что все конфигурации в наборе содержат цикл длины не более γ. Однако существуют снарки с произвольно большим обхватом, то есть с произвольно высокими границами длины их кратчайшего цикла. [5] Снарк G с обхватом больше γ не может содержать ни одной из конфигураций из множества S , поэтому редукции в S недостаточно сильны, чтобы исключить возможность того, что G может быть минимальным контрпримером.
Гипотеза кругового вложения [ править ]
Если граф имеет циклическое двойное покрытие, циклы покрытия можно использовать для формирования 2-ячеек графа, встраиваемого в двумерный комплекс ячеек . В случае кубического графа этот комплекс всегда образует многообразие . Граф называется циклически вложенным в многообразие в том смысле, что каждая грань вложения является простым циклом в графе. Однако циклическое двойное покрытие графа со степенью больше трех может не соответствовать вложению на многообразие: клеточный комплекс, образованный циклами покрытия, может иметь в вершинах немногообразную топологию. Гипотеза о круговом вложении или сильная гипотеза о вложении [3] утверждает, что каждоедвусвязный граф имеет круговое вложение на многообразие. Если это так, то граф также имеет циклическое двойное покрытие, образованное гранями вложения.
Для кубических графов двусвязность и отсутствие мостов эквивалентны. Следовательно, гипотеза о круговом вложении, очевидно, не менее сильна, чем гипотеза о циклическом двойном покрытии. Однако, оказывается, не сильнее. Если вершины графа G расширяются, образуя кубический граф, который затем циклический внедренный и разложения отменяются стягивание добавлены краев, то результат будет круглое вложением G сам. Следовательно, если гипотеза о циклическом двойном покрытии верна, каждый двусвязный граф имеет круговое вложение. Таким образом, гипотеза о двойном покрытии цикла эквивалентна гипотезе о круговом вложении, хотя двойное покрытие цикла и круговое вложение не всегда одно и то же. [3]
Если круговое вложение существует, оно может не быть на поверхности минимального рода: Нгуен Хуй Сюонг описал двусвязный тороидальный граф, ни одно из круговых вложений которого не лежит на торе. [3]
[ править ]
Более сильная версия гипотезы о круговом вложении, которая также рассматривалась, - это гипотеза о том, что каждый двусвязный граф имеет круговое вложение на ориентируемое многообразие . В терминах гипотезы о двойном циклическом покрытии это эквивалентно гипотезе о существовании циклического двойного покрытия и ориентации для каждого из циклов в покрытии, так что для каждого ребра e два цикла, покрывающих e , ориентированы в в противоположных направлениях через e . [3]
В качестве альтернативы также рассматривались усиления гипотезы о раскраске циклов в покрытии. Самая сильная из них - это гипотеза о том, что любой граф без мостов имеет круговое вложение на ориентируемое многообразие, в котором грани могут быть 5-раскрашены. Если это правда, это будет означать гипотезу У. Т. Тутта о том, что каждый граф без мостов имеет нигде-нулевой 5-поток . [3]
Более сильный тип вложения, чем круговое вложение, - это полиэдральное вложение , вложение графа на поверхность таким образом, что каждая грань представляет собой простой цикл, а каждые две пересекающиеся грани делают это либо в одной вершине, либо в одном ребре. . (В случае кубического графа это можно упростить до требования, чтобы каждые две пересекающиеся грани делали это на одном ребре.) Таким образом, с учетом сведения гипотезы о циклическом двойном покрытии к снаркам, представляет интерес исследовать полиэдральные вложения снарков. Не имея возможности найти такие вложения, Бранко Грюнбаум предположил, что их не существует, но Кохоль ( 2009a , 2009b ) опроверг гипотезу Грюнбаума, найдя снарк с полиэдральным вложением.
См. Также гипотезу о раскраске Петерсена .
Заметки [ править ]
- ^ Шекереса (1973) .
- ^ Сеймур (1980) .
- ^ Б с д е е г Jaeger (1985) .
- ^ Гек (2000) .
- ^ Kochol (1996) .
Ссылки [ править ]
- Флейшнер, Герберт (1976), «Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen», Monatshefte für Mathematik , 81 (4): 267–278, doi : 10.1007 / BF01387754.
- Хак, А. (2000), "Приводимые конфигурации для гипотезы о двойном покрытии цикла", Дискретная прикладная математика , 99 (1–3): 71–90, DOI : 10.1016 / S0166-218X (99) 00126-2.
- Jaeger, F. (1985), "Обзор цикла накрытия гипотезы", Annals дискретной математики 27 - Циклы в графах , North-Holland Mathematics Studies, 27 , стр 1-12. Дои : 10.1016 / S0304-0208 (08) 72993-1.
- Кохол, Мартин (1996), «Снарки без малых циклов», Журнал комбинаторной теории, серия B (1 изд.), 67 (1): 34–47, DOI : 10.1006 / jctb.1996.0032.
- Кохол, Мартин (2009a), «3-регулярные не 3-крано-раскрашиваемые графы с полиэдральными вложениями в ориентируемые поверхности», Graph Drawing 2008, редакторы: И. Г. Толлис, М. Патриньяни , Lecture Notes in Computer Science, 5417 , стр. 319 –323.
- Кохол, Мартин (2009b), «Многогранные вложения снарков в ориентируемые поверхности», Труды Американского математического общества (5-е изд.), 137 (05): 1613–1619, DOI : 10.1090 / S0002-9939-08-09698- 6.
- Seymour, PD (1980), "непересекающиеся пути в графах", дискретная математика , 29 (3): 293-309, DOI : 10.1016 / 0012-365X (80) 90158-2.
- Шекереса, Г. (1973), "Многогранные разложение кубических графов", Бюллетень австралийского математического общества , 8 (03): 367-387, DOI : 10,1017 / S0004972700042660.
- Чжан, Цун-Цюань (1997), Целочисленные потоки и покрытия циклов графов , CRC Press, ISBN 978-0-8247-9790-4.
- Чжан, Цунь-Цюань (2012), Двойное покрытие схемы графов , Cambridge University Press, ISBN 978-0-5212-8235-2.
Внешние ссылки [ править ]
- Цикл двойной крышка догадка , циркулярное вложение гипотеза и гипотеза Грюнбаума в , с открытой проблемой сада.
- Гипотеза о двойном покрытии цикла , Дэн Архидьякон .
- Вайсштейн, Эрик В. , "Гипотеза о двойном покрытии цикла" , MathWorld
