|
В графе $%2n$% вершин, степень каждой равна $%n$%. Докажите, что после удаления любого подмножества из менее чем $%n$% ребер получается связный граф. Мое решение:
Для начала докажем, что после удаления $%n - 1$% ребер, у нас их вообще остается достаточно, чтобы граф был связным. Далее докажем, что никакую вершину нельзя отсоединить от графа. Так как каждая вершина связана с остальным графом $%n$% ребрами, значит, при удалении $%n - 1$% ребер, вершина так же останется связанна с остальным графом как минимум одним ребром. Значит, граф останется связным, что и требовалось доказать. Я правильно все доказал? задан 18 Ноя '14 18:46 
Leva319 |
|
Прежде всего, граф из условия задачи должен считаться простым: в противном случае утверждение не будет верно. Я так понимаю, что в большинстве задач этого рода такое предположение делается "по умолчанию". Соображение из второго абзаца можно опустить, так как эта проверка ничего не даёт. Количество рёбер $%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 
falcao
Я не понял этого момента. То есть у нас получается двудольный граф, где 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
|