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

[iifat]

А можно попросить вот это

Цитата:

Let G be 2k-regular graph. then E(G) can be decomposed into the union of k line-disjoint 2-factors

по-русски? Так понимаю, если из/и каждой вершины вы- и входят по $2k$ дуг (или это про неориентированные?), то граф можно разбить на объединение $k$ — чего?

-- 02.06.2015, 12:40 --

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

циклы длины 0 считаются?

Думаю, нет — иначе можно стереть все вообще рёбра, оставив кучу циклов длины 0

[g______d]

iifat в сообщении #1022656 писал(а):

про неориентированные?

Про неориентированные. Но там на первом шаге берётся неориентированный граф степени $2k$, в нём строится эйлеров цикл, и дальше каждое ребро ориентируется в направлении этого цикла. У нас изначально граф ориентирован. Можно построить в нём ориентированный эйлеров цикл и прийти к той же ситуации.

iifat в сообщении #1022656 писал(а):

то граф можно разбить на объединение $k$ — чего?

Непересекающихся подграфов степени 2, т. е. того, что нужно. Я, правда, не проверил, что у них будет нужная ориентация. Но это, по-моему, сразу следует из конструкции.

-- Пн, 01 июн 2015 19:12:43 --

Попробую перевести на русский. Пусть есть ориентированный граф со множеством вершин $V$. Возьмём два экземпляра множества вершин $V'$ и $V''$ и для каждого ребра $(u,v)$ исходного графа добавим ребро $(u',v'')$ в новый граф. Новый граф является двудольным графом степени $k$ с долями $V'$ и $V''$. Возьмём какое-нибудь паросочетание этого двудольного графа. Очевидно, как по нему построить разбиение исходного графа на циклы: для каждой вершины мы знаем, куда из неё идти (в ту, с которой она паросочетается).

[iifat]

Дааа... Осталось доказать, что паросочетание будет полным. Пошёл вспоминать теорию.

[Skeptic]

Доказать - это не значит только построить.
По ссылке, приведённой Brukvalub, есть задача с решением без построения.

Цитата:

Пример 3. В стране Радонежии некоторые города связаны между собой авиалиниями. Из столицы выходит 1985 авиалиний, из города Дальнего - одна, а из остальных городов - по 20 линий. Докажите, что из столицы можно добраться до Дальнего (быть может, с пересадками).
Решение. Рассмотрим множество городов, до которых можно добраться из столицы. Это граф: его вершины (города, ребра) авиалинии, их соединяющие. Из каждой вершины графа выходит столько рёбер, сколько всего авиалиний выходит из соответствующего города. Граф содержит нечётную вершину - столицу. Поскольку число нечётных вершин в графе чётно, в нем есть ещё одна нечётная вершина. Этой вершиной может быть только город Дальний.

В таком ключе надо искать доказательство в поставленной ТС задаче.

[g______d]

iifat в сообщении #1022670 писал(а):

Дааа... Осталось доказать, что паросочетание будет полным. Пошёл вспоминать теорию.

Теорема Холла. Чтобы её применить, надо проверить, что любые $n$ вершин из одной половинки связаны как минимум с $n$ вершин из другой. Пусть это не так, и $n$ вершин $V'$ связаны только с $m$ вершинами из $V''$, где $m<n$. Тогда в эти $m$ вершин входит $kn$ рёбер, и, поскольку всего вершин $m$, хотя бы в одну из них будет входить больше $k$ рёбер.

-- Пн, 01 июн 2015 22:47:05 --

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

Доказать - это не значит только построить.
По ссылке, приведённой Brukvalub, есть задача с решением без построения.

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

В таком ключе надо искать доказательство в поставленной ТС задаче.

Я не уверен, что вы поняли, что сказали.

[iifat]

А, так вот где всплыло условие на количество входящих и выходящих рёбер!
Спасибо.

[arseniiv]

(Оффтоп)

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

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

Тогда, получается, я тоже неправильно понял. Кстати, что странно, мы с iifat привели в пример один и тот же граф.

[Evgenjy]

leolev в сообщении #1022151 писал(а):

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

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

leolev в сообщении #1022151 писал(а):

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

Правильно. Можно.

[iifat]

У вас одна вершина распадается на $n$ дуг. Если, к примеру, пара этих дуг войдёт в остаточные циклы, вам придётся исключённую вершину включать в два цикла.

[Skeptic]

Сколько циклов в этом графе?

(Оффтоп)

g______d, если не понимаете, что я написал, - это ваши проблемы.

[arseniiv]

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

Сколько циклов в этом графе?

Не иначе издеваетесь. Их не 2, и даже не 22.

[iifat]

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

Сколько циклов в этом графе?

Не соблаговолите как-то увязать свой вопрос с темой топика?

[Skeptic]

Извините, неаккуратно задал вопрос.

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

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

На сколько циклов можно разбить предложенный граф, убирая рёбра?

[iifat]

На один.

[Skeptic]

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