Разбиения графа на циклы

[iifat]

Как по мне, один — вполне себе несколько. Я, по крайней мере, именно так понял условие. Хотя, возможно, вы и правы.

[Sender]

В стартовом сообщении слово "несколько" отсутствует.

[Evgenjy]

В предыдущих моих сообщениях были ложные предложения.
Вот новое решение.
1 Рассматривается компонент связности.
2 Доказывается распадение на циклы индукцией по количеству вершин.
3 Множество циклов не пусто. Идем по стрелкам и когда-нибудь зацикливаемся. Возьмем цикл $C_1$.
4 Если он не содержит все вершины, то исключим $C_1$ (вершины и дуги) из графа. Остальные входящие и исходящие дуги каждой из вершин $C_1$ соединим попарно в одну дугу общего направления (для каждой пары). Получим такой же граф с меньшим количеством вершин. По предположению индукции его можно разбить на циклы.
5 Если новообразованные дуги не входят в циклы уменьшенного графа, то стираем эти дуги, добавляем $C_1$ и получаем нужное разбиение на циклы.
6 Если какие-либо новообразованные дуги входят в такие циклы, то стираем те новообразованные, которые не входят, а из $C_1$ и циклов уменьшенного графа которые касаются $C_1$ образуем один цикл следующим образом. Начиная с общей вершины $C_1$ и какого-то из касающегося цикла обходим присоединенный цикл и двигаемся по$C_1$ до следующего касающегося, обходим его и т. д. Получаем требуемое разбиение на циклы.

Замечание 1. Решение можно оформить и в виде процесса.
Замечание 2. Речь идет о циклах, у которых повтор вершин допускается в отличие от простых циклов. Это весьма существенно, поскольку существует пример, когда разбиение на простые циклы не возможно.

Skeptic в сообщении #1023080 писал(а):

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

Конечно представление в виде одного цикла также считается разбиением. Также и допустимо удаление нуля дуг. Пример: Исходный граф -- простой цикл.

[iifat]

Evgenjy в сообщении #1023093 писал(а):

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

Не поделитесь?

-- 04.06.2015, 00:08 --

Evgenjy в сообщении #1023093 писал(а):

Речь идет о циклах, у которых повтор вершин допускается в отличие от простых циклов

Попытался себе представить ваш алгоритм на

Skeptic в сообщении #1022835 писал(а):

этом графе

Выделяем цикл 1 — 2 — 5 — 1, остаётся граф $\{3,4\}$, из него делаем цикл 3 — 4 — 3, соответствующий циклу 3 — 4 — 2 — 3 исходного графа. То бишь, вы допускаете циклы с повторением вершин, да ещё и пересекающиеся циклы, не? Слишком просто, имхо. Раз в/из любой вершины входят и выходят дуги, можно было б просто выписать все циклы графа и обойтись безо всяких сложностей.

-- 04.06.2015, 00:18 --

Sender в сообщении #1023092 писал(а):

В стартовом сообщении слово "несколько" отсутствует

А ведь и правда что.

[Skeptic]

iifat

(Оффтоп)

Первый мой вопрос не соответствует постановке задачи.

В постановке задачи сказано

Цитата:

Докажите, что можно убрать часть ребер так, чтобы граф разбился на циклы.

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

Я так понимаю задачу.

Решение простое, когда найден контрпример.

[iifat]

Задача «разбить на более чем один цикл» нерешаема. Контрпример это доказывает.
Задача «разбить на циклы», не уточняя количество — решаема. Решение приведено.
Я лично голосую за второй вариант — хотя бы потому, что контрпример строится элементарно: рисуем простой цикл — такой граф также нельзя разбить на два и более циклов стиранием рёбер. Выбирать — это уже дело ТС и того, кто поставил ему задачу.

[Brukvalub]

Задача взята из книги, на которую я дал ссылку в самом начале, задача давно решена, а на Skeptic советую не обращать внимания - он постоянно несет здесь несусветную чушь.

[Skeptic]

Brukvalub в сообщении #1023151 писал(а):

Задача взята из книги, на которую я дал ссылку в самом начале, задача давно решена, а на Skeptic советую не обращать внимания - он постоянно несет здесь несусветную чушь.

Brukvalub, вы ошиблись форумом, это научный форум, а не коммунальная кухня.
Знаете решение, вот и помогите ТС.
Ваша ссылка - пустая отписка, нет там такой задачи.

[Brukvalub]

Skeptic в сообщении #1023211 писал(а):

Brukvalub в сообщении #1023151 писал(а):

Задача взята из книги, на которую я дал ссылку в самом начале, задача давно решена, а на Skeptic советую не обращать внимания - он постоянно несет здесь несусветную чушь.

Brukvalub, вы ошиблись форумом, это научный форум, а не коммунальная кухня.
Знаете решение, вот и помогите ТС.
Ваша ссылка - пустая отписка, нет там такой задачи.

Ну вот, очередная чушь! Ведь сам ТС на первой странице пишет:

alphavector в сообщении #1022304 писал(а):

Brukvalub в сообщении #1022286 писал(а):

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

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

[Skeptic]

Brukvalub , при чём здесь ТС?
Вас за язык никто не тянул:

Цитата:

Задача взята из книги, на которую я дал ссылку в самом начале, задача давно решена

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

[Brukvalub]

Skeptic в сообщении #1023292 писал(а):

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

Стр. 63, задача 11. Решение задачи дано в этой ветке.
Может быть, вам,Skeptic, как участнику, непрерывно несущему чушь в этом разделе, пора извиниться за свое поведение? Я три раза тыкал вас носом в вашу чушь (указать, где?), но вы ни разу за свою чушь не ответили.

[Sender]

Может, ему не вполне очевидно, что из представленного в ветке является решением? Можно рекомендовать внимательнее присмотреться к сообщениям участника g______d.

[Brukvalub]

(Оффтоп)

Sender в сообщении #1023297 писал(а):

Может, ему не вполне очевидно, что из представленного в ветке является решением? Можно рекомендовать внимательнее присмотреться к сообщениям участника g______d.

Skeptic всегда так делает: сначала напишет полную чушь, а потом, когда его носом в его же чушь ткнут, затаится на время и ничего не отвечает, выжидает, когда все этот эпизод забудут. Я недавно в трех разных местах ему указывал на его чушь, помечая ее словами "а карась икру метал" ( по этим словам можно найти соответствующие места ) в ответ - молчание. Вот и сейчас, увидев свой "косяк" он и не подумает за него извиниться, а просто спрячется на время

[Skeptic]

Brukvalub, спасибо, что точно указали задачу.

[Evgenjy]

Здесь уже указывались источники, где дано решение. Даю еще один, где все это подробно изложено.
Это теорема Петерсена, доказательство которой основано на теореме о свадьбах (Холла).
См. Дистель. Теория графов. Новосибирск. 2002 г. Страница 49 (следствия 2.1.5 и 2.1.4, а также предыдущие положения)