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

Дерево. Дерево случайного эксперимента

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

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

R05.1 · R05.2

Цели урока

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

Узнавать дерево

проверять, что граф связный и без циклов (ПР-4)

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

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

Строить дерево опыта

изображать этапы опыта ветвями, а исходы — листьями (ПР-4, ПР-6)

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

число исходов и вероятность $P = \frac{m}{n}$ по листьям (ПР-2, ПР-4)

повторение: графы, 7 класс

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

Вспомним графы

Сколько вершин и рёбер у $G$ ? $5$ и $5$
Степень вершины $C$ $3$
Сумма степеней всех вершин $10 = 2 \cdot 5$
Есть ли в $G$ цикл? да: $A B C A$
Связный ли граф $G$ ? да
Путь из $A$ в $E$ и его длина $A C D E$ ; $3$
У графа $4$ вершины степени $3$ . Рёбер? $6$

3 мин · практика
Повторение строки R04 7 класса «Введение в теорию графов». Ответы по клику: 1) 5 вершин, 5 рёбер (AB, BC, CA, CD, DE). 2) C соединена с A, B, D — степень 3. 3) 2 + 2 + 3 + 2 + 1 = 10 = 2 · 5: каждое ребро даёт вклад 2.
4) Цикл A–B–C–A (треугольник). 5) Из любой вершины можно дойти до любой — связный. 6) A–C–D–E, длина = число рёбер = 3 (не число вершин!). 7) Сумма степеней 12 = 2 · рёбер, рёбер 6 (полный граф на 4 вершинах).
Вопрос-мостик: если из графа G убрать ребро BC, останется ли он связным? Будут ли циклы? (Связный, циклов нет — получится дерево, о нём урок.)

R05.1 · R05.2

Теория · определение дерева

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

Дерево — граф, который связный и не содержит циклов.

Есть цикл — не дерево: одно ребро цикла «лишнее».

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

Генеалогическое дерево, схема папок, турнирная сетка — деревья.

2,5 мин · теория
Три графа по 5 вершин. Первый (бирюзовый) — дерево: связный, циклов нет. Второй: по клику подсвечивается цикл (треугольник) — не дерево. Третий: по клику обводятся две части — граф несвязный; без циклов, но это не дерево, а лес (два дерева).
Оба условия обязательны. Вопрос классу: можно ли во втором графе удалить одно ребро так, чтобы получилось дерево? (Да — любое ребро треугольника.) А в третьем — добавить одно ребро? (Да — соединить части, например вершину 4 с вершиной 2.)
Примеры из жизни: родословная по одной линии, папки на компьютере, турнир «на выбывание», дерево решений.

R05.1 · R05.2

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

Проверяем два условия

Образец: дерево ли этот граф? Как сделать дерево?

Связный: из $A$ дойдём до любой условие 1 выполнено

Цикл $A B C D A$ — не дерево условие 2 нарушено

Убрать ребро цикла, например $C D$ связность сохранится

Сам: дерево ли граф?

а) да
б) нет: цикл
в) нет: несвязный (лес)

2,5 мин · практика
Образец (по клику): 1) граф связный — проверяем проходом из A: B, F, C, D, E достижимы. 2) Подсвечивается цикл A–B–C–D–A — значит, не дерево. 3) Удаляем одно ребро цикла (CD, пунктир): граф остаётся связным, цикла больше нет — дерево. Подойдёт любое из рёбер AB, BC, CD, DA.
Сам: а) 5 вершин, связный, циклов нет — дерево. б) Есть треугольник — не дерево. в) Две отдельные цепочки по 3 вершины — циклов нет, но несвязный: лес из двух деревьев. Вопрос: каким одним ребром превратить в) в дерево? (Соединить любую вершину левой цепочки с любой вершиной правой.)

R05.1

Теория · лист, путь, диаметр

Как устроено дерево

Висячая вершина (лист) — вершина степени $1$ .

Путь — вершины подряд по рёбрам, без повторов; длина — число рёбер.

Диаметр — наибольшая длина пути в дереве.

Длинный путь начинается и кончается в листьях.

2,5 мин · теория
Дерево из 8 вершин A–H (7 рёбер). Шаги: 1) листья — вершины степени 1: C, E, F, H (бирюзовые). 2) Путь из C в H: C–B–A–G–H; вершины не повторяются; длина 4 (рёбер), а не 5 (вершин). 3) Диаметр: перебираем пути между листьями: C–E и C–F — 3, E–F — 2, C–H — 4, E–H и F–H — 5. Наибольший — 5 (E–D–B–A–G–H).
Почему самый длинный путь кончается в листьях: если конец пути не лист, у него есть ещё сосед вне пути (циклов нет) — путь можно продлить.
Вопрос: сколько путей ведёт из C в H? (Один — в дереве путь между двумя вершинами единственный; докажем на следующем уроке.)

R05.1

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

Ищем путь и самый длинный путь

Образец: путь из $C$ в $H$ и диаметр дерева

$C B A G H$ : длина $4$ считаем рёбра

$E D B A G H$ : $5$ пути между листьями

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

Сколько листьев? $4$
Длина пути из $E$ в $C$ $3$
Степень вершины $D$ $3$
углубл.К какой вершине прикрепить новый лист, чтобы диаметр стал $6$ ? к $E$ , $F$ или $H$

R05.1 · R05.2

Теория · дерево случайного эксперимента

Этапы опыта — уровни дерева

Бросают монету, затем тянут одну из карточек $1, 2, 3$

Корень — начало опыта; рёбра — исходы этапа.

Лист — элементарное событие; ветвь — путь от корня до листа.

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

Исходы этапов равновозможны — листья тоже:

P = \frac{m}{n}

.

2,5 мин · теория
Корневое дерево: одна вершина выделена — корень; от него идут ветви «вправо» по этапам опыта. Опыт в два этапа: монета (О или Р), затем карточка 1, 2 или 3. У каждой вершины уровня 1 по 3 ребра.
Лист = элементарное событие (О1, О2, О3, Р1, Р2, Р3); ветвь — путь от корня до листа (подсвечена ветвь Р2: «решка, карточка 2»). Число листьев 2 · 3 = 6 — комбинаторное правило умножения в виде дерева.
Если на каждом этапе исходы равновозможны и число ветвей у вершин одного уровня одинаковое, листья равновозможны: P(О и чётная карточка) = 1/6 (О2), P(карточка 3) = 2/6 = 1/3.
Вероятности на рёбрах и правило умножения вероятностей — позже (строки R07–R08); сегодня считаем листья.

R05.1 · R05.2

Теория · пример учителя: без возвращения

Карточки $1, 2, 3$ : двузначное число

Наугад тянут карточку, кладут слева, затем вторую — справа.

Листьев: $3 \cdot 2 = 6$ вторая — из двух

«больше $20$ »: $\frac{4}{6} =$ $\frac{2}{3}$ розовые

«чётное»: $12, 32$ : $\frac{2}{6} =$ $\frac{1}{3}$ точки

Без возвращения на каждом уровне ветвей на одну меньше.

2 мин · теория (учитель решает сам)
Опыт: из трёх карточек 1, 2, 3 тянут одну (десятки), затем из оставшихся двух — вторую (единицы). Первая карточка не возвращается, поэтому у каждой вершины 1-го уровня только 2 ветви: 3 · 2 = 6 листьев: 12, 13, 21, 23, 31, 32. Все равновозможны.
«Больше 20» — 21, 23, 31, 32: 4/6 = 2/3 (розовые). «Чётное» — кончается на 2: 12, 32 — 2/6 = 1/3 (фиолетовые точки).
Вопрос: а если первую карточку вернуть? (Тогда 3 · 3 = 9 листьев, появятся 11, 22, 33 — следующий слайд про шары с возвращением.)

R05.1 · R05.2

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

Шары: красный, синий, жёлтый

Образец: шар вынули, вернули, вынули снова. $P (« одного цвета »)$

Листьев $3 \cdot 3 = 9$ шар вернули

КК, СС, ЖЖ: $\frac{3}{9} =$ $\frac{1}{3}$ $m = 3$

Сам: тот же опыт

$P (« шары разного цвета »)$ $\frac{2}{3}$
$P (« хотя бы один красный »)$ $\frac{5}{9}$
$P («1- й красный, 2- й нет »)$ $\frac{2}{9}$

R05.1 · R05.2

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

Матч до двух побед

Образец: Аня и Борис играют до двух побед (ничьих нет). Исходы матча?

Победа во 2-й раз — ветвь обрывается матч окончен

Листьев $6$ ; из двух партий — АА, ББ $2$ исхода

Сам: тот же матч

В скольких исходах победила Аня? $3$
Сколько исходов из $3$ партий? $4$
углубл.Первую партию выиграла Аня. Сколько исходов осталось? $3$ : АА, АБА, АББ

2,5 мин · практика
Образец: дерево неполное — ветви разной длины. После второй победы одного из игроков ветвь заканчивается листом. Исходы: АА, АБА, АББ, БАА, БАБ, ББ — 6 листьев. Из двух партий — АА и ББ (бирюзовые).
Осторожно: эти 6 исходов НЕ равновозможны (АА вероятнее, чем АБА) — поэтому здесь считаем только число исходов, а не вероятность. Вероятности на рёбрах — в строках R07–R08.
Сам: 1) АА, АБА, БАА — 3 (Аня выиграла 2 партии). 2) АБА, АББ, БАА, БАБ — 4. 3) Остаётся верхняя половина дерева: АА, АБА, АББ — 3. Проверено перебором кодом.

R05.1 · R05.2

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

Код камеры хранения

Образец: код — цифра $1$ или $2$ , цифра $0, 5$ или $7$ , буква А или Б. Код выбран наугад. $P (« \dots 0 А »)$

Листьев $2 \cdot 3 \cdot 2 = 12$ три этапа

$10$ А, $20$ А: $\frac{2}{12} =$ $\frac{1}{6}$ $m = 2$

Сам: тот же код

$P (« первая цифра 2 »)$ $\frac{1}{2}$
$P (« вторая цифра не 0 »)$ $\frac{2}{3}$
$P (« код 15 Б »)$ $\frac{1}{12}$

2,5 мин · практика
Образец: три этапа — первая цифра (2 ветви), вторая цифра (3 ветви у каждой), буква (2 ветви). Листьев 2 · 3 · 2 = 12; все коды равновозможны (выбран наугад). Событие «вторая цифра 0 и буква А»: 10А, 20А — 2/12 = 1/6 (розовые).
Сам: 1) Верхняя половина дерева — 6 листьев из 12: 1/2. 2) Вторая цифра 5 или 7: 2 · 2 · 2 = 8 листьев, 8/12 = 2/3. 3) Один лист из 12: 1/12. Проверено перебором кодом.
Вопрос из жизни: сколько попыток в худшем случае нужно, чтобы подобрать такой код? (12.) Зачем в настоящих кодах 4–6 знаков?

R05.1 · R05.2

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

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

Где ошибаются	Неверно	Верно
граф без циклов, но из двух частей	«это дерево»	нужна связность — это лес
длина пути $C B A$	$3$ — по вершинам	$2$ — по рёбрам
$2$ карточки из $3$ без возвращения	$3 \cdot 3 = 9$ исходов	$3 \cdot 2 = 6$ исходов
матч до двух побед	$2 \cdot 2 \cdot 2 = 8$ исходов	$6$ : ветвь обрывается

R05.1 · R05.2

Найди ошибку

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

а) Диаметр «звезды»: центр и $5$ листьев

Самый длинный путь «лист — центр — лист»: $3$ вершины, диаметр $3$

длину считают по рёбрам

диаметр $= 2$

б) Из $4$ карточек тянут $2$ без возвращения. Исходов?

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

второй раз — из $3$ карточек

$4 \cdot 3 = 12$

в) Путь из $A$ в $E$ в этом дереве

$A B C B D E$ , длина $5$

$B$ повторяется — это не путь

$A B D E$ , длина $3$

R05.1 · R05.2

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

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

Дерево

Связный граф без циклов называется… деревом
Путь $K L M N P$ . Его длина $4$
«Звезда»: центр и $6$ лучей. Листьев? $6$

Дерево опыта

Монету бросают $3$ раза. Листьев? $8$
Из карточек $1$ – $4$ тянут $2$ без возвращения. Листьев? $12$
Там же: $P (« сумма 5 »)$ $\frac{1}{3}$

R05.1 · R05.2

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

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

повыш.У корня $3$ ветви, у каждой следующей вершины — по $2$ , всего $3$ уровня. Сколько листьев и сколько всего вершин? $12$ и $22$
повыш.Дерево — путь из $7$ вершин. Найдите число листьев и диаметр. $2$ и $6$
повыш.Буквы М, А, Т расставляют в случайном порядке. Найдите вероятность, что «слово» начинается с гласной. $\frac{1}{3}$
исследованиеМатч до трёх побед, ничьих нет. Сколько у него исходов? Сколько из них из $5$ партий? $20$ и $12$

2 мин · практика
В парах, по готовности; ответы — по клику. Задания 3–4 при нехватке времени — в ДЗ.
1) Листьев 3 · 2 · 2 = 12; вершин 1 + 3 + 6 + 12 = 22. 2) Листья — два конца; диаметр — весь путь: 6 рёбер. 3) Дерево 3 · 2 · 1 = 6 «слов»; с А начинаются АМТ, АТМ — 2/6 = 1/3.
4) Строим дерево до 3 побед: из 3 партий — ААА, БББ (2); из 4 — победитель берёт 4-ю партию и 2 из первых трёх: 3 + 3 = 6; из 5 — 4-я партия при счёте 2:2, первые 4 партии — 6 вариантов для каждого победителя: 12. Итого 2 + 6 + 12 = 20. Проверено перебором кодом.

R05.2 · ОГЭ

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

Дерево помогает перечислить исходы

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

$0, 5$

2. Команда «Физик» играет три матча с разными командами; перед каждым судья бросает монету. Найдите вероятность того, что «Физик» выиграет жребий ровно два раза.

$0, 375$

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

$0, 125$

Дерево

2 \cdot 2 \cdot 2 = 8

листьев; ответ — десятичной дробью:

\frac{3}{8} = 0, 375

.

R05.1 · R05.2

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

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

Вариант 1

Дерево — путь из $5$ вершин. Листьев? Диаметр? $2$ ; $4$
Из карточек $1, 2, 3$ тянут $2$ с возвращением. Листьев? $9$
Там же: $P (« карточки одинаковы »)$ $\frac{1}{3}$
Матч до двух побед: исходов из $2$ партий? $2$

Вариант 2

«Звезда»: центр и $4$ луча. Листьев? Диаметр? $4$ ; $2$
Из карточек $1$ – $4$ тянут $2$ без возвращения. Листьев? $12$
Там же: $P («1- я больше 2- й »)$ $\frac{1}{2}$
Матч до двух побед: исходов, где победил Борис? $3$

R05.1 · R05.2

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

Дерево и дерево опыта

Дерево — связный граф без циклов; лист — степень $1$ .

Длина пути и диаметр — в рёбрах.

Одинаковое ветвление: листьев $= n_{1} \cdot n_{2} \cdot \dots$

Без возвращения — ветвей меньше; матч — ветви обрываются.

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

Итог урока

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

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

Какой граф называют деревом?
Как найти диаметр дерева?
Что в дереве опыта изображают листья?
Почему без возвращения ветвей меньше?

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

Из шаров К, С, Ж тянут $2$ без возвращения: дерево, $P (« есть К »)$
Нарисуйте дерево из $8$ вершин с диаметром $3$
Тренажёр: reknow.ru/8/veroyatnost/8_veroyatnost_derevya.htm

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

VIS8U-017 · Дерево. Дерево случайного эксперимента

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

Дерево. Дерево случайного эксперимента

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

Узнавать дерево

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

Строить дерево опыта

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

Вспомним графы

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

Проверяем два условия

Образец: дерево ли этот граф? Как сделать дерево?

Сам: дерево ли граф?

Как устроено дерево

Ищем путь и самый длинный путь

Образец: путь из C в H и диаметр дерева

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

Этапы опыта — уровни дерева

Карточки 1, 2, 3: двузначное число

Шары: красный, синий, жёлтый

Образец: шар вынули, вернули, вынули снова. P(«одного цвета»)

Сам: тот же опыт

Матч до двух побед

Образец: Аня и Борис играют до двух побед (ничьих нет). Исходы матча?

Сам: тот же матч

Код камеры хранения

Образец: код — цифра 1 или 2, цифра 0, 5 или 7, буква А или Б. Код выбран наугад. P(«…0А»)

Сам: тот же код

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

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

а) Диаметр «звезды»: центр и 5 листьев

б) Из 4 карточек тянут 2 без возвращения. Исходов?

в) Путь из A в E в этом дереве

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

Дерево

Дерево опыта

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

Дерево помогает перечислить исходы

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

Вариант 1

Вариант 2

Дерево и дерево опыта

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

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

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

VIS8U-017 · Дерево. Дерево случайного эксперимента

Образец: путь из $C$ в $H$ и диаметр дерева

Карточки $1, 2, 3$ : двузначное число

Образец: шар вынули, вернули, вынули снова. $P (« одного цвета »)$

Образец: код — цифра $1$ или $2$ , цифра $0, 5$ или $7$ , буква А или Б. Код выбран наугад. $P (« \dots 0 А »)$

а) Диаметр «звезды»: центр и $5$ листьев

б) Из $4$ карточек тянут $2$ без возвращения. Исходов?

в) Путь из $A$ в $E$ в этом дереве