Главная → Уроки → Вероятность и статистика 8 класс

§ 16. Свойства деревьев

Прочитай параграф о свойствах деревьев: почему любые две вершины дерева соединены единственной цепью, что происходит с графом, если убрать из него ребро, какую вершину называют концевой и почему в конечном дереве рёбер всегда на одно меньше, чем вершин, — и ответь на 10 вопросов.

Не понял параграф? Бесплатный ИИ-репетитор по вероятности и статистике 8 класс объяснит по шагам, но готовый ответ не скажет.

Спросить репетитора
Два чертежа. а) Пять вершин A, B, C, D, E; зелёная ломаная A—C—D—B — цепь из A в B, внизу серым пунктиром показано убранное ребро AB, под ним красный крестик. б) Тот же граф, ребро AB вернули красной линией: ломаная A—C—D—B и ребро AB вместе замкнулись в цикл
Рис. 1. Свойство 1 от противного: вернули убранное ребро — получился цикл

В прошлом параграфе мы условились называть деревом связный граф без циклов. Требований всего два, но вместе они дают неожиданно много: не глядя на чертёж, можно сказать, сколько в дереве рёбер, найдётся ли в нём вершина с единственным ребром и что случится, если убрать хотя бы одну связь. Разберём эти свойства по порядку — они пригодятся и в схеме водопровода, и в дереве случайного опыта.

Между двумя вершинами — только одна дорога

Дерево связно, значит, из любой вершины по рёбрам можно добраться до любой другой. Спросим строже: а сколькими способами? Пусть из вершины X в вершину Y ведут два разных маршрута. Пройдём по первому туда, по второму обратно — получится замкнутый путь, то есть цикл. А циклов в дереве нет. Противоречие, значит, маршрут только один.

Теорема. Любые две вершины в дереве соединены единственной цепью.

Вот чем дерево удобно на практике: дорогу между двумя точками не приходится выбирать, она единственная. По той же причине вода из водонапорной башни доходит до каждого дома ровно одним путём, а не двумя.

Свойство 1. Убрали ребро — потеряли связность

Первое свойство звучит так: стоит выбросить из дерева любое ребро, и граф перестаёт быть связным. Докажем его от противного. Предположим, что мы выбросили ребро AB, а граф всё же остался связным. Тогда из A в B по-прежнему ведёт какая-то цепь — на рисунке 1, а она показана зелёным. Теперь поставим ребро AB обратно: перед нами снова исходное дерево, но зелёная цепь вместе с этим ребром замкнулась в цикл (рис. 1, б). А в дереве циклов не бывает — противоречие.

Хочешь больше времени в телефоне?

В Family Track телефон открывается за уроки: прочитал параграф, сдал тест и получил минуты. Сколько минут стоит урок, решают родители. Отправь им ссылку, пусть посмотрят.

Отправить родителямПройти урок бесплатно

Вопросы из теста

Правильные ответы и разбор ошибок — в приложении: при пересдаче вопросы меняются, поэтому списать не получится.

В дереве есть вершины X и Y. Сколько различных цепей ведёт из X в Y?

Сколько концевых вершин у дерева на рисунке?

Не получается разобраться? Бесплатный ИИ-репетитор по вероятности и статистике 8 класс разберёт ошибку по шагам и не даст списать.

← § 15. Деревья§ 17. Дерево случайного эксперимента →