В графе $%2n$% вершин, степень каждой равна $%n$%. Докажите, что после удаления любого подмножества из менее чем $%n$% ребер получается связный граф.

Мое решение: Для начала докажем, что после удаления $%n - 1$% ребер, у нас их вообще остается достаточно, чтобы граф был связным.
По лемме: сумма степеней всех вершин графа равна $%2*E$% ($%E$% - кол-во ребер), получаем $%2n^2 = 2E$%, отсюда следует, что $%E = n^2$%.
По теореме "В связном графе с $%N$% вершинами не менее $%N - 1$% ребер" получаем, что $%n^2 - ( n - 1) \geq 2n - 1$%. (т.к. вершин у нас $%2n$%, значит ребер должно быть не меньше $%2n - 1$%).
Преобразовываем неравенство и получаем $%\to (n - 1)^2 \geq n - 1$%, что является, несомненно, верно.

Далее докажем, что никакую вершину нельзя отсоединить от графа. Так как каждая вершина связана с остальным графом $%n$% ребрами, значит, при удалении $%n - 1$% ребер, вершина так же останется связанна с остальным графом как минимум одним ребром. Значит, граф останется связным, что и требовалось доказать.

Я правильно все доказал?

задан 18 Ноя '14 18:46

изменен 19 Ноя '14 16:13

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


9917

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

Прежде всего, граф из условия задачи должен считаться простым: в противном случае утверждение не будет верно. Я так понимаю, что в большинстве задач этого рода такое предположение делается "по умолчанию".

Соображение из второго абзаца можно опустить, так как эта проверка ничего не даёт. Количество рёбер $%2n-1$%, необходимое для связности графа, очень далеко от того, чтобы быть достаточным.

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

Далее, нам не дано в условии, что исходный граф связен. Разумеется, это верно, так как граф и после удаления рёбер останется связным, но опираться на такой факт мы не можем, так как он ещё не установлен.

То, что при удалении $%n-1$% ребра каждая вершина соединена с остальной частью, верно. Но этого не достаточно для установления связности. Отсюда следует только то, что после удаления рёбер не возникает изолированных вершин, но этого мало.

Рассуждение я могу предложить вот какое. Предположим, что после удаления рёбер граф оказался не связным. Тогда возникает по крайней мере две связных компоненты, и у той из них, в которой меньше всего вершин, их не более половины от общего количества, то есть не более $%n$%. Обозначим через $%A$% множество её вершин, и пусть $%B$% -- множество остальных вершин.

Поскольку граф простой, а вершин в $%A$% имеется $%k\le n$%, степень каждой вершины из $%A$% не превосходит $%k-1$% (речь о подграфе с множеством вершин $%A$%, полученном после удаления рёбер). Но в исходном графе степень каждой вершины была равна $%n$%. Это значит, что для каждой вершины из $%A$% мы удалили как минимум $%n-k+1$% ребро. Нетрудно заметить, что для всех вершин эти рёбра будут разными, так как они соединяют вершины из $%A$% с вершинами из $%B$%. Это значит, что общее количество удаляемых рёбер составило как минимум $%k(n-k+1)$%, и по условию оно строго меньше $%n$%. Тогда имеет место неравенство $%nk-k^2+k-n < 0$%, что равносильно $%(n-k)(k-1) < 0$%, но это невозможно, так как оба сомножителя неотрицательны.

ссылка

отвечен 19 Ноя '14 2:52

нетрудно заметить, что для всех вершин эти рёбра будут разными, так как они соединяют вершины из A с вершинами из B.

Я не понял этого момента. То есть у нас получается двудольный граф, где A и В это разные доли?

(19 Ноя '14 13:57) Leva319

Нет, они не двудольные, потому что могут быть рёбра, соединяющие вершины из A между собой, а также из B между собой. Но, если на эти рёбра не обращать внимания, мы действительно получим двудольный граф. Число рёбер в нём оценивается, и оно оказывается достаточно большим, не меньшим $%n$% по количеству. Поэтому множества А и В невозможно "разорвать", удаляя менее n рёбер. В этом основная идея.

(19 Ноя '14 14:15) falcao

Множество А у нас обязательно получается связным?

(19 Ноя '14 14:36) Leva319

Да, это так по определению, так как A есть связная компонента. Но это обстоятельство вообще-то не важно: прослеживать надо только необходимую часть рассуждения.

(19 Ноя '14 14:45) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×137

задан
18 Ноя '14 18:46

показан
1580 раз

обновлен
19 Ноя '14 14:45

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

по почте:

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

по RSS:

Ответы

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

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