Деревья — Вероятность и статистика, 8 класс

Свойства деревьев: единственность пути, висячие вершины, число рёбер. 100 заданий на отработку.

Простыми словами

Генеалогическое древо, папки на компьютере, схема «турнир на выбывание» — всё это деревья: от любого места до любого другого можно добраться, причём ровно одним путём, и нигде нельзя «ходить по кругу».

Граф — набор точек (вершин), часть которых соединена линиями (рёбрами). Дерево — связный граф (из любой вершины можно дойти до любой) без циклов (нет замкнутых путей).

Как выглядит дерево

Дерево:

7

вершин,

7 - 1 = 6

рёбер; закрашены иначе — висячие вершины

Степень вершины — число рёбер, выходящих из неё. Висячая вершина (лист) — вершина степени $1$ .

Свойства дерева

P = B - 1

B

— число вершин,

P

— число рёбер

Между любыми двумя вершинами существует ровно один путь.
В любом дереве (с двумя и более вершинами) есть хотя бы две висячие вершины.
Удаление любого ребра разбивает дерево на две части (связность теряется).
Добавление любого нового ребра между имеющимися вершинами создаёт цикл.

Дерево с $15$ вершинами: рёбер $15 - 1 = 14$ .
В дереве $12$ рёбер: вершин $12 + 1 = 13$ .
Граф: $10$ вершин и $10$ рёбер — не дерево (рёбер должно быть $9$ , значит есть цикл или граф несвязен).

Почему $B - 1$ ? Начнём с одной вершины. Каждое новое ребро «приводит» ровно одну новую вершину. Если вершин $B$ , то добавили $B - 1$ вершину, то есть $B - 1$ ребро.

Не перепутайте направление: рёбер меньше вершин на $1$ . По рёбрам вершины находят прибавлением единицы, по вершинам рёбра — вычитанием.

Дерево эксперимента

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

N = m^{k}

k

уровней, на каждом по

m

ветвей:

N

листьев (исходов)

4 уровня по 3 ветви: $3^{4} = 81$ исход. 2 уровня по 3 ветви: $3^{2} = 9$ .

Всего вершин в дереве с 2 уровнями по 4 ветви, считая корень: $1 + 4 + 16 = 21$ .

Если из вершины выходят две равновозможные ветви, вероятность каждой $\frac{1}{2} = 0, 5$ .

Каждое ребро соединяет две вершины, поэтому сумма степеней всех вершин равна удвоенному числу рёбер. В дереве с $B$ вершинами она равна $2 (B - 1)$ : при $B = 20$ это $38$ .

Примеры заданий

Это несколько заданий из тренажёра, остальные — в тренажёре в начале страницы.

Сколько рёбер в дереве с 15 вершинами?

Показать ответ

Ответ: 14
Решение. В дереве рёбер на одно меньше, чем вершин.

В дереве 12 рёбер. Сколько в нём вершин?

Показать ответ

Ответ: 13
Решение. 12 + 1 = 13.

Сколько путей соединяет две вершины дерева?

Показать ответ

Ответ: 1
Решение. В дереве путь между любыми двумя вершинами единственный.

Есть ли в дереве циклы? Введите 1, если есть, и 0, если нет.

Показать ответ

Ответ: 0
Решение. Дерево — связный граф без циклов.

Сколько висячих вершин минимум в дереве с 9 вершинами?

Показать ответ

Ответ: 2
Решение. У любого дерева есть хотя бы две вершины степени 1.

Дерево эксперимента: 2 уровня по 2 ветви. Сколько исходов?

Показать ответ

Ответ: 4
Решение. 2² = 4.

Сколько рёбер надо удалить из дерева с 10 вершинами, чтобы оно распалось на две части?

Показать ответ

Ответ: 1
Решение. Любое ребро дерева — мост.

Связный граф с 6 вершинами и 5 рёбрами — это…

цикл
дерево
полный граф
ориентированный граф

Показать ответ

Ответ: дерево
Решение. Столько рёбер бывает только у дерева.