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

задан 27 Окт '15 15:10

изменен 27 Окт '15 22:03

10|600 символов нужно символов осталось
1

Хорошая задача, только условие надо подкорректировать. Во-первых, граф следует считать конечным (в противном случае утверждение неверно). Во-вторых, граф может вообще не иметь циклов (дерево), поэтому надо потребовать условия $%a\ge2$%. В-третьих, под графом нужно понимать простой граф, то есть без петель и кратных рёбер.

Вывод здесь можно будет даже несколько усилить, доказав, что найдётся цикл длиной не меньше $%a+1$%.

Вот скорректированная формулировка. Дан простой конечный граф, в котором каждая вершина имеет степень не меньше $%d\ge2$%. Тогда в нём найдётся (простой) цикл длиной не меньше $%d+1$%.

Рассмотрим самый длинный простой путь, то есть такой путь, в котором вершины не повторяются: $%v_1-v_2-\cdots-v_n$%. Это возможно, так как граф конечен. Вершина $%v_1$% имеет степень не меньше двух, поэтому она соединена в графе ещё по крайней мере с одной вершиной. Если это вершина, отличная от вершин рассматриваемого пути, то путь можно удлинить. Следовательно, все соединения $%v_1$% имеют место лишь с вершинами пути. Пусть $%j > 1$% -- максимальный из таких номеров, для которого $%v_1$% соединена с $%v_j$%. При этом возникает простой цикл длиной $%j$%.

Соединений у вершины $%v_1$% может быть не более $%j-1$%: только с вершинами $%v_2$%, ... , $%v_j$%. Следовательно, $%d\le j-1$%, то есть длина цикла $%j\ge d+1$%.

ссылка

отвечен 27 Окт '15 18:05

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

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

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

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

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

отмечен:

×3,340
×477

задан
27 Окт '15 15:10

показан
1235 раз

обновлен
27 Окт '15 22:03

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

по почте:

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

по RSS:

Ответы

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

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