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




Докажите, что в дереве есть вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).
спросил 13 Фев, 19 от цельсия в категории школьный раздел


решение вопроса

+8
Рассмотрим произвольную вершину дерева и пойдем по любому выходящему из нее ребру в другую вершину. Если из новой вершины больше ребер не выходит, то мы остаёмся в ней, а в противном случае идём по любому другому ребру дальше. В этом путешествии мы никогда не сможем попасть в вершину, в которой уже побывали: это означало бы наличие цикла. Так как у графа конечное число вершин, то наше путешествие когда-нибудь закончится. Но закончиться оно может только в висячей вершине
ответил 13 Фев, 19 от аминна

Связанных вопросов не найдено

Обучайтесь и развивайтесь всесторонне вместе с нами, делитесь знаниями и накопленным опытом, расширяйте границы знаний и ваших умений.

Популярное на сайте:

Как быстро выучить стихотворение наизусть? Запоминание стихов является стандартным заданием во многих школах. 

Как научится читать по диагонали? Скорость чтения зависит от скорости восприятия каждого отдельного слова в тексте. 

Как быстро и эффективно исправить почерк?  Люди часто предполагают, что каллиграфия и почерк являются синонимами, но это не так.

Как научится говорить грамотно и правильно? Общение на хорошем, уверенном и естественном русском языке является достижимой целью.