ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 31098
Темы:    [ Связность и разложение на связные компоненты ]
[ Деревья ]
Сложность: 3
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

Доказать, что
  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
  б) в дереве с n вершинами ровно  n – 1  ребро;
  в) в дереве не меньше двух висячих вершин;
  г) в связном графа из n вершин не меньше  n – 1  ребра;
  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.


Решение

  а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.

  б) У дерева есть висячая вершина (см. задачу 30786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию  n – 1  раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было  n – 1.

  в) Выйдем из висячей вершины и пойдём по графу как в задаче 30786. Так же как и там этот путь закончится в другой висячей вершине.

  г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве  n – 1  вершина, а в иcходном – не меньше.

  д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).

Источники и прецеденты использования

книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 5
Название Графы
Тема Теория графов
задача
Номер 30

© 2004-... МЦНМО (о копирайте)
     
Пишите нам
Rambler's Top100

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .