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

Дерево

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

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

R05.1

Цели урока

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

Распознавать дерево

среди графов: связный граф без циклов (ПР-5)

Находить листья

висячие вершины, степени вершин и ветви дерева (ПР-5)

Находить пути

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

Перебирать варианты

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

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

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

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

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

Сколько вершин? Сколько рёбер? $6$ и $6$
Степень вершины $C$ $3$
Сумма степеней всех вершин $12$
Назовите цикл $A$ – $B$ – $C$ – $A$
Граф связный? да
Уберите одно ребро, чтобы циклов не стало $A B$ , $BC$ или $C A$
Цепь из $A$ в $F$ $A$ – $C$ – $D$ – $F$
Сколько исходов у двух бросков монеты? $4$

R05.1

Новое · что такое дерево

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

Связный — от любой вершины можно дойти до любой по рёбрам

Без циклов — нельзя выйти из вершины и вернуться в неё, не проходя ребро дважды

3 мин · теория
Три графа на одних и тех же шести вершинах. Первый — дерево. Во втором добавили одно ребро — появился цикл (выделен красным), это уже не дерево. В третьем убрали одно ребро — граф распался на две части, тоже не дерево. Граф без циклов, состоящий из нескольких деревьев, называют лесом (термин не обязателен).
Вопрос классу: почему «дерево»? (Похоже на ветвящееся дерево: из вершин расходятся ветви, ветви не срастаются — нет циклов.) Примеры деревьев из жизни: родословная, структура папок на компьютере, схема турнира на выбывание, оглавление книги.
Наблюдение (без доказательства, это сл. VIS8-020): у дерева на рисунке 6 вершин и 5 рёбер; добавили ребро — появился цикл, убрали — пропала связность.

R05.1

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

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

Образец: является ли граф деревом?

Сам: какой граф — дерево?

R05.1

Новое · висячие вершины и ветви

Листья дерева

2,5 мин · теория
Степени (по клику, жёлтые кружки): A — 3, B — 3, C — 2, D — 3, листья E, F, G, H, I — по 1. Вершины степени 1 называют висячими, или листьями: на них дерево «заканчивается». Лист — это не «крайняя на рисунке» вершина, а вершина ровно с одним ребром (сл. 14).
Рёбра дерева называют ветвями. Здесь 9 вершин и 8 ветвей. Вопрос: может ли в дереве быть вершина степени 0? (Только если дерево состоит из одной вершины — иначе граф несвязный.)
Наблюдение для следующего урока: в каждом нарисованном дереве (где больше одной вершины) есть хотя бы два листа.

R05.1

Образец → сам · листья и степени

Ищем висячие вершины

Образец: найдите листья дерева и вершины степени $2$

Сам

Сколько листьев у этого дерева? Наибольшая степень? $5$ ; $4$
Сколько листьев у дерева-«цепочки» из $6$ вершин? $2$
Нарисуйте дерево с $5$ вершинами и $4$ листьями «звезда»

R05.1

Новое · путь в дереве и диаметр

Путь, расстояние, диаметр

2,5 мин · теория
Путь (цепь, как в 7 классе) — последовательность вершин, в которой соседние соединены ребром и вершины не повторяются. Длина пути — число рёбер, а не вершин: в пути A–B–C–E–G пять вершин, но четыре ребра.
Спросить: есть ли другой путь из A в G? (Нет: чтобы пойти иначе, пришлось бы вернуться по ребру, а в дереве нет циклов. Это свойство «единственность пути» докажем на следующем уроке VIS8-020.) Поэтому расстояние в дереве — длина единственного пути.
Диаметр — наибольшее из всех расстояний. Самый длинный путь всегда соединяет два листа. Здесь F–H и G–H — по 5 рёбер; A–F, A–G — по 4; диаметр 5 (проверено перебором всех пар кодом).

R05.1

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

Длина пути — число рёбер

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

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

Путь из $K$ в $O$ и его длина $K$ – $L$ – $N$ – $O$ , $3$
Расстояние $d (M, K)$ $2$
Расстояние $d (S, R)$ $4$
Какие вершины на расстоянии $1$ от $N$ ? $L, O, P$

R05.1

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

Самый длинный маршрут в парке

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

Сам: найдите диаметр

R05.1

Новое · корневое дерево и перебор вариантов

Обед: суп и второе — сколько вариантов?

2,5 мин · теория (учитель решает пример сам)
Условие: в столовой 2 супа (щи, борщ) и 3 вторых блюда (котлета, рыба, плов). Обед — один суп и одно второе. Строим дерево: корень — «начало выбора», первый уровень — выбор супа, второй — выбор второго блюда. Такое дерево с выделенной начальной вершиной называют корневым.
Каждый вариант обеда — путь от корня к листу: щи + котлета, щи + рыба, щи + плов, борщ + котлета, борщ + рыба, борщ + плов. Листьев 6 — вариантов 6 (проверено перебором кодом). Дерево гарантирует, что ни один вариант не пропущен и не повторён.
Заметить: 6 = 2 · 3 — это правило умножения, его сформулируем на уроке VIS8-021. Сегодня считаем листья.

R05.1

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

Ни один вариант не пропустить

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

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

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

R05.1 · ПР-4

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

Листья дерева — элементарные события

Образец: монету бросают $3$ раза. $P (ровно 2 орла)$ ?

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

Все три раза выпало одно и то же $0, 25$
Хотя бы один орёл $0, 875$
Первым выпал орёл, а последней — решка $0, 25$

R05.1

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

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

«Циклов нет — значит, дерево»

дерево?

нет: граф несвязный. Нужны оба условия

«Длина пути $A$ – $B$ – $C$ – $D$ равна $4$ »

считали вершины

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

«Лист — крайняя вершина рисунка»

$X$ — лист?

у $X$ степень $2$ ; листья $Y, L, Z$

1,5 мин · практика (ученики объясняют, почему неверно)
1) Граф из двух частей без циклов — не дерево (лес): от левой части нельзя дойти до правой. 2) В пути A–B–C–D четыре вершины, но три ребра; длина пути = число рёбер (номера рёбер подписаны розовым). 3) Лист определяется степенью, а не положением на рисунке: вершина X нарисована с края, но из неё два ребра; Z нарисована внутри, но это лист (одно ребро). Тот же граф можно нарисовать по-разному.

R05.1

Найди ошибку

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

Решение ученика

1) Связный, циклов нет — это дерево.

2) Листья: $A, C, H$ — $3$ листа.

3) Путь $A$ – $B$ – $D$ – $F$ – $G$ , его длина $5$ .

Пункт 2: забыт лист $G$ — листьев $4$ : $A, C, G, H$

Пункт 3: рёбер $4$ — длина пути $4$

R05.1

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

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

Сколько вершин и сколько рёбер? $10$ и $9$
Сколько листьев? $6$
Степень вершины $D$ $4$
Расстояние $d (A, I)$ $5$
Диаметр дерева $5$
$2$ напитка и $3$ десерта: сколько вариантов «напиток + десерт»? $6$
Монету бросают дважды: $P (ровно один орёл)$ $0, 5$

R05.1

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

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

повыш.В графе-цикле из $6$ вершин убрали одно ребро. Получилось дерево? Каков его диаметр? да; $5$
повыш.У дерева $7$ вершин, из них $6$ — листья. Найдите диаметр $2$
повыш.Сколько разных по форме деревьев с $4$ вершинами? $2$ : цепочка и «звезда»
из жизниТурнир на выбывание: $8$ команд, проигравший выбывает. Схема турнира — дерево. Сколько матчей сыграно? $7$
из жизниКод замка — $3$ буквы, каждая $А$ или $Б$ . Сколько кодов? $8$

2 мин · практика
В парах, по готовности; ответы — по клику. Задания 4–5 при нехватке времени — в ДЗ.
1) Остаётся цепочка из 6 вершин: связная, без циклов — дерево; диаметр 5 (от одного конца до другого). 2) Два листа не могут быть соседями (иначе это отдельная часть из двух вершин), значит, все 6 листьев соединены с седьмой вершиной — «звезда», диаметр 2.
3) Перебором кодом всех графов на 4 вершинах с 3 рёбрами: деревья двух форм — цепочка (степени 1, 2, 2, 1) и «звезда» (3, 1, 1, 1). 4) Четвертьфинал 4 матча, полуфинал 2, финал 1 — 7 (вершины-матчи образуют дерево). 5) Дерево: 2 · 2 · 2 = 8 листьев: ААА, ААБ, …, БББ.

ПР-4 · ОГЭ

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

Дерево исходов помогает в ОГЭ

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

$0, 375$

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

$0, 5$

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

$0, 0625$

Число листьев дерева исходов:

2

броска —

4

,

3

броска —

8

,

4

броска —

16

.

R05.1

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

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

Вариант 1

Сколько листьев? $4$
Расстояние $d (A, G)$ $4$
Диаметр дерева $4$
Двузначные числа из цифр $4$ и $5$ : сколько? $4$

Вариант 2

Сколько вершин степени $2$ ? $2$
Расстояние $d (D, H)$ $4$
Диаметр дерева $5$
Двузначные числа из цифр $1, 2, 3$ без повторений: сколько? $6$

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

Итог урока

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

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

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

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

Нарисуйте дерево с $6$ вершинами и диаметром $3$
$3$ рубашки и $2$ пары брюк: дерево вариантов, число вариантов
Тренажёр: reknow.ru/8/veroyatnost/8_veroyatnost_derevya.htm

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

VIS8-019 · Дерево

Поле	Значение
ФРП	«Математика» (базовый уровень), 5–9 кл., Москва – 2025 · курс «Вероятность и статистика», 8 класс
Строка, урок	R05 «Введение в теорию графов», 4 ч · урок 1/4 · тип Н
Единицы → слайды	R05.1 «Дерево» → 2, 4–17, 19 · повторение графов 7 класса → 3 · дерево исходов (ПР-4) → 13, 16, 18
Результаты	ПР-5 / REQ-5.5 (графические модели: дерево) → 4–17, 19 · ПР-4 / REQ-5.4 (вероятности в опытах с равновозможными исходами) → 13, 16, 18
Вне урока	свойства дерева (единственность пути, висячая вершина, $V - E = 1$ ) — VIS8-020; правило умножения — VIS8-021
Время	теория 12,5 мин · практика 32,5 мин (72 %)
Проверки	автопроверка: pending · методист: pending

Дерево

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

Распознавать дерево

Находить листья

Находить пути

Перебирать варианты

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

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

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

Образец: является ли граф деревом?

Сам: какой граф — дерево?

Листья дерева

Ищем висячие вершины

Образец: найдите листья дерева и вершины степени 2

Сам

Путь, расстояние, диаметр

Длина пути — число рёбер

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

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

Самый длинный маршрут в парке

Образец: 8 павильонов соединены дорожками. Сколько дорожек в самом длинном маршруте без повторов?

Сам: найдите диаметр

Обед: суп и второе — сколько вариантов?

Ни один вариант не пропустить

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

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

Листья дерева — элементарные события

Образец: монету бросают 3 раза. P(ровно 2 орла)?

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

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

«Циклов нет — значит, дерево»

«Длина пути A–B–C–D равна 4»

«Лист — крайняя вершина рисунка»

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

Решение ученика

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

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

Дерево исходов помогает в ОГЭ

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

Вариант 1

Вариант 2

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

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

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

VIS8-019 · Дерево

Образец: найдите листья дерева и вершины степени $2$

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

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

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

Образец: монету бросают $3$ раза. $P (ровно 2 орла)$ ?

«Длина пути $A$ – $B$ – $C$ – $D$ равна $4$ »