Деревья
Загрузка…
Загрузка…
Дерево — это граф особого вида: связный и без циклов. Так выглядят схема водопровода в посёлке, родословная семьи, схема турнира на выбывание и дерево исходов случайного опыта. В 8 классе по учебнику Высоцкого и Ященко «Вероятность и статистика» деревья изучают в главе X: как узнать дерево, сколько у него рёбер и висячих вершин, почему между двумя вершинами ровно одна цепь.
Граф называют связным, если из любой его вершины можно пройти по рёбрам в любую другую. Цикл — это замкнутая цепочка рёбер без повторяющихся вершин: можно выйти из вершины и вернуться в неё, не повторяя пути. Дерево — связный граф без циклов. Чтобы проверить рисунок, ответьте на два вопроса: «Связен ли граф?» и «Есть ли в нём цикл?». Дерево получается только при ответах «да» и «нет». Цепочка вершин тоже дерево, и одна-единственная вершина без рёбер — простейшее дерево.
Пример. На рисунке изображён граф. Является ли он деревом?
Граф связный: из любой вершины можно дойти до любой
В графе нет циклов
Связный и без циклов — это дерево
Ответ: Да.
Пример. На рисунке изображён граф. Является ли он деревом?
Граф не связный: в нём 2 части
В графе есть цикл
Граф не связный — это не дерево
Ответ: Нет.
Пример. На рисунке изображён граф, который не является деревом. Почему?
Граф связный: из любой вершины можно дойти до любой
В графе есть цикл
В графе есть цикл
Ответ: В графе есть цикл.
В конечном дереве рёбер на 1 меньше, чем вершин: если вершин n, то рёбер n − 1. Объяснение простое: можно по одной убирать висячие вершины вместе с их ребром, пока не останется одна вершина без рёбер. Поэтому если известно число рёбер m, то вершин m + 1.
Пример. В дереве 13 вершин. Сколько в нём рёбер?
Рёбер на 1 меньше, чем вершин: рёбра = n − 1
Рёбер: 13 − 1 = 12
Ответ: 12.
Пример. В дереве 6 рёбер. Сколько в нём вершин?
Вершин на 1 больше, чем рёбер: вершины = m + 1
Вершин: 6 + 1 = 7
Ответ: 7.
Пример. В дереве 23 вершины. Из него убрали одну висячую вершину вместе с её ребром. Сколько рёбер в получившемся дереве?
Вершин осталось: 23 − 1 = 22
Рёбер осталось: 22 − 1 = 21
Ответ: 21.
Пример. На рисунке изображено дерево. Сколько в нём рёбер?
Вершин: n = 6
Рёбер: 6 − 1 = 5
Ответ: 5.
Висячей (концевой) называют вершину, из которой выходит ровно одно ребро, то есть вершину степени 1. В конечном дереве, где есть хотя бы одно ребро, висячие вершины есть всегда, и не меньше двух. Больше всего висячих вершин у «звезды»: у неё n − 1 висячих, а наименьшее число, 2, у цепочки. Верхняя вершина дерева на рисунке тоже может быть висячей, если из неё выходит одно ребро.
Пример. На рисунке изображено дерево. Сколько в нём висячих вершин?
Висячие вершины: C, D, E, F
Их 4
Ответ: 4.
Пример. На рисунке изображено дерево. Какая из вершин A, E, F не является висячей?
Степени: A — 2, E — 1, F — 1
A — не висячая
Ответ: A.
Пример. В дереве 8 вершин. Какое наименьшее число висячих вершин может быть в таком дереве?
Меньше всего висячих у цепочки: у неё два конца
Висячих вершин: 2
Ответ: 2.
Пример. В дереве 41 вершина. Какое наибольшее число висячих вершин может быть в таком дереве?
Больше всего висячих у «звезды»: центр и n − 1 лучей
Висячих вершин: 40
Ответ: 40.
В дереве с n вершинами n − 1 ребро. Если в связном графе с n вершинами m рёбер, то лишних m − (n − 1) рёбер, и столько нужно удалить. Удаляют рёбра, лежащие на циклах: тогда граф остаётся связным, а циклов становится меньше.
Пример. На рисунке изображён связный граф. Сколько рёбер нужно удалить, чтобы он стал деревом?
Вершин: n = 5
Рёбер: m = 7
В дереве рёбер: 5 − 1 = 4
Удалить: 7 − 4 = 3
Ответ: 3.
Пример. Связный граф имеет 15 вершин и 17 рёбер. Сколько рёбер нужно удалить, чтобы получилось дерево?
Останется рёбер: 15 − 1 = 14
Убрать: 17 − 14 = 3
Ответ: 3.
Пример. Между 12 городами проложено 17 дорог, из любого города можно доехать в любой. Какое наибольшее число дорог можно закрыть, чтобы по-прежнему можно было доехать из любого города в любой?
Останется рёбер: 12 − 1 = 11
Убрать: 17 − 11 = 6
Ответ: 6.
Цепь — это путь по рёбрам без повторяющихся вершин. В дереве любые две вершины соединены единственной цепью: она есть, потому что граф связен, и она одна, потому что цикла нет. Если в графе есть цикл, то у двух вершин на этом цикле цепей уже две — по одной и по другой его части.
Пример. На рисунке изображено дерево. Какая цепь ведёт из C в G?
В дереве между двумя вершинами ровно одна цепь
Цепь: C–A–B–E–G
Ответ: C–A–B–E–G.
Пример. На рисунке изображён граф. Сколько существует цепей (путей без повторяющихся вершин), ведущих из вершины A в вершину C?
В графе есть цикл: это не дерево
Цепей из A в C: 2
Ответ: 2.
Сумма степеней всех вершин любого графа вдвое больше числа рёбер: у каждого ребра два конца. У дерева с n вершинами рёбер n − 1, поэтому сумма степеней равна 2(n − 1). Если известны степени всех вершин, кроме висячих, число висячих находят из уравнения для суммы степеней.
Пример. На рисунке изображено дерево. Чему равна сумма степеней всех его вершин?
Рёбер: 7 − 1 = 6
Сумма степеней: 2 · 6 = 12
Ответ: 12.
Пример. В дереве есть 2 вершины степеней 5, 5, все остальные вершины — висячие. Сколько в дереве висячих вершин?
Сумма степеней этих вершин: 5 + 5 = 10
10 + k = 4 + 2k − 2
k = 10 − 4 + 2 = 8
Ответ: 8.
Деревья встречаются и в житейских задачах. В турнире на выбывание каждый матч «убирает» одну команду, поэтому матчей на 1 меньше, чем команд. Схема водопровода без колец — дерево: участков труб на 1 меньше, чем зданий. В родословной число предков удваивается с каждым поколением.
Пример. В турнире на выбывание участвуют 8 команд: проигравший матч выбывает, ничьих нет. Сколько матчей надо сыграть, чтобы определить победителя?
В каждом матче выбывает одна команда
Матчей: 8 − 1 = 7
Ответ: 7.
Пример. В посёлке есть водонапорная башня, 8 домов, гараж и школа. Трубы проложены так, что от башни к каждому зданию ведёт единственный путь (граф труб — дерево). Сколько всего участков труб проложено?
Вершин: 1 + 8 + 2 = 11
Участков: 11 − 1 = 10
Ответ: 10.
Пример. Родословное дерево: у каждого человека двое родителей, у каждого из них тоже двое, и так далее. Сколько всего предков у человека в 4 поколениях (родители — 1-е поколение, их родители — 2-е и так далее)?
В 4-м поколении: 2 · 2 · 2 · 2 = 16
Всего: 2 + 4 + 8 + 16 = 30
Ответ: 30.