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

0 голосов
38 просмотров

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


Математика (314 баллов) | 38 просмотров
Дан 1 ответ
0 голосов

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

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

(117 баллов)
0

А в вершину мы уткнемся, потому что ребер конечное число.

0

Это понятно, спасибо большое, а можешь еще помочь??

0

В смысле какой город?

0

Ну, у вас на мат. кружке задание дали ведь? Этого нет в школьной программе. Чем еще помочь?

0

Смотри в вопросах, а это не задача в принципе, это я к зачету готовлюсь))