из любого связного графа можно удалить вершину
Сообщение удалил
здесь что-то не сходитсяключевое слово можно.
Задача гавно думай сам, даже писать лень.
да, туплю. тогда всё сходится.
Очень правильная картинка, она как бы говорит нам, что нужно построить остовное дерево графа.
Очень правильная картинка, она как бы говорит нам, что нужно построить остовное дерево графа.тогда уж допишу, что осталось найти вершину, из которой идет одно ребро.
по индукции легко доказывается, индукция по количеству ребер
при n=1 верно
допустим что верно для n=k
докажем что верно и для n=k+1
Если есть висячие вершины, тогда просто удаляем её с ребром и все доказано, в противном случае в графе должны присутствовать циклы, временно удалим из любого цикла произвольное ребро (граф останется связным по предположению индукции существует вершина, которую можно удалить с её ребрами не нарушив связности,удалим эту вершину, далее если временно удаленное ребро не было связано с удаленной вершиной вернем его назад.
при n=1 верно
допустим что верно для n=k
докажем что верно и для n=k+1
Если есть висячие вершины, тогда просто удаляем её с ребром и все доказано, в противном случае в графе должны присутствовать циклы, временно удалим из любого цикла произвольное ребро (граф останется связным по предположению индукции существует вершина, которую можно удалить с её ребрами не нарушив связности,удалим эту вершину, далее если временно удаленное ребро не было связано с удаленной вершиной вернем его назад.
стыдно, товарищи
тогда уж допишу, что осталось найти вершину, из которой идет одно ребро.на всякий случай поясню, что такая вершина называется "листовой"
Похожие темы:
Оставить комментарий
sergeilevanov
Малый мехмат 7 класс.Доказать, что из любого связного графа можно удалить вершину со всеми выходящими из нее ребрами, не нарушив связности графа.
Как решить?