В графе 100 вершин и 200 ребер. Докажите, что в нем есть 2 простых цикла одинаковой длины.

задан 21 Сен '14 11:23

изменен 21 Сен '14 12:27

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

@Lackawanna, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(21 Сен '14 12:27) Виталина
10|600 символов нужно символов осталось
0

Рассмотрим в каждой из связных компонент графа максимальное поддерево $%T_i$%, а также отметим одну из вершин $%o_i$%. Если $%n_i$% -- число вершин этой связной компоненты, то в дерево входит в точности $%n_i-1$% ребро. Общее количество рёбер, входящих в деревья, равно $%\sum (n_i-1)\le n-1$%, где $%n=\sum n_i$% -- общее число вершин. По условию, общее количество рёбер равно $%2n$%, поэтому имеется по крайней мере $%n+1$% ребро, не входящее ни в одно из деревьев.

Пусть $%e$% -- одно из таких рёбер с началом $%u$% и концом $%v$%, принадлежащее $%i$%-й связной компоненте. Рассмотрим следующий цикл с началом и концом $%o_i$%. Сначала пройдём по рёбрам выбранного поддерева кратчайшим путём из $%o_i$% в $%u$%, затем пройдём ребро $%e$%, и далее вернёмся в $%o_i$% по кратчайшему пути в поддереве $%T_i$% из $%v$% в $%o_i$%. Рассмотренный цикл $%\gamma(o_i,u)e\gamma(v,o_i)$%, вообще говоря, не является простым. Здесь $%\gamma$% обозначает кратчайший (геодезический) путь из одной вершины в другую по рёбрам поддерева. Если мы теперь рассмотрим максимальное общее начало $%p$% путей $%\gamma(o_i,u)$% и $%\gamma(o_i,v)$%, то рассмотренный нами путь примет вид $%pqp^{-1}$%, где $%q$% является простым циклом. Длина такого цикла не меньше $%1$% и не больше $%n$%, а самих таких циклов мы построили столько, сколько имеется рёбер, не входящих в поддеревья вида $%T_i$%. Все они попарно различны, так как каждый цикл содержит ровно одно ребро не из поддеревьев. Поскольку циклов построено не меньше $%n+1$%, по принципу Дирихле какие-то два из них должны иметь одинаковую длину.

Добавление. Небольшое упрощение по ходу дела. Можно не отмечать точки в компонентах связности, а для каждого ребра $%e$%, не входящего в дерево, брать кратчайший путь $%s$% в этом дереве от конца $%e$% к началу $%e$%. Тогда сразу возникает простой цикл $%es$%, свой для каждого такого ребра $%e$%.

ссылка

отвечен 21 Сен '14 11:49

изменен 21 Сен '14 18:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×334
×113

задан
21 Сен '14 11:23

показан
761 раз

обновлен
21 Сен '14 18:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru