|
Добрый вечер!
Гипотеза о двойном покрытии циклами
(Гипотеза о круговом вложении)
Формулировка гипотезы:
В любом графе без мостов есть набор простых
циклов, для которого каждое ребро содержится
ровно в двух циклах этого набора?
Мост - ребро в теории графов,
удаление которого увеличивает
число компонент связности.
Доказательство гипотезы:
Доказано сведение графа к кубическому.
Далее будем рассматривать кубические графы.
Циклы из трех ребер исключаются, три ребра соединяются
в трехлучевую звезду. При восстановлении исходного графа
удаленный цикл из трех ребер - один из циклов и
соответствует гипотезе.
Также, в графе без мостов присутствует как минимум один
цикл.
Если этот цикл гамильтонов, то в кубическом графе
число ребер цикла четное.
Двойное покрытие циклами cтроится так:
Гамильтонов цикл - первый цикл;
четные ребра гамильтонова цикла и
хорды - второй цикл;
нечетные ребра гамильтонова цикла и
хорды - третий цикл.
Эти три цикла проходят каждое ребро ровно
два раза.
Если цикл не гамильтонов, то делим граф на две части -
цикл и остальные вершины. "Висячие" ребра между циклом и
остальной частью графа соединяем вместе для цикла и
остальной части. Потом эту вершину разбиваем на несколько
вершин, которым инцидентны два или три ребра.
Цикл выбираем такой, что в остальной части графа нет вершин,
связанных с двумя или тремя вершинами цикла.
(Тогда нет изолированных вершин или вершин с одним
инцидентным ребром в остальной части графа).
Если две вершины цикла соединяет цепь
из двух ребер, вершина, инцидентная которым не
принадлежит циклу,
то между этими вершинами не менее двух
ребер цикла. (так как удалены треугольники). Проход по
другой части графа и по цепи - меньше, если ребер три и
более. Если же ребер два, то проход по двум ребрам цикла
и двум ребрам цепи даст цикл из четырех ребер -
минимальный цикл.
Цикл - граф без мостов. Остальная часть графа
с соединенными ребрами - также граф без мостов,
так как соединены вершины, направленные на
цикл без учета хорд цикла.
Допустимы кратные ребра
в цикле. Тогда в цикле может появиться двойное ребро.
В этом случае: проход по одному ребру, второму
и цикл из двух ребер. Такие двойные ребра и ребра,
смежные к двойному заменяются на одно ребро.
Остальная часть графа (второй подграф) зацикливается как удобно,
цикл - согласно остальной части графа.
В процессе разрезов графа (подграфа) - соединяются два или три ребра,
если две части графа (подграфа) соединяют только они.
Граф и подграфы разрезаются до выявления всех подциклов, которые
потом "склеиваются". Из одного графа без мостов получаются несколько
подграфов без мостов. (Цикл, содержащий не менее четырех вершин,
и остальная часть графа).
Гипотеза доказана.
Спасибо за внимание!
|
17.10.2022, 22:30 