Введение в теорию графов · урок 4 из 4 · практикум

Практикум: дерево

Вероятность и статистика · 8 класс · базовый уровень
ФРП «Математика», Москва – 2025 · строка R05 · VIS8-022

1 мин · теория (орг. момент, тема урока)
Паспорт: R05 «Введение в теорию графов» (4 ч), урок 4/4, единица R05.1 «Дерево»; в практикуме повторяются R05.2 (свойства дерева) и R05.3 (правило умножения). Тип урока — П (практикум): теория — короткими сводками и одним демонстрационным примером, остальное время решают ученики. Опора — VIS8-019 (дерево), VIS8-020 (свойства дерева), VIS8-021 (правило умножения).
Хронометраж: Теория 12 мин · практика 33 мин (73 %), итого 45 мин.
Теория (12 мин): сл. 1–2 (тема, цели) 2 · 4 (сводка: дерево и его элементы) 3 · 6 (сводка: свойства дерева) 2,5 · 8 (сводка: дерево вариантов и правило умножения) 2 · 11 (демонстрационный пример: бинарное дерево бросаний монеты) 2,5.
Практика (33 мин): разминка (сл. 3) 2,5 · образцы → сам (сл. 5, 7, 9, 12) по 2,5, (сл. 10, 13) по 2 · типичные ошибки (сл. 14) 1,5 · найди ошибку (сл. 15) 2 · самопроверка, база (сл. 16) 3 · повышенный уровень (сл. 17) 2 · ОГЭ (сл. 18) 2 · самостоятельная работа (сл. 19) 5 · итог и ДЗ (сл. 20) 1.
Картинка на титуле — дерево из 12 вершин и 11 рёбер; розовые — 6 листьев (висячих вершин), бирюзовый — самый длинный путь (длина 6 — диаметр). Вопрос для начала урока: сколько рёбер станет, если добавить ещё один лист? (12.)
Если не успеваете: задания 3–4 сл. 17 и задание 3 сл. 13 — в ДЗ; сводки теории не сокращать.

R05.1 · R05.2 · R05.3

Цели урока

Сегодня вы научитесь

Читать дерево

находить листья, пути, их длину и диаметр дерева (ПР-5)

Считать вершины и рёбра

$n$ вершин — $n - 1$ ребро; сумма степеней (ПР-5)

Строить дерево вариантов

перечислять пути и применять правило умножения (ПР-5)

Находить вероятности

по бинарному дереву бросаний монеты (ПР-4)

1 мин · теория
ПР-5 (= REQ-5.5): «Использовать графические модели: дерево случайного эксперимента, диаграммы Эйлера, числовая прямая». ПР-4 (= REQ-5.4): «Находить вероятности случайных событий в опытах… с равновозможными элементарными событиями». Элемент содержания EL-5.7: «Дерево. Свойства деревьев: единственность пути, существование висячей вершины, связь между числом вершин и числом рёбер. Правило умножения. Решение задач с помощью графов».

повторение: VIS8-019 – VIS8-021

Разминка · устно

Дерево или нет? Считаем быстро

Какой из графов — дерево? а)
Почему б) — не дерево? есть цикл
Почему в) — не дерево? несвязный

В дереве $7$ вершин. Рёбер? $6$
В дереве $10$ рёбер. Вершин? $11$
Сколько путей между двумя вершинами дерева? $1$
$3 \cdot 4 \cdot 2$ $24$
Сумма степеней вершин графа с $5$ рёбрами $10$

2,5 мин · практика
1) а) — связный граф без циклов (5 вершин, 4 ребра). 2) б): четыре вершины образуют цикл (квадрат), 5 вершин и 5 рёбер. 3) в): две отдельные части — граф несвязный (6 вершин, 4 ребра); каждая часть — дерево, но весь граф — нет.
4) 7 − 1 = 6. 5) 10 + 1 = 11. 6) Ровно один путь (свойство дерева, VIS8-020). 7) 24 — правило умножения (VIS8-021). 8) Каждое ребро добавляет 1 к степени двух вершин: 2 · 5 = 10.
Задания 4, 5, 8 — подготовка к сл. 7 (листья по степеням), задание 7 — к сл. 8–10.

R05.1

Теория · сводка · дерево и его элементы

Дерево — связный граф без циклов

Дерево: из любой вершины можно дойти в любую, циклов нет.

Лист (висячая вершина) — вершина степени $1$ : Г, Ж, З, И, К.

