Докажите, что если граф связен и не содержит циклов, то в нем n-1 ребро (n - кол-во вершин)

+ 0 -

Tim10

14 янв. 2014 г., 15:55:10 (10 лет назад)

Возьмем какую-либо вершину. Просто выбрали любую. Теперь "идем" по ребрам графа, не проходя по каждому ребру более 1 раза. Поскольку циклов нет, рано или поздно мы "упремся" в какую-нибудь вершину, у которой только 1 ребро, по которому мы в нее зашли. Заметим, что тогда ее степень равна 1. Возьмем и выкинем эту вершину и ее единственное ребро из графа. Теперь кол-во вершин в графе - n-1, а ребер m-1 (m - кол-во ребер в изначальном графе). При этом связности мы не испортили, т.к. у нее было только одно ребро, которое мы выкинули с этой же вершиной!
Проделаем ту же операцию. Таким образом мы уменьшаем кол-во ребер и вершин каждым шагом на 1. Рассмотрим граф, в котором осталось 2 вершины. Одна из этих вершин имеет степень 1. Значит и вторая тоже (при условии, что нет двойных ребер, но граф связен, поэтому их нет). Уберем последнюю "единичную" вершину. У нас осталась одна вершина и ни одного ребра. А значит вершин изначально было на 1 больше, чем ребер. Доказано.

P.S.: Где задачи достал(а)? Какой город?)