Двойное покрытие графа циклами

[MerkulovaLE]

Добрый вечер!

Гипотеза о двойном покрытии циклами
(Гипотеза о круговом вложении)

Формулировка гипотезы:

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

Мост - ребро в теории графов, удаление которого увеличивает число компонент связности.

Доказательство гипотезы:

Доказано сведение графа к кубическому.
Далее будем рассматривать кубические графы.

Циклы из трех ребер исключаются, три ребра соединяются в трехлучевую звезду. При восстановлении исходного графа удаленный цикл из трех ребер - один из циклов и соответствует гипотезе.

Также, в графе без мостов присутствует как минимум один цикл.
Если этот цикл гамильтонов, то в кубическом графе число ребер цикла четное.

Двойное покрытие циклами cтроится так: Гамильтонов цикл - первый цикл; четные ребра гамильтонова цикла и хорды - циклы; нечетные ребра гамильтонова цикла и хорды - циклы. Эти циклы проходят каждое ребро ровно два раза.

Если цикл не гамильтонов, то делим граф на две части - цикл и остальные вершины. "Висячие" ребра между циклом и остальной частью графа соединяем вместе для цикла и остальной части. Потом эту вершину разбиваем на несколько вершин, которым инцидентны два или три ребра.

Цикл выбираем такой, что в остальной части графа нет вершин, связанных с двумя или тремя вершинами цикла. (Тогда нет изолированных вершин или вершин с одним инцидентным ребром в остальной части графа).

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

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

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

Остальная часть графа (второй подграф) зацикливается как удобно, цикл - согласно остальной части графа. В процессе разрезов графа (подграфа) - соединяются два или три ребра, если две части графа (подграфа) соединяют только они.

Граф и подграфы разрезаются до выявления всех подциклов, которые потом "склеиваются". Из одного графа без мостов получаются несколько подграфов без мостов. (Цикл, содержащий не менее четырех вершин, и остальная часть графа). В подграфе из четырех вершин гамильтонов цикл находится элементарно.

Гипотеза доказана.

Спасибо за внимание!

[Sender]

MerkulovaLE в сообщении #1569007 писал(а):

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

А если граф представляет собой простой цикл? Мостов нет, но утверждение гипотезы явно не выполнено.

[Ende]

MerkulovaLE
Вообще говоря, перенос темы в Карантин означает, что нужно отредактировать тему в Карантине, а не создать новую такую же. Но, поскольку новое стартовое сообщение оформлено правильно, на первый раз оставим все как есть.

[MerkulovaLE]

Sender, при графе - простом цикле два этих цикла подходят условию, циклы в наборе могут повторяться.

Пропущенное в доказательстве:

Если граф можно разрезать так, что разрезаются два ребра, разделить граф на две части и соединить два ребра в каждой части. Если граф можно разрезать так, что разрезаются три ребра, и в каждой части более одной вершины, то разделить граф на две части и соединить в каждой части три разрезанных ребра.

Если в графе, разделенном на цикл и остальную часть графа, разрезается нечетное количество ребер, то три ребра соединяются; цикл же при этом становится новым графом без мостов.

Если цикл в графе состоит из четырех ребер и есть два ребра, соединяющие первую и третью или вторую и четвертую вершины цикла, то выделить эти ребра в отдельный подграф. Получаются две вершины, соединенные тремя путями по два ребра каждый. Если три вершины соединены, то получается двудольный граф $K(3,3)$, в котором легко можно выделить нужные циклы. Если соединены две вершины, то третья вершина и ребро от двух вершин соединяются. Мы получаем граф, в котором разрез разрезает два ребра. Если вершины не соединены, то разрез разрезает три ребра и получаются два подграфа, каждый из которых идет в работу дальше.

[Ende]

MerkulovaLE
Чтобы упомянуть участника, нажмите на его ник мышкой. А если пишете вручную, не забывайте теги жирного шрифта.
Тогда участник увидит в уведомлениях, что его упомянули, и с большей вероятностью ответит.

[Null]

Возьмем обход всех ребер в ширину или в глубину и сделаем из него цикл(не простой) который ходит по каждому ребру(1 раз туда и 1 раз обратно). Теперь идем по этому циклу и бьем его на простые - вернулись в вершину принадлежащую текущему пути - получили простой цикл - выводим его и выкидываем из пути - продолжаем идти дальше с этой вершины.