Оглавление [Скрыть]
Двойная крышка цикла
-
Гипотеза о двойном покрытии цикла
- Гипотеза утверждает, что каждый связный граф имеет двойное покрытие цикла.
- Покрытие состоит из циклов, которые покрывают все ребра графа.
- Гипотеза была предложена в 1960 году и остается открытой.
-
Примеры и контрпримеры
- Существуют кубические графы с двойными покрытиями, но не все кубические графы имеют их.
- Существуют кубические графы без мостов, но не все из них имеют двойные покрытия.
- Гипотеза не выполняется для снарков с большим обхватом.
-
Гипотеза о круговом вложении
- Гипотеза о круговом вложении утверждает, что каждый связный граф имеет круговое вложение в двумерное многообразие.
- Круговое вложение подразумевает вложение циклов покрытия в многообразие.
- Гипотеза эквивалентна гипотезе о двойном покрытии цикла для кубических графов.
-
Усиленные версии гипотезы
- Существуют гипотезы о раскраске циклов на обложке и многогранных вложениях, которые являются более сильными версиями гипотезы о двойном покрытии цикла.
- Бранко Грюнбаум предположил отсутствие многогранных вложений для снарков, но Кохоль опроверг это предположение.
-
Дополнительные сведения
- В статье также упоминаются другие гипотезы и связанные с ними проблемы, а также внешние ссылки на материалы по теме.
Полный текст статьи: