В конечном графе степень каждой вершины по крайней мере равна а . Доказать, что в этом графе обязательно найдется цикл длины не меньше а задан 27 Окт '15 15:10 NataliaIvanova |
Хорошая задача, только условие надо подкорректировать. Во-первых, граф следует считать конечным (в противном случае утверждение неверно). Во-вторых, граф может вообще не иметь циклов (дерево), поэтому надо потребовать условия $%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 falcao |