2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2, 3, 4  След.
 
 Разбиения графа на циклы
Сообщение31.05.2015, 03:55 
Добрый день! Давно мучаюсь с одной олимпиадной задачкой (и подсчеты, и индукция, много чего банального и не очень пробовал), так что уже не уверен что это не какая-то открытая проблема:

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


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

 
 
 
 Re: Разбиения графа на циклы
Сообщение31.05.2015, 08:52 
А почему бы не попробовать индукцию по $n$? Мне кажется она сработает. :roll:

 
 
 
 Re: Разбиения графа на циклы
Сообщение31.05.2015, 14:15 
alphavector в сообщении #1021750 писал(а):
А почему бы не попробовать индукцию по $n$? Мне кажется она сработает.

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение01.06.2015, 01:53 
Evgenjy в сообщении #1021842 писал(а):
alphavector в сообщении #1021750 писал(а):
А почему бы не попробовать индукцию по $n$? Мне кажется она сработает.

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

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение01.06.2015, 12:50 
Для вершины в цикле достаточно иметь два ребра: одно входящее и одно выходящее. Все остальные ребра вершины можно удалить.

 
 
 
 Re: Разбиения графа на циклы
Сообщение01.06.2015, 13:18 
Аватара пользователя
Такие задачи нередко решаются организацией "процесса" (см., например, "процессы и операции") Если разбиения на циклы еще нет, то можно удалить одно ребро, ребер конечное число, поэтому процесс их удаления не может быть бесконечным.

 
 
 
 Re: Разбиения графа на циклы
Сообщение01.06.2015, 13:49 
Brukvalub в сообщении #1022286 писал(а):
Такие задачи нередко решаются организацией "процесса" (см., например, "процессы и операции") Если разбиения на циклы еще нет, то можно удалить одно ребро, ребер конечное число, поэтому процесс их удаления не может быть бесконечным.

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение01.06.2015, 23:09 
Skeptic в сообщении #1022265 писал(а):
Для вершины в цикле достаточно иметь два ребра: одно входящее и одно выходящее. Все остальные ребра вершины можно удалить.

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

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 02:15 

(Оффтоп)

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 03:17 
Рисовать не особо умею, поэтому приведу матрицу инцидентности.
$\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. Баланс соблюдается, но на циклы не распадается.

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 03:38 
Аватара пользователя
А, я неправильно понял слово "распадается". Что оно означает? Что вершина может входить только в один цикл?

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 03:48 
g______d в сообщении #1022653 писал(а):
А, я неправильно понял слово "распадается". Что оно означает? Что вершина может входить только в один цикл?

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

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 03:50 
Аватара пользователя
Да, сорри. Так намного интереснее. Видимо, циклы нулевой длины тоже нельзя :)

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

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

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

 
 
 [ Сообщений: 49 ]  На страницу 1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group