из любого связного графа можно удалить вершину

sergeilevanov

Малый мехмат 7 класс.
Доказать, что из любого связного графа можно удалить вершину со всеми выходящими из нее ребрами, не нарушив связности графа.
Как решить?

pilaf4

Сообщение удалил

Vlad128

здесь что-то не сходится
ключевое слово можно.
Задача гавно думай сам, даже писать лень.

pilaf4

да, туплю. тогда всё сходится.

ramses1971

Очень правильная картинка, она как бы говорит нам, что нужно построить остовное дерево графа.

Vlad128

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

Skilet3d

по индукции легко доказывается, индукция по количеству ребер
при n=1 верно
допустим что верно для n=k
докажем что верно и для n=k+1
Если есть висячие вершины, тогда просто удаляем её с ребром и все доказано, в противном случае в графе должны присутствовать циклы, временно удалим из любого цикла произвольное ребро (граф останется связным по предположению индукции существует вершина, которую можно удалить с её ребрами не нарушив связности,удалим эту вершину, далее если временно удаленное ребро не было связано с удаленной вершиной вернем его назад.

Vlad128

стыдно, товарищи

ramses1971

тогда уж допишу, что осталось найти вершину, из которой идет одно ребро.
на всякий случай поясню, что такая вершина называется "листовой" :)
Оставить комментарий
Имя или ник:
Комментарий: