2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 04:39 
А можно попросить вот это
Цитата:
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 :wink:

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 05:05 
Аватара пользователя
iifat в сообщении #1022656 писал(а):
про неориентированные?


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

iifat в сообщении #1022656 писал(а):
то граф можно разбить на объединение $k$ — чего?


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

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 08:09 
Дааа... Осталось доказать, что паросочетание будет полным. Пошёл вспоминать теорию.

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 08:39 
Аватара пользователя
iifat в сообщении #1022670 писал(а):
Дааа... Осталось доказать, что паросочетание будет полным. Пошёл вспоминать теорию.


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

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

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

Skeptic в сообщении #1022671 писал(а):
В таком ключе надо искать доказательство в поставленной ТС задаче.


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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 08:54 
А, так вот где всплыло условие на количество входящих и выходящих рёбер!
Спасибо.

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

(Оффтоп)

g______d в сообщении #1022653 писал(а):
А, я неправильно понял слово "распадается". Что оно означает? Что вершина может входить только в один цикл?
Тогда, получается, я тоже неправильно понял. Кстати, что странно, мы с iifat привели в пример один и тот же граф. :-)

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 09:53 
leolev в сообщении #1022151 писал(а):
А как строго доказать, что каждая связанная компонента такого графа имеет контур?

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

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 10:12 
У вас одна вершина распадается на $n$ дуг. Если, к примеру, пара этих дуг войдёт в остаточные циклы, вам придётся исключённую вершину включать в два цикла.

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 18:05 
Сколько циклов в этом графе?
Изображение

(Оффтоп)

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение02.06.2015, 23:04 
Skeptic в сообщении #1022835 писал(а):
Сколько циклов в этом графе?
Не иначе издеваетесь. Их не 2, и даже не 22.

 
 
 
 Re: Разбиения графа на циклы
Сообщение03.06.2015, 01:10 
Skeptic в сообщении #1022835 писал(а):
Сколько циклов в этом графе?
Не соблаговолите как-то увязать свой вопрос с темой топика?

 
 
 
 Re: Разбиения графа на циклы
Сообщение03.06.2015, 07:40 
Извините, неаккуратно задал вопрос.
alphavector в сообщении #1021750 писал(а):
Дан ориентированный граф. Из каждой его вершины выходит n стрелок, и в каждую его вершину входит n стрелок. Докажите, что можно убрать часть ребер так, чтобы граф разбился на циклы.

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

 
 
 
 Re: Разбиения графа на циклы
Сообщение03.06.2015, 08:26 
На один.

 
 
 
 Re: Разбиения графа на циклы
Сообщение03.06.2015, 15:18 
Значит не каждый граф удалением вершин можно разбить на несколько циклов.
Задача, кажется, решена без всяких теорем.

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


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