Путь З — Д — Б — А — В — Е — К; длина пути — число рёбер: $6$ .

Диаметр дерева — длина самого длинного пути: здесь

6

3 мин · теория
Сводка уроков VIS8-019, VIS8-020. Дерево — связный граф без циклов. Ветвь — часть дерева, отходящая от вершины. Висячая вершина (лист) — вершина степени 1.
По клику подсвечиваются листья (5 штук: Г, Ж, З, И, К), затем путь З → К. Длина пути — число рёбер, а не вершин: на пути 7 вершин и 6 рёбер. Самый длинный путь в этом дереве имеет длину 6 (ещё один такой: И → К) — это диаметр дерева.
Вопросы классу: какова степень вершины Б? (3.) Какая длина пути Г → Ж? (4: Г — Б — А — В — Ж.) Сколько рёбер в этом дереве? (10 вершин → 9 рёбер, можно пересчитать.)

R05.1

Образец → сам · пути и диаметр

Путь в дереве — единственный

Образец: найдите путь из $1$ в $10$ и его длину

от $10$ идём назад: $10 \to 8 \to 6 \to 4$ лист — одно ребро

от $1$ : $1 \to 3 \to 4$ — встретились в $4$

путь $1346810$ , длина $5$ считаем рёбра

Сам: по тому же дереву

Длина пути из $2$ в $7$ $4$
Сколько листьев? $5$
Найдите диаметр дерева $5$
Через какие вершины проходят все пути из $1$ и $2$ в $5$ , $6$ , $7$ , $8$ ? $3$ и $4$

2,5 мин · практика
Образец: путь в дереве единственный, поэтому его можно искать с двух концов до встречи. 1 — 3 — 4 — 6 — 8 — 10: 6 вершин, 5 рёбер; длина 5. По клику путь подсвечивается на рисунке.
1) 2 — 3 — 4 — 5 — 7: длина 4. 2) Листья: 1, 2, 7, 9, 10 — 5. 3) Самые длинные пути: 1 → 10, 2 → 10, 7 → 10 — длина 5; длиннее нет (проверено перебором всех пар вершин), диаметр 5. 4) Все такие пути идут через 3 и 4 (ребро 3 — 4 — «мост»: удалите его — дерево распадётся на две части).

R05.2

Теория · сводка · свойства дерева

Три свойства, которые работают в задачах

Путь — единственный

Новое ребро между вершинами дерева даёт второй путь — появляется цикл.

Есть висячая вершина

Концы самого длинного пути — листья. Листьев не меньше $2$ (если вершин $\geq 2$ ).

$n$ вершин — $n - 1$ ребро

Убрали лист — ушли $1$ вершина и $1$ ребро. Сумма степеней $= 2 \cdot (рёбер)$ .

2,5 мин · теория
Сводка урока VIS8-020. 1) Если бы между двумя вершинами было два разных пути, вместе они дали бы цикл. По клику на первом рисунке добавляется пунктирное ребро — граф уже не дерево.
2) Возьмём самый длинный путь (фиолетовый). Если бы у его конца было ещё одно ребро, путь можно было бы продлить (цикла нет, вернуться нельзя). Значит, концы — висячие вершины.
3) Убираем лист вместе с его ребром — снова дерево, вершин и рёбер стало на 1 меньше; дойдём до одной вершины без рёбер. Значит, рёбер всегда на 1 меньше, чем вершин. Подписи «2 — 1» и т. д.: вершин — рёбер.
Сумма степеней = удвоенное число рёбер (каждое ребро считается у двух концов) — пригодится на следующем слайде.

R05.2

Образец → сам · число вершин и рёбер

Листья — через сумму степеней

Образец: в дереве $4$ вершины степени $3$ , остальные — листья. Сколько листьев?

листьев $x$ : вершин $4 + x$ , рёбер $3 + x$ $n - 1$

$4 \cdot 3 + x = 2 (3 + x)$ сумма степеней

$12 + x = 6 + 2 x$ , $x =$ $6$ рисунок: $6$ розовых

Сам

В дереве $15$ вершин. Рёбер? $14$
Граф: $8$ вершин, $8$ рёбер. Может ли он быть деревом? нет
$3$ вершины степени $4$ , остальные — листья. Сколько всего вершин? $11$
Связный граф: $10$ вершин, $12$ рёбер. Сколько рёбер удалить, чтобы получилось дерево? $3$

R05.3

Теория · сводка · дерево вариантов и правило умножения

Каждый вариант — путь от корня к листу

Футболка — Б или С; шорты — Ч, Д или З. Сколько комплектов?

2 \cdot 3 = 6

листьев

Первый выбор —

m

способов, после каждого второй —

n

способов: всего

m \cdot n

Путь к листу единственный — варианты не повторяются и не теряются

2 мин · теория
Сводка урока VIS8-021. Корень — начало выбора; первый уровень — футболка (белая Б, синяя С), второй — шорты (чёрные Ч, джинсовые Д, зелёные З). Листья перечисляются по клику: БЧ, БД, БЗ, СЧ, СД, СЗ.
Почему умножение, а не сложение: от каждой из 2 вершин первого уровня отходит по 3 ветви, листьев 3 + 3 = 2 · 3. Для трёх выборов — m · n · k.
Связь со свойством «путь единственный»: каждому листу соответствует ровно один путь от корня — поэтому, перечисляя листья, мы перечисляем все варианты ровно по одному разу.

R05.1 · R05.3

Образец → сам · дерево вариантов

Перебор по дереву: ничего не пропустить

Образец: двузначные числа из цифр $0, 1, 2$ без повторений

1-я цифра: $1$ или $2$ с нуля число не начинается

2-я — любая из $2$ оставшихся: $2 \cdot 2 =$ $4$

Сам: постройте дерево, сосчитайте

Трёхзначные числа из цифр $1, 2, 3$ без повторений $6$
Двузначные числа из цифр $0, 5, 7$ (цифры могут повторяться) $6$
Двузначные чётные числа из цифр $1, 2, 3, 4$ без повторений $6$

R05.3

Образец → сам · правило умножения

Дерево большое — рисуем одну ветку

Образец: $3$ салата, $4$ горячих, $2$ десерта. Сколько обедов из трёх блюд?

из корня $3$ ветви, из каждой — по $4$ , из каждой — по $2$

листьев $3 \cdot 4 \cdot 2 =$ $24$ правило умножения

Сам: сколько вариантов?

Код из $3$ цифр (от $0$ до $9$ ) $1000$
Флаг из $3$ полос, цвета — из $4$ , все полосы разные $24$
Флаг из $3$ полос, цвета — из $5$ , соседние полосы разные $80$

R05.1 · R05.3

Теория · демонстрационный пример · бинарное дерево

Монету бросают $3$ раза: из каждой вершины — $2$ ветви

Обход «сначала О, потом Р»: листья идут по порядку ООО, ООР, …, РРР —

2 \cdot 2 \cdot 2 = 8

исходов

2,5 мин · теория (учитель показывает и комментирует)
Бинарное дерево: из каждой не висячей вершины выходят ровно 2 ветви (О — орёл, Р — решка). На уровнях 1, 2, 4, 8 вершин (числа справа появляются по клику) — каждый бросок удваивает число путей.
Обход дерева: из каждой вершины сначала идём по ветви О, потом по ветви Р. Тогда листья выписываются по порядку: ООО, ООР, ОРО, ОРР, РОО, РОР, РРО, РРР — ничего не пропущено.
Вопросы классу: сколько всего вершин в дереве? (1 + 2 + 4 + 8 = 15.) Сколько рёбер? (14 — на одно меньше, свойство дерева.) Какой путь ведёт к листу РОР? (Р, затем О, затем Р.)
Все 8 исходов равновозможны — значит, вероятность события = (число нужных листьев) / 8. Это используем на сл. 12 и 18.

R05.1 · R05.3

Образец → сам · пути в бинарном дереве

Отмечаем нужные листья

Образец: в скольких исходах трёх бросаний орёл выпал ровно $2$ раза?

нужные листья: ООР, ОРО, РОО — $3$ из $8$

$P = \frac{3}{8} = 0, 375$ исходы равновозможны

Сам: монету бросают $4$ раза

Сколько листьев у дерева? $16$
В скольких исходах ровно одна решка? $4$
Сколько всего вершин в дереве? $31$

R05.1 · R05.2

Образец → сам · задача из жизни · турнирная сетка

Олимпийская система — это дерево

Образец: $8$ команд, проигравший выбывает. Сколько матчей?

каждый матч выбивает $1$ команду; выбыть должны $7$

матчей $7$ , туров $3$ $8 \to 4 \to 2 \to 1$

Сам

$16$ команд: сколько матчей? $15$
$32$ команды: сколько туров? $5$
$20$ теннисистов (часть пропускает 1-й тур): сколько матчей? $19$

