Введение в теорию графов · урок 3 из 3 · углублённый уровень

Решение задач с помощью деревьев

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

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

R05.5

Цели урока

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

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

перебирать исходы без пропусков, в том числе при разном ветвлении (ПР-1, ПР-4)

Считать вероятность по дереву

доля нужных листьев, когда исходы равновозможны (ПР-2, ПР-4)

Находить вершины и рёбра

турнир на выбывание, «вершин на $1$ больше, чем рёбер» (ПР-4)

Искать пути в дереве

единственный маршрут, его длина, самая далёкая вершина (ПР-4)

1 мин · теория
ПР-4: «Иметь представление о дереве, о вершинах и ребрах дерева, использовании деревьев при решении задач в теории вероятностей, в других учебных математических курсах и задач из других учебных предметов» — главный результат урока. ПР-1: «…перечислять элементы множеств с использованием организованного перебора и комбинаторного правила умножения». ПР-2: «Находить вероятности случайных событий в опытах с равновозможными элементарными событиями». Единица ФРП: R05.5.
Деревья с вероятностями на рёбрах и правило умножения вероятностей — позже (R08, ПР-6); сегодня вероятность только как доля равновозможных листьев.

повторение: VIS8U-017, VIS8U-018

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

Деревья и варианты

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

В дереве $12$ вершин. Рёбер? $11$
В дереве $9$ рёбер. Вершин? $10$
Сколько путей между двумя вершинами дерева? ровно $1$
В дерево добавили одно ребро. Что появится? цикл

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

Монету бросили $2$ раза: исходов $4$
$3$ рубашки, $2$ брюк: комплектов $6$
Трёхзначные из цифр $1$ и $2$ $8$
Кубик: $P (чётное)$ $0, 5$

R05.5

Теория · дерево вариантов

Трёхзначные числа из цифр $1, 3, 5$ без повторов

Корень — начало; уровень — очередной выбор; ветвь — вариант; лист — готовый исход.

Исход = путь от корня до листа

Листьев: $3 \cdot 2 \cdot 1 =$ $6$ ветвление $3$ , $2$ , $1$

Одинаковое ветвление на уровне → правило умножения. Разное → считаем листья.

2,5 мин · теория
Дерево строим слева направо: из корня — 3 ветви (сотни: 1, 3 или 5), из каждой — 2 (десятки: оставшиеся цифры), из каждой — 1 (единицы: последняя цифра). Шаги открывают ветви 1, 3, 5. Листья: 135, 153, 315, 351, 513, 531.
Почему перебор полный: на каждом уровне выписаны все допустимые цифры, а разные пути дают разные числа — ни пропусков, ни повторов.
Вопрос: что изменится, если повторы разрешены? (Из каждой вершины — 3 ветви, 27 листьев: 3 · 3 · 3.)

R05.5

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

Большое дерево: рисуем одну ветку

Образец: трёхзначные числа из цифр $1, 2, 3$ , в которых соседние цифры различны

ветка « $1$ » — $4$ листа после цифры — $2$ другие

ветки « $2$ », « $3$ » такие же: $3 \cdot 4 =$ $12$

Сам: соседние различны

Четырёхзначные из цифр $1, 2, 3$ $24$
Четырёхзначные из цифр $1, 2$ $2$
Флаг из $3$ полос, $4$ цвета, соседние полосы разные $36$

2 мин · практика
Образец: ветка «1» целиком: 121, 123, 131, 132 — 4 листа. Ветки «2» и «3» устроены так же (симметрия), поэтому 3 · 4 = 12 = 3 · 2 · 2. Проверено перебором.
1) 3 · 2 · 2 · 2 = 24. 2) 1212 и 2121 — после каждой цифры остаётся одна. 3) Верхняя полоса — 4 цвета, каждая следующая — 3 (любой, кроме цвета соседа сверху): 4 · 3 · 3 = 36. Всё проверено перебором.
Совет классу: «одна ветка» работает, только если все ветки одинаковы; иначе — каждую считать отдельно (сл. 6).

R05.5

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

Матч до двух побед: Аня (А) против Бори (Б)

Ничьих нет. Кто первым выиграл $2$ партии — победил, игра останавливается.

Ветка обрывается на «АА», «ББ»

Листьев $6$ , а не $2 \cdot 2 \cdot 2 = 8$

Сыграно $3$ партии: $4$ исхода

Ветки разной длины — правило умножения не работает: пересчитываем листья.

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

R05.5

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

Обрезаем запрещённые ветки

Образец: слова из $4$ букв А и Б без двух Б подряд

после Б — только А иначе «ББ»

листья: $2, 3, 5, 8$ — слов $8$

Сам

То же, слова из $3$ букв $5$
углубл.То же, из $5$ букв $13$
Монету бросают до первого орла, но не больше $4$ раз. Исходов? $5$

R05.5

Теория · вероятность по дереву

Шары $1$ , $2$ — белые, $3$ — чёрный; вынимают два

Если все листья равновозможны:

$P (A) = \frac{листья с A}{все листья}$

Шар не возвращают: $3 \cdot 2 = 6$ листьев

$P (оба белые) = \frac{2}{6} =$ $\frac{1}{3}$

$P (разного цвета) = \frac{4}{6} = \frac{2}{3}$

Одинаковые шары нумеруем — так исходы становятся равновозможными.

3 мин · теория
Опыт: из урны наугад вынимают шар, не возвращают, вынимают второй. Первый — любой из 3, второй — любой из 2 оставшихся: 6 упорядоченных пар, все равновозможны. Подсвечены «1, 2» и «2, 1» — оба белые.
Почему нумеруем: если рисовать ветви «белый/чёрный», то листья «ББ», «БЧ», «ЧБ» не равновозможны (белых шаров два) — ответ 1/3 получится только при честных, пронумерованных шарах.
Разного цвета: (1, 3), (2, 3), (3, 1), (3, 2) — 4 из 6. Проверка: 1/3 + 2/3 = 1 (чёрный не может попасться дважды). Проверено перебором.

R05.5

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

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

Образец: из карточек $1, 2, 3, 4$ берут две по очереди — двузначное число. $P (делится на 3)$ ?

листьев $4 \cdot 3 = 12$ все равновозможны

$12, 21, 24, 42$ сумма цифр делится на $3$

$P = \frac{4}{12} =$ $\frac{1}{3}$

Сам: нарисуйте дерево

Монету бросают $3$ раза. $P (выпадут и орёл, и решка)$ $0, 75$
Шары со сл. 8: $P (второй шар чёрный)$ $1/3$
Аня, Боря, Вика встают в очередь наугад. $P (Аня раньше Бори)$ $0, 5$

R05.5

Теория · вершины и рёбра в задачах

Олимпийская система: проигравший выбывает

$8$ команд — листья, каждый матч ( $m$ ) — вершина, из неё $2$ ребра вниз.

вершин $8 + m$ , рёбер $2 m$

$8 + m = 2 m + 1$ вершин на $1$ больше

$m =$ $7$ матчей

n

команд →

n - 1

матч: каждый матч выбивает ровно одну команду.

2,5 мин · теория
Сетку турнира рисуем деревом снизу вверх: листья — 8 команд, над каждой парой — вершина-матч (её победитель идёт выше), корень — финал. Шаги: 4 матча 1/4 финала, 2 полуфинала, финал (номера 1–7).
Используем свойство с прошлого урока: в дереве вершин на одну больше, чем рёбер. Вершины: 8 листьев + m матчей; рёбра: из каждой вершины-матча по 2 вниз — 2m. 8 + m = 2m + 1 ⇒ m = 7.
Второе рассуждение (проще): в итоге выбывают все, кроме чемпиона, — 7 команд, а в каждом матче выбывает ровно одна. Работает при любом n, даже если n — не степень двойки (кто-то проходит тур без игры): матчей n − 1.

R05.5

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

Сколько листьев, если известны внутренние вершины

Образец: в корневом дереве у каждой вершины $3$ потомка или ни одного. Внутренних вершин $5$ . Сколько листьев?

рёбер $3 \cdot 5 = 15$ по $3$ вниз

вершин $15 + 1 = 16$

листьев $16 - 5 =$ $11$

Сам

Олимпийская система, $32$ команды. Матчей? $31$
Турнир на выбывание, $20$ команд. Матчей? $19$
У каждой вершины $2$ потомка или ни одного; листьев $10$ . Всего вершин? $19$

R05.5

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

Дороги между посёлками образуют дерево (км)

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

путь единственный: А–Б–Г–Е–Ж

$3 + 2 + 4 + 1 =$ $10$ км

Сам: по той же карте

Длина пути из В в З $13$ км
Самый далёкий от А посёлок Д, $12$ км
углубл.Сколько всего маршрутов между парами посёлков? $28$

R05.5

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

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

Где ошибаются	Неверно	Верно
ветки разной длины, а перемножили	матч до $2$ побед: $2 \cdot 2 \cdot 2 = 8$	листьев $6$
одинаковые шары «склеили» в одну ветвь	$2$ белых, $1$ чёрный: $P (б) = \frac{1}{2}$	нумеруем: $P (б) = \frac{2}{3}$
рёбер столько же, сколько вершин	$10$ вершин → $10$ рёбер	$10 - 1 = 9$ рёбер
посчитали только первый тур	$16$ команд: $16 : 2 = 8$ матчей	$16 - 1 = 15$ матчей

R05.5

Найди ошибку

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

а) Монету бросают до первого орла, но не больше $3$ раз. Сколько исходов?

$2 \cdot 2 \cdot 2 = 8$

после орла бросать не нужно — ветка обрывается

О, РО, РРО, РРР — $4$

б) Шары $1, 2$ — белые, $3$ — чёрный; вынимают два без возвращения. $P (оба белые)$ ?

$P = \frac{4}{9}$ : листьев $3 \cdot 3 = 9$ , нужных $4$

шар не возвращают: $3 \cdot 2 = 6$ листьев

нужных $2$ : $P = \frac{2}{6} = \frac{1}{3}$

в) У каждой вершины $2$ потомка или ни одного; внутренних $4$ . Сколько листьев?

$4 \cdot 2 = 8$ листьев

потомки бывают и внутренними: рёбер $8$ , вершин $9$

листьев $9 - 4 = 5$

2 мин · практика
Сначала видны только «решения ученика» (красным); 1 мин в парах — найти ошибку, затем открывать исправления.
а) Дерево «лесенкой»: О (стоп), Р → О (стоп) или Р → О или Р: 4 листа. б) Ученик посчитал с возвращением (1, 1), (1, 2), (2, 1), (2, 2) — но второй раз тот же шар не вынуть. Без возвращения: (1, 2), (2, 1) из 6. в) 8 — это все потомки, включая 3 внутренние вершины (кроме корня); по формуле: 2 · 4 = 8 рёбер, 9 вершин, листьев 5 (= 4 + 1). Всё проверено перебором.

R05.5

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

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

Вершины, рёбра, варианты

Дерево с $25$ вершинами: рёбер $24$
Олимпийская система, $64$ игрока: матчей $63$
Трёхзначные из цифр $2, 4, 6$ без повторов $6$

По дереву

Слова из $3$ букв А, Б без двух А подряд $5$
Монету бросают $3$ раза: исходов с ровно одной решкой $3$
То же: $P (хотя бы одна решка)$ $0, 875$

R05.5

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

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

повыш.Матч до трёх побед, ничьих нет. Сколько всего возможных исходов (последовательностей партий)? $20$
повыш.Сколько слов из $6$ букв А и Б, в которых нет двух Б подряд? $21$
повыш.В корневом дереве у каждой вершины $4$ потомка или ни одного; листьев $22$ . Сколько внутренних вершин? $7$
исследованиеТурнир $8$ команд, команда выбывает после второго поражения, ничьих нет. Сколько матчей может быть сыграно? $14$ или $15$

2,5 мин · практика
В парах, по готовности; ответы — по клику. Задания 3–4 при нехватке времени — в ДЗ.
1) Победа А за 3 партии — 1 исход (ААА), за 4 — 3 (поражение в одной из первых трёх), за 5 — 6 (два поражения в первых четырёх: 6 мест для пары, перебором); всего 10, и столько же у Б — 20 (проверено перебором). 2) Ряд 2, 3, 5, 8, 13, 21 — 21.
3) k внутренних: рёбер 4k, вершин 4k + 1 = k + 22 ⇒ k = 7. 4) В каждом матче ровно одно поражение. Все 7 выбывших проиграли по 2 раза — 14 поражений; победитель проиграл 0 или 1 раз. Матчей 14 или 15 — оба случая возможны.

R05.5 · ОГЭ

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

Рисуем дерево — ответ десятичной дробью

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

$0, 375$

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

$0, 0625$

3. Из цифр $1, 2, 3, 4, 5$ наугад составляют двузначное число с разными цифрами. Найдите вероятность того, что оно чётное.

$0, 4$

Листья равновозможны:

P = \frac{нужные листья}{все листья}

. В бланк: 0,375.

R05.5 · из жизни

Задача из жизни · тест наугад

Тест из $3$ вопросов «да/нет»: зачёт — от $2$ верных

Ученик не готовился и отвечает наугад: В — верно, Н — неверно, оба варианта равновозможны.

$P (зачёт)$ $0, 5$
$P (все ответы верны)$ $0, 125$
Тест из $4$ вопросов, зачёт — от $3$ верных. $P (зачёт)$ $0, 3125$

Угадать зачёт — как подбросить монету. С

4

вопросами — хуже.

R05.5

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

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

Вариант 1

Дерево с $40$ вершинами: рёбер $39$
Трёхзначные из цифр $1, 2, 3$ , соседние различны $12$
Олимпийская система, $32$ команды: матчей $31$
Монету бросают $3$ раза: $P (ровно две решки)$ $0, 375$

Вариант 2

Дерево с $30$ рёбрами: вершин $31$
Трёхзначные из цифр $1, 2, 3, 4$ без повторов $24$
Олимпийская система, $128$ команд: матчей $127$
Монету бросают $3$ раза: $P (все броски одинаковы)$ $0, 25$

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

Итог урока

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

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

Что в дереве вариантов — исход?
Когда листья можно не рисовать, а перемножить?
Когда вероятность — доля листьев?
Почему в турнире $n$ команд $n - 1$ матч?

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

Слова из $5$ букв А, Б, В без двух одинаковых букв подряд
Монету бросают $4$ раза: $P (орлов больше, чем решек)$
Тренажёр: reknow.ru/8/veroyatnost/8_veroyatnost_derevya.htm

2 мин · практика (рефлексия, запись ДЗ)
Ответы на вопросы: исход — путь от корня до листа; перемножать — когда на каждом уровне у всех вершин одинаковое число ветвей; доля листьев — когда листья равновозможны; каждый матч выбивает одну команду, выбывают все, кроме победителя.
Ответы ДЗ: 3 · 2 · 2 · 2 · 2 = 48; 5/16 = 0,3125 (4 орла — 1 лист, 3 орла — 4 листа). Проверено перебором.
Следующий урок — логические союзы «И» и «ИЛИ» (VIS8U-020); деревья с вероятностями на рёбрах — в теме «Случайные события» (R08).

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

VIS8U-019 · Решение задач с помощью деревьев

Поле	Значение
ФРП	«Математика» (углублённый уровень), 7–9 кл., Москва – 2025 · курс «Вероятность и статистика», 8 класс
Строка, урок	R05 «Введение в теорию графов», 3 ч · урок 3/3 · тип Н
Единицы → слайды	R05.5 «Решение задач с помощью деревьев» → 2, 4–20 · повторение R05.1–R05.3 (дерево, единственность пути, связь вершин и рёбер) → 3, 10–12
Результаты	ПР-4 (дерево, вершины и рёбра, деревья в задачах теории вероятностей и других предметов) → 2–20 · ПР-1 (организованный перебор, правило умножения) → 4–7, 15, 19 · ПР-2 (вероятность в опытах с равновозможными исходами) → 8–9, 15, 17–19
Вне урока	логические союзы «И» и «ИЛИ» — VIS8U-020; дерево с вероятностями на рёбрах и правило умножения вероятностей (ПР-6) — строка R08
Время	теория 13 мин · практика 32 мин (71 %)
Проверки	автопроверка: pending · методист: pending

Решение задач с помощью деревьев

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

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

Считать вероятность по дереву

Находить вершины и рёбра

Искать пути в дереве

Деревья и варианты

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

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

Трёхзначные числа из цифр 1,3,5 без повторов

Большое дерево: рисуем одну ветку

Образец: трёхзначные числа из цифр 1,2,3, в которых соседние цифры различны

Сам: соседние различны

Матч до двух побед: Аня (А) против Бори (Б)

Обрезаем запрещённые ветки

Образец: слова из 4 букв А и Б без двух Б подряд

Сам

Шары 1, 2 — белые, 3 — чёрный; вынимают два

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

Образец: из карточек 1,2,3,4 берут две по очереди — двузначное число. P(делится на 3)?

Сам: нарисуйте дерево

Олимпийская система: проигравший выбывает

Сколько листьев, если известны внутренние вершины

Образец: в корневом дереве у каждой вершины 3 потомка или ни одного. Внутренних вершин 5. Сколько листьев?

Сам

Дороги между посёлками образуют дерево (км)

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

Сам: по той же карте

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

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

а) Монету бросают до первого орла, но не больше 3 раз. Сколько исходов?

б) Шары 1,2 — белые, 3 — чёрный; вынимают два без возвращения. P(оба белые)?

в) У каждой вершины 2 потомка или ни одного; внутренних 4. Сколько листьев?

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

Вершины, рёбра, варианты

По дереву

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

Рисуем дерево — ответ десятичной дробью

Тест из 3 вопросов «да/нет»: зачёт — от 2 верных

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

Вариант 1

Вариант 2

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

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

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

VIS8U-019 · Решение задач с помощью деревьев

Трёхзначные числа из цифр $1, 3, 5$ без повторов

Образец: трёхзначные числа из цифр $1, 2, 3$ , в которых соседние цифры различны

Образец: слова из $4$ букв А и Б без двух Б подряд

Шары $1$ , $2$ — белые, $3$ — чёрный; вынимают два

Образец: из карточек $1, 2, 3, 4$ берут две по очереди — двузначное число. $P (делится на 3)$ ?

Образец: в корневом дереве у каждой вершины $3$ потомка или ни одного. Внутренних вершин $5$ . Сколько листьев?

а) Монету бросают до первого орла, но не больше $3$ раз. Сколько исходов?

б) Шары $1, 2$ — белые, $3$ — чёрный; вынимают два без возвращения. $P (оба белые)$ ?

в) У каждой вершины $2$ потомка или ни одного; внутренних $4$ . Сколько листьев?

Тест из $3$ вопросов «да/нет»: зачёт — от $2$ верных