|
|
 |
Условие
Доказать, что
а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
б) в дереве с n вершинами ровно n – 1 ребро;
в) в дереве не меньше двух висячих вершин;
г) в связном графа из n вершин не меньше n – 1 ребра;
д) если в связном графе n вершин и n – 1 ребро, то он – дерево.
Решение
а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.
б) У дерева есть висячая вершина (см. задачу 30786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию n – 1 раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было n – 1.
в) Выйдем из висячей вершины и пойдём по графу как в задаче 30786. Так же как и там этот путь закончится в другой висячей вершине.
г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве n – 1 вершина, а в иcходном – не меньше.
д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).
Источники и прецеденты использования
| книга | |
| Автор | Иванов С.В. |
| Название | Математический кружок |
| глава | |
| Номер | 5 |
| Название | Графы |
| Тема | Теория графов |
| задача | |
| Номер | 30 |