R05.1 · R05.2 · R05.3

Осторожно · типичные ошибки

Неверно → почему → верно

Где ошибаются	Неверно	Верно
рёбер столько же, сколько вершин	$12$ вершин → $12$ рёбер	$12 - 1 = 11$ рёбер
« $n - 1$ ребро — значит, дерево»	$4$ вершины, $3$ ребра — дерево	нужна ещё связность: здесь цикл
длина пути — число вершин	путь А — Б — В: длина $3$	рёбер $2$ : длина $2$
сложили вместо умножения	$3$ супа, $4$ вторых: $3 + 4 = 7$	$3 \cdot 4 = 12$ обедов

R05.1 · R05.2 · R05.3

Найди ошибку

Где ошибся ученик?

а) В дереве $2$ вершины степени $3$ , остальные — листья. Сколько листьев?

листьев $x$ , рёбер $2 + x$

$6 + x = 2 (2 + x)$ , $x = 2$

рёбер на $1$ меньше вершин: $1 + x$

$6 + x = 2 + 2 x$ , $x = 4$

б) Монету бросают $3$ раза. В скольких исходах есть хотя бы один орёл?

ОРР, РОР, РРО — $3$ исхода

это «ровно один орёл»; а годятся и два, и три

все, кроме РРР: $8 - 1 = 7$

в) Длина пути

вершин $5$ — длина $5$

длина — число рёбер

рёбер $4$ , длина $4$

2 мин · практика
Сначала видны только «решения ученика» (красным); 1 мин в парах — найти ошибку, затем открывать исправления.
а) Вершин 2 + x, рёбер 2 + x − 1 = 1 + x. Сумма степеней 2 · 3 + x = 2(1 + x) ⇒ x = 4. Проверка: две соединённые вершины, у каждой ещё по 2 листа — 6 вершин, 5 рёбер, 3 + 3 + 4 = 10 = 2 · 5. Ответ ученика x = 2 дал бы 4 вершины и сумму степеней 8, а рёбер у дерева на 4 вершинах — 3.
б) «Хотя бы один» = один, два или три. Удобно через противоположное: орла нет только в исходе РРР; 8 − 1 = 7.
в) Путь З — Д — Б — А — В: 5 вершин, 4 ребра; длина 4.

R05.1 · R05.2 · R05.3

Задания с самопроверкой · база

Решите и проверьте

Сколько листьев? $4$
Длина пути из А в И $5$
Сколько рёбер? Ответьте, не считая $9 - 1 = 8$

В дереве $20$ вершин. Рёбер? $19$
В дереве $13$ рёбер. Вершин? $14$
Трёхзначные числа из цифр $5$ и $7$ (повторы можно) $8$
Монету бросают $2$ раза: сколько листьев у дерева? $4$

R05.2 · R05.3

Задания с самопроверкой · повышенный уровень

Подумайте и решите

повыш.В дереве $5$ вершин степени $3$ , $2$ вершины степени $2$ , остальные — листья. Сколько листьев? $7$
повыш.Может ли у дерева с $6$ вершинами степень каждой вершины быть равна $2$ ? нет
повыш.Монету бросают $4$ раза. В скольких исходах орлов больше, чем решек? $5$
из жизниШифр: $2$ буквы из А, Б, В (повторы можно), затем $2$ разные цифры. Сколько шифров? $810$

R05.3 · ОГЭ

Формат ОГЭ · линия 10

Нарисуйте дерево — запишите ответ десятичной дробью

1. Симметричную монету бросают четыре раза. Найдите вероятность того, что орёл выпадет ровно три раза.

Ответ: $0, 25$

2. Симметричную монету бросают три раза. Найдите вероятность того, что решка не выпадет ни разу.

Ответ: $0, 125$

3. Симметричную монету бросают три раза. Найдите вероятность того, что орёл выпадет не меньше двух раз.

Ответ: $0, 5$

R05.1 · R05.2 · R05.3

Самостоятельная работа · 5 минут

Два варианта — решите свой

Вариант 1

В дереве $16$ вершин. Рёбер? $15$
Двузначные числа из цифр $0, 3, 6$ без повторений $4$
$3$ броска монеты: исходов, где решка ровно $1$ раз $3$
В дереве $3$ вершины степени $3$ , остальные — листья. Листьев? $5$

Вариант 2

В дереве $21$ ребро. Вершин? $22$
Двузначные числа из цифр $0, 2, 5, 7$ без повторений $9$
$3$ броска монеты: исходов, где есть хотя бы одна решка $7$
В дереве $2$ вершины степени $4$ , остальные — листья. Листьев? $6$

рефлексия · ДЗ

Итог урока

Проверьте себя и потренируйтесь

Ответьте одной фразой

Почему путь в дереве единственный?
Как найти число листьев по степеням?
Где в дереве вариантов «спрятано» умножение?

Домашнее задание

Нарисуйте дерево: $7$ вершин, ровно $4$ листа
$6$ вершин степени $3$ , остальные — листья: сколько листьев?
$4$ броска монеты: в скольких исходах орлов и решек поровну?
Тренажёр: reknow.ru/8/veroyatnost/8_veroyatnost_derevya.htm

Паспорт соответствия · скрытый слайд

VIS8-022 · Практикум: дерево

Поле	Значение
ФРП	«Математика» (базовый уровень), 5–9 кл., Москва – 2025 · курс «Вероятность и статистика», 8 класс
Строка, урок	R05 «Введение в теорию графов», 4 ч · урок 4/4 · тип П
Единицы → слайды	R05.1 «Дерево» → 2–5, 9, 11–16, 19, 20 · повторение: R05.2 «Свойства дерева» → 6, 7, 13–17, 19 · R05.3 «Правило умножения» → 8–12, 14, 16–19
Результаты	ПР-5 / REQ-5.5 (графические модели: дерево) → 3–17, 19 · ПР-4 / REQ-5.4 (вероятности в опытах с равновозможными исходами) → 11, 12, 18 · EL-5.7
Вне урока	дерево случайного эксперимента с вероятностями на рёбрах — R06 (VIS8-025, VIS8-026); противоположное событие — VIS8-023
Время	теория 12 мин · практика 33 мин (73 %)
Проверки	автопроверка: pending · методист: pending

Практикум: дерево

Сегодня вы научитесь

Читать дерево

Считать вершины и рёбра

Строить дерево вариантов

Находить вероятности

Дерево или нет? Считаем быстро

Дерево — связный граф без циклов

Путь в дереве — единственный

Образец: найдите путь из 1 в 10 и его длину

Сам: по тому же дереву

Три свойства, которые работают в задачах

Путь — единственный

Есть висячая вершина

n вершин — n−1 ребро

Листья — через сумму степеней

Образец: в дереве 4 вершины степени 3, остальные — листья. Сколько листьев?

Сам

Каждый вариант — путь от корня к листу

Перебор по дереву: ничего не пропустить

Образец: двузначные числа из цифр 0,1,2 без повторений

Сам: постройте дерево, сосчитайте

Дерево большое — рисуем одну ветку

Образец: 3 салата, 4 горячих, 2 десерта. Сколько обедов из трёх блюд?

Сам: сколько вариантов?

Монету бросают 3 раза: из каждой вершины — 2 ветви

Отмечаем нужные листья

Образец: в скольких исходах трёх бросаний орёл выпал ровно 2 раза?

Сам: монету бросают 4 раза

Олимпийская система — это дерево

Образец: 8 команд, проигравший выбывает. Сколько матчей?

Сам

Неверно → почему → верно

Где ошибся ученик?

а) В дереве 2 вершины степени 3, остальные — листья. Сколько листьев?

б) Монету бросают 3 раза. В скольких исходах есть хотя бы один орёл?

в) Длина пути

Решите и проверьте

Подумайте и решите

Нарисуйте дерево — запишите ответ десятичной дробью

Два варианта — решите свой

Вариант 1

Вариант 2

Проверьте себя и потренируйтесь

Ответьте одной фразой

Домашнее задание

VIS8-022 · Практикум: дерево

Образец: найдите путь из $1$ в $10$ и его длину

$n$ вершин — $n - 1$ ребро

Образец: в дереве $4$ вершины степени $3$ , остальные — листья. Сколько листьев?

Образец: двузначные числа из цифр $0, 1, 2$ без повторений

Образец: $3$ салата, $4$ горячих, $2$ десерта. Сколько обедов из трёх блюд?

Монету бросают $3$ раза: из каждой вершины — $2$ ветви

Образец: в скольких исходах трёх бросаний орёл выпал ровно $2$ раза?

Сам: монету бросают $4$ раза

Образец: $8$ команд, проигравший выбывает. Сколько матчей?

а) В дереве $2$ вершины степени $3$ , остальные — листья. Сколько листьев?

б) Монету бросают $3$ раза. В скольких исходах есть хотя бы один орёл?