Свойства дерева: единственность пути, существование висячей вершины, связь между числом вершин и числом рёбер
Вспомним! Что такое дерево
Дерево — это связный граф без циклов. Три главных свойства, которые мы сегодня доказываем и применяем:
Между любыми двумя вершинами существует единственный путь .
В любом дереве есть хотя бы одна висячая вершина (вершина степени 1).
В дереве с n вершинами ровно n −1 рёбер.
Как пользоваться формулой. Если граф — дерево, Е — количество ребер, V - количество вершин, то E = V −1 (рёбер на одно меньше, чем вершин).
Эта формула работает и «в обратную сторону»: она помогает проверить, является ли граф деревом.
Свойство 1: единственность пути
Между любыми двумя вершинами дерева существует ровно один путь.
Доказательство:
1. Путь существует. Дерево — связный граф по определению, а связность и означает, что между любыми двумя вершинами есть хотя бы один путь.
2. Путь только один. Предположим противное: между вершинами A и B есть два разных пути P 1 и P 2 . Тогда, пройдя из A в B по пути P 1 и вернувшись из B в A по пути P 2 , мы получим замкнутый маршрут. Если два пути действительно различны, где-то они расходятся и сходятся снова — а это значит, что в графе образуется цикл .
Но в дереве циклов нет — противоречие. Значит, путь единственный.
Пример: если бы между двумя сёлами в дереве (без петель на дорогах) вели две разные дороги, то, выехав по одной и вернувшись по другой, мы сделали бы «круг» — а кругов в дереве не бывает.
Пример:
В этом графе между вершинами 1 и 4 два пути:
1—2—4 и 1—3—4 .
Пути два → их замыкание даёт цикл
1—2—4—3—1 → граф не дерево .
Свойство 2: существование висячей вершины
В любом дереве есть хотя бы одна вершина степени 1 (висячая вершина).
Вспомним! Степенью вершины называется количество ребер, из нее выходящих. Следовательно висячая вершина это вершина, из которой выходит ровно одно ребро.
На рисунке вершины Г, Д, Е и Ж - висячие
Доказательство (метод «иди и не возвращайся»)
Возьмём любую вершину дерева и начнём из неё идти по рёбрам, не поворачивая назад (не возвращаясь в вершину, из которой только что пришли).
Вершин в дереве конечное число, значит, рано или поздно мы не сможем идти дальше.
Остановиться мы можем только в такой вершине, из которой выходит одно ребро — то, по которому мы пришли (если бы выходили и другие рёбра, мы бы пошли дальше по одному из них; повернуть назад нам не разрешают правила движения).
Вершина, из которой выходит ровно одно ребро, — это и есть висячая вершина.
Пример: Допустим мы выходим из вершины 1: А—Б—Г. Дальше пути нет.
Вершина Г — висячая
Почему нельзя застрять где-то ещё?
Если в текущей вершине степень 2 или больше, значит, кроме ребра «откуда пришли», есть ещё хотя бы одно ребро «вперёд» — по нему и идём. Застрять можно только там, где рёбер, кроме «обратного», нет — то есть при степени 1.
А цикла при этом не образуется, потому что мы в дереве и, не возвращаясь назад, просто не можем прийти в вершину повторно (иначе возник бы цикл).
Пример: В вершине А степень равна 2, значит, можно идти дальше.
Дальше можно выбрать вершины Б или В, степень каждой из которых равна 3 и можно идти дальше. Из вершины Б можно пойти в вершины Г или Д, а из вершины В в вершины Е или Ж, у каждой из которых степень равна 1.
То есть в вершинах Г, Д, Е и Ж будет остановка, они висячие.
Свойство 3: число рёбер E на 1 меньше числа вершин V: E=V-1
В дереве с n вершинами ровно n −1 ребро.
Пример: На рисунке дерево с 7 вершинами (А, Б, В, Г, Д, Е, Ж) и 6 ребрами (А-Б, А-В, Б-Г, Б-Д, В-Е, В-Ж).
Доказательство методом математической индукции (база и шаг)
База. Дерево из одной вершины: n =1 , рёбер 0. Формула E = n −1=0 верна.
Возьмём дерево с n вершинами.
По свойству 2 в нём есть висячая вершина X (степени 1).
Шаг. Пусть для всех деревьев с числом вершин меньше n формула верна.
Доказательство формулы:
Отрежем её: удалим вершину X и единственное выходящее из неё ребро. Граф остался связным (мы удалили «лист дерева», через который ничего не проходило) и по-прежнему без циклов — значит, это снова дерево.
В новом дереве n −1 вершина и E −1 рёбер. По предположению индукции: E −1=( n −1)−1. Отсюда E = n −1 .
Интуиция: каждое новое ребро дерева «приносит» ровно одну новую вершину. Начали с одной вершины — построили цепочку: +1 ребро — +1 вершина. Поэтому рёбер всегда на одно меньше, чем вершин.
Применение: проверка, является ли граф деревом
Граф является деревом тогда и только тогда, когда выполнены два условия сразу :
- Граф связный (из любой вершины можно пройти в любую другую).
- Рёбер ровно на одно меньше числа вершин: E = V −1 .
Дополнительная быстрая проверка:
- у дерева нет циклов, а значит, оно обязано иметь висячую вершину (свойство 2).
- Если у графа E = V −1 , но он не связный — он состоит из нескольких «кусков»-деревьев (лес), или где-то обязательно есть цикл.
Пример: На рисунке у графа 7 вершин и 6 ребер, но он несвязный: тогда у него есть цикл: В − Е − Ж
Задача 1 (проверка по формуле)
В графе 10 вершин и 9 рёбер, граф связный.
Является ли он деревом?
Решение. Проверяем:
E =9 ,
V −1=10−1=9 .
Формула выполнена, граф связный → это дерево.
Ответ: да.
Задача 2 (ловушка)
В графе 8 вершин и 7 рёбер. Является ли он деревом?
Решение. Формула E = V −1 выполнена, но про связность мы ничего не знаем.
Контрпример: не связный граф из двух частей — цикл «треугольник» (3 вершины, 3 ребра) и дерево из 5 вершин (4 ребра). Всего 8 вершин и 3+4=7 рёбер, но граф несвязный и, значит, он содержит цикл — деревом он не является.
Ответ: нет, обязательно нужно ещё проверить связность.
Задача 3 (подсчёт)
В графе, который является деревом, 15 вершин.
Сколько у него рёбер?
Решение.
E =15−1=14 .
Ответ: 14 рёбер.
Задача 4 (обратная)
У дерева 12 рёбер. Сколько у него вершин?
Решение.
V = E +1=13 .
Ответ: 13 вершин.
Задача 5 (на висячие вершины)
Существует ли дерево, у которого 6 вершин, одна из которых степени 3, одна степени 2, остальные вершины висячие?
Решение: Пусть висячих вершин равно х, каждая степени 1.
По свойству 3 у дерева 5 рёбер.
Сумма степеней всех вершин равна удвоенному числу рёбер: 3+2+х⋅1=2⋅5=10,
Тогда х=10-5=5.
Получается, что у дерева 5 висячих вершин, одна вершина степени 3, одна вершина степени 2.
5+1+1=7, то есть у дерева с такими условиями должно быть 7 вершин, а унас по условию задачи их 6: 7≠6,
Ответ: Нет, такого дерева не существует
Типичные ошибки
«Формула E = V −1 гарантирует дерево».
Нет! Она работает только вместе со связностью (см. задачу 2).
«Висячая вершина — это вершина степени 0».
Нет: висячая вершина — степени 1 . Вершина степени 0 — изолированная, в дереве с числом вершин больше 1 изолированных вершин быть не может (граф связный).
Забывают удвоение суммы степеней. Сумма степеней всех вершин любого графа равна удвоенному числу рёбер:
∑ deg( v )=2 E . Это удобный инструмент для задач типа 5.
Путают «есть путь» с «есть неколько путей». В генеалогическом древе между предком и потомком ровно одна «цепочка родства» — это и есть следствие свойства 1.
Решите самостоятельно
- В дереве 20 вершин. Сколько рёбер?
- Граф связный, у него 25 рёбер и 26 вершин. Является ли он деревом?
- В дереве 8 вершин: одна вершина степени 4, одна степени 3. Сколько висячих вершин может быть в этом графе?
- Может ли в дереве быть ровно 2 вершины степени 3 и ни одной висячей? Ответ обоснуйте
Вопросы для рефлексии
- Почему два разных пути между одними и теми же вершинами означают наличие цикла?
- Где в доказательстве свойства 3 используется свойство 2 (висячая вершина)?
- Какие два условия нужно проверить, чтобы убедиться, что граф — дерево?