Деревья

Загрузка…

Деревья: правила и примеры

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

Что такое дерево

Граф называют связным, если из любой его вершины можно пройти по рёбрам в любую другую. Цикл — это замкнутая цепочка рёбер без повторяющихся вершин: можно выйти из вершины и вернуться в неё, не повторяя пути. Дерево — связный граф без циклов. Чтобы проверить рисунок, ответьте на два вопроса: «Связен ли граф?» и «Есть ли в нём цикл?». Дерево получается только при ответах «да» и «нет». Цепочка вершин тоже дерево, и одна-единственная вершина без рёбер — простейшее дерево.

ABCDEF

Пример. На рисунке изображён граф. Является ли он деревом?

Граф связный: из любой вершины можно дойти до любой
В графе нет циклов
Связный и без циклов — это дерево
Ответ: Да.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Является ли он деревом?

Граф не связный: в нём 2 части
В графе есть цикл
Граф не связный — это не дерево
Ответ: Нет.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф, который не является деревом. Почему?

Граф связный: из любой вершины можно дойти до любой
В графе есть цикл
В графе есть цикл
Ответ: В графе есть цикл.

Разобрать по шагам →

Число рёбер дерева

В конечном дереве рёбер на 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.

Разобрать по шагам →
ABCDEF

Пример. На рисунке изображено дерево. Сколько в нём рёбер?

Вершин: n = 6
Рёбер: 6 − 1 = 5
Ответ: 5.

Разобрать по шагам →

Висячие вершины

Висячей (концевой) называют вершину, из которой выходит ровно одно ребро, то есть вершину степени 1. В конечном дереве, где есть хотя бы одно ребро, висячие вершины есть всегда, и не меньше двух. Больше всего висячих вершин у «звезды»: у неё n − 1 висячих, а наименьшее число, 2, у цепочки. Верхняя вершина дерева на рисунке тоже может быть висячей, если из неё выходит одно ребро.

ABCDEF

Пример. На рисунке изображено дерево. Сколько в нём висячих вершин?

Висячие вершины: C, D, E, F
Их 4
Ответ: 4.

Разобрать по шагам →
ABCDEF

Пример. На рисунке изображено дерево. Какая из вершин 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) рёбер, и столько нужно удалить. Удаляют рёбра, лежащие на циклах: тогда граф остаётся связным, а циклов становится меньше.

ABCDE

Пример. На рисунке изображён связный граф. Сколько рёбер нужно удалить, чтобы он стал деревом?

Вершин: 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.

Разобрать по шагам →

Единственная цепь в дереве

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

ABCDEFG

Пример. На рисунке изображено дерево. Какая цепь ведёт из C в G?

В дереве между двумя вершинами ровно одна цепь
Цепь: C–A–B–E–G
Ответ: C–A–B–E–G.

Разобрать по шагам →
ABCDE

Пример. На рисунке изображён граф. Сколько существует цепей (путей без повторяющихся вершин), ведущих из вершины A в вершину C?

В графе есть цикл: это не дерево
Цепей из A в C: 2
Ответ: 2.

Разобрать по шагам →

Степени вершин дерева

Сумма степеней всех вершин любого графа вдвое больше числа рёбер: у каждого ребра два конца. У дерева с n вершинами рёбер n − 1, поэтому сумма степеней равна 2(n − 1). Если известны степени всех вершин, кроме висячих, число висячих находят из уравнения для суммы степеней.

ABCDEFG

Пример. На рисунке изображено дерево. Чему равна сумма степеней всех его вершин?

Рёбер: 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.

Разобрать по шагам →

Частые ошибки

Тренажёр, самостоятельные и зачёт