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

[alphavector]

Добрый день! Давно мучаюсь с одной олимпиадной задачкой (и подсчеты, и индукция, много чего банального и не очень пробовал), так что уже не уверен что это не какая-то открытая проблема:

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


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

[Sonic86]

А почему бы не попробовать индукцию по $n$? Мне кажется она сработает.

[Evgenjy]

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

А почему бы не попробовать индукцию по $n$? Мне кажется она сработает.

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

[leolev]

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

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

А почему бы не попробовать индукцию по $n$? Мне кажется она сработает.

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

А как строго доказать, что каждая связанная компонента такого графа имеет контур? И почему тогда нельзя убрать все, кроме контура?

P.S.я тоже встречал эту задачу недавно, но не решил(

[Skeptic]

Для вершины в цикле достаточно иметь два ребра: одно входящее и одно выходящее. Все остальные ребра вершины можно удалить.

[Brukvalub]

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

[alphavector]

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

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

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

[alphavector]

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

Для вершины в цикле достаточно иметь два ребра: одно входящее и одно выходящее. Все остальные ребра вершины можно удалить.

Но у каждого ребра по n входящих и выходящих, какие n-1 из n удалять?

[arseniiv]

Очевидно, тут будет произвол. И поначалу громадный — можно удалить любую дугу. Удалив дугу, мы делаем граф «плохим» — у некоторых его вершин входная и выходная степени будут не равны, и это надо поправить, потому что в наборе циклов такого не бывает. При исправлении может получиться и такое, и эдакое.

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

Для вершины в цикле достаточно иметь два ребра: одно входящее и одно выходящее. Все остальные ребра вершины можно удалить.

В простом цикле — всё так. А в любом цикле не обязательно. Посмотрите на граф $1\to2\to3\to1\to4\to1$; целиком он тоже цикл, но при этом связен. А если исследовать более узкую задачу о разбиении на именно простые циклы, может статься, она и не всегда разрешима (это моё дилетантское в теории графов мнение, ничего не проверял; сужать задачу всё равно нет причин).

[iifat]

(Оффтоп)

Кажется, понял.
Надо вычеркнуть несколько дуг, чтоб из каждой вершины и в каждую входило/выходило по $n-1$ дуг. Строим двудольный граф. Каждой вершине нашего сопоставляем вершину одной доли и вершину другой. Каждой дуге понятным образом сопоставляем дугу двудольного графа. Потом решаем на нём задачу паросочетаний — и вот он, набор наших дуг.

[g______d]

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

[iifat]

Рисовать не особо умею, поэтому приведу матрицу инцидентности.
$\begin{pmatrix}0&1&0&1\\0&0&1&0\\1&0&0&0\\1&0&0&0\end{pmatrix}$
Ну, то бишь, цикл 1 — 2 — 3 — 1 плюс петля 1 — 4 — 1. Баланс соблюдается, но на циклы не распадается.

[g______d]

А, я неправильно понял слово "распадается". Что оно означает? Что вершина может входить только в один цикл?

Хорошо, а циклы длины 0 считаются?

[alphavector]

g______d в сообщении #1022653 писал(а):

А, я неправильно понял слово "распадается". Что оно означает? Что вершина может входить только в один цикл?

Хорошо, а циклы длины 0 считаются?

Подозреваю, что автором задачи подразумевалось что граф должен стать дизъюнктным объединением циклов (возможно одного)

Вообще, тут правильно высказались насчет процессов - задача на эту тему, но что-то тривиально пройдет навряд ли

[g______d]

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

-- Пн, 01 июн 2015 18:13:39 --

По-моему, решение написано здесь: http://en.wikipedia.org/wiki/2-factor_theorem

Изначально это теорема для неориентированного графа, но на первом же шаге из него делается ориентированный, поэтому можно начать сразу с этого ориентированного.