Участник:Бушенкова Ксения/Решения задач/Остовное дерево

Материал из DISCOPAL
< Участник:Бушенкова Ксения
Версия от 22:23, 5 мая 2020; Бушенкова Ксения (обсуждение | вклад) (Новая страница: «http://discopal.ispras.ru/%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

http://discopal.ispras.ru/%D0%9F%D1%80%D0%B8%D0%B1%D0%BB%D0%B8%D0%B6%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%BB%D1%8F_%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B9_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D0%B5%D1%80%D0%B0/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/%D0%A7%D0%B5%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D1%81%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D0%B8_%D0%B2_MST

Почему множество всех вершин нечётной степени в остовном дереве Т чётно?

Сначала докажем , что в дереве есть висячая вершина(вершина, из которой выходит одно ребро).

Нам нужно рассмотреть произвольную вершину дерева.Из этой вершины по любому ребру пойдём в другую вершину.Если из вершины, в которую мы перешли, больше не выходит рёбер , то мы в ней останемся.Если есть вершины, то мы идём по дюбому другому ребру.Мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. У графа конечное число вершин, поэтому когда-нибудь мы остановемся. Но закончиться оно может только в висячей вершине.

В дереве с n вершинами ровно n – 1 ребро.

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

Степень вершины -сколько рёбер выходит из него. У нас n-1 ребро. То есть (n-1)-нечётно. Значит т чётно.