Задача
Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с n вершинами ровно n – 1 ребро;
в) в дереве не меньше двух висячих вершин;
г) в связном графа из n вершин не меньше n – 1 ребра;
д) если в связном графе n вершин и n – 1 ребро, то он – дерево.
Решение
а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом. б) У дерева есть висячая вершина (см. задачу 130786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию n – 1 раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было n – 1. в) Выйдем из висячей вершины и пойдём по графу как в задаче 130786. Так же как и там этот путь закончится в другой висячей вершине. г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве n – 1 вершина, а в иcходном – не меньше. д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь