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

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

Единственность пути, висячая вершина, связь между числом вершин и числом рёбер

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

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

R05.2

Цели урока

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

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

он всегда единственный; считать его длину (ПР-5)

Объяснять, почему есть висячая вершина

и находить висячие вершины и степени

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

в дереве с $n$ вершинами ровно $n - 1$ ребро (ПР-5)

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

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

повторение: VIS8-019, 7 класс

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

Три графа: что вы видите?

Вершин и рёбер у Г1 $4$ и $4$
Есть ли цикл в Г1? да: $a, b, c$
Какие графы связные? Г1 и Г2
Какой граф — дерево? Г2

Степень вершины $q$ $3$
Висячие вершины Г2 $p, r, t$
Сумма степеней графа с $6$ рёбрами $12$

2,5 мин · практика
Ответы (по клику): 1) Г1: вершины a, b, c, d; рёбра ab, bc, ca, cd — 4 и 4. 2) Да, цикл a–b–c–a. 3) Связные Г1 и Г2; Г3 распался на две части: {x, y} и {z, w, u}. 4) Дерево — Г2: связный и без циклов (Г1 — с циклом, Г3 — несвязный). 5) Степень q равна 3 (рёбра qp, qr, qs). 6) Висячие (степени 1): p, r, t. 7) Каждое ребро добавляет 2 к сумме степеней: 2 · 6 = 12.
Обратить внимание: у дерева Г2 5 вершин и 4 ребра, у Г1 — 4 и 4 (лишнее ребро дало цикл), у Г3 — 5 и 3 (рёбер не хватает для связности). Это подводка к свойству «рёбер на одно меньше» (сл. 8).

R05.2

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

Из любой вершины в любую — ровно один путь

Свойство 1. В дереве любые две вершины соединены ровно одним путём (вершины в пути не повторяются).

путь $D \to G$ : $D B A C G$ длина $4$ ребра

Хотя бы один — дерево связно

Не больше одного — два разных пути вместе дали бы цикл, а циклов в дереве нет

2,5 мин · теория
Путь — последовательность вершин, в которой соседние соединены ребром и вершины не повторяются; длина пути — число рёбер в нём (у пути D–B–A–C–G длина 4, а не 5).
Доказательство. Существование: дерево — связный граф, значит, из D можно дойти до G. Единственность: пусть есть второй путь из D в G (красный пунктир). Идём по двум путям из D до первой вершины, где они расходятся, и до первой общей вершины после неё — участки двух путей между этими вершинами замыкаются в цикл. В дереве циклов нет — противоречие.
Вопрос классу: если в графе есть две вершины, между которыми два разных пути, — может ли он быть деревом? (Нет: в нём есть цикл.)

R05.2

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

Путь ищем «через общего предка»

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

$D \to B \to A$ поднимаемся к $A$ : $G$ — в правой ветви

$A \to C \to F \to G$ спускаемся к $G$

длина $5$ число рёбер, не вершин

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

Путь из $K$ в $H$ , длина $K E B A C F H$ ; $6$
Вершины между $E$ и $M$ $B, A, C, F, H$
Самый длинный путь в дереве $K \dots M$ , длина $7$

2,5 мин · практика
Образец: из D ведёт единственное ребро — в B; G лежит в правой части дерева, поэтому идём через A. Путь D–B–A–C–F–G: 6 вершин, 5 рёбер. Другого пути нет (свойство 1).
1) K–E–B–A–C–F–H, длина 6. 2) Путь E–B–A–C–F–H–M, внутри него вершины B, A, C, F, H (длина 6). 3) Самый длинный путь (диаметр дерева, VIS8-019) соединяет висячие K и M: K–E–B–A–C–F–H–M, длина 7. Проверено перебором всех пар вершин (python).
Подсказка: концы самого длинного пути — всегда висячие вершины; это пригодится на сл. 6.

R05.2

Теория · свойство 2: висячая вершина

В каждом дереве есть висячая вершина

Свойство 2. В дереве, где вершин не меньше двух, есть висячая вершина (степени $1$ ) — и даже две.

1. Идём из любой вершины, каждый раз по новому ребру.

2. В пройденную вершину не вернёмся — получился бы цикл.

3. Вершин конечное число — мы остановимся. Там, где нового ребра нет, вершина висячая.

Из старта — в другую сторону: вторая висячая.

2,5 мин · теория
Доказательство «прогулкой». Стартуем из A, идём A → B → E → G, каждый раз по ребру, по которому ещё не шли. Вернуться в уже пройденную вершину нельзя: вместе с пройденным участком это был бы цикл. Вершин конечное число, значит, прогулка оборвётся. Оборвётся в вершине, где кроме ребра, по которому пришли, других рёбер нет, — это висячая вершина (G).
Вторая висячая: из старта A идём в другую сторону (A → C → H) — H тоже висячая, и H ≠ G. Порядок кликов: три шага прогулки, затем строки доказательства, затем вторая прогулка (бирюзовая).
Почему «вершин ≥ 2»: дерево из одной вершины без рёбер висячих вершин не имеет (степень 0).

R05.2

Образец → сам · висячие вершины и степени

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

Образец: висячие вершины и степени

висячие: $3, 5, 6, 8, 9$ одно ребро

степени: $3, 3, 2, 3$ вершины $1, 2, 4, 7$

$5 + 11 = 16 = 2 \cdot 8$ сумма = $2 \cdot$ рёбра

Сам: дерево из $5$ вершин

Наименьшее число висячих $2$ (путь)
Наибольшее число висячих $4$ (звезда)
Может ли висячая быть одна? нет

2,5 мин · практика
Образец: клик 1 — кольца на висячих вершинах 3, 5, 6, 8, 9; клик 2 — степени остальных (1, 2 и 7 — по 3, вершина 4 — 2). Сумма степеней: 5 · 1 + 3 + 3 + 2 + 3 = 16; рёбер 8 — каждое ребро считается дважды (7 класс).
1) Дерево-«цепочка» из 5 вершин: висячие — только два конца. Меньше двух нельзя (свойство 2: «даже две»). 2) «Звезда»: центр соединён с остальными 4 вершинами — 4 висячие; 5 висячих нельзя: тогда сумма степеней 5, а должна быть 2 · 4 = 8. 3) Нет — в дереве с n ≥ 2 вершинами висячих не меньше двух (концы самого длинного пути).
Попросить учеников нарисовать «цепочку» и «звезду» на 5 вершинах в тетради.

R05.2

Теория · свойство 3: вершины и рёбра

Обрываем висячие вершины по одной

Убрали висячую вершину и её ребро — снова дерево

$n$ и число рёбер уменьшились на $1$ : разность та же

В конце $1$ вершина и $0$ рёбер: разность $1$

рёбер

= n - 1

Свойство 3. В дереве с

n

вершинами ровно

n - 1

ребро.

2,5 мин · теория
Доказательство. По свойству 2 в дереве есть висячая вершина (розовая). Удалим её вместе с единственным ребром: граф остаётся связным и без циклов — снова дерево. Вершин и рёбер стало на 1 меньше, значит, разность «вершины − рёбра» не изменилась. Повторяем, пока не останется одна вершина без рёбер: разность 1 − 0 = 1. Значит, и в исходном дереве рёбер на одно меньше, чем вершин.
По рисунку: 5 и 4 → 4 и 3 → 3 и 2 → 2 и 1 → 1 и 0. Разность всё время 1.
Вопрос: почему после удаления висячей вершины граф остаётся связным? (Через висячую вершину не проходит ни один путь между другими вершинами — у неё одно ребро.)

R05.2

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

Рёбер на одно меньше, чем вершин

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

граф — дерево путь единственный ⇒ нет циклов

$n = 12$ станции — вершины

рёбер $12 - 1$ = $11$ свойство 3

Сам

Дерево с $17$ вершинами: рёбер? $16$
Дерево с $30$ рёбрами: вершин? $31$
Дерево: $10$ вершин и $10$ рёбер? нет, рёбер $9$

R05.2

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

Лишние рёбра — это циклы

Признак. Связный граф с $n$ вершинами и $n - 1$ ребром — дерево.

Связный граф: $n = 6$ , рёбер $9$ . Сколько рёбер удалить, чтобы получить дерево?

в дереве $6 - 1 = 5$ рёбер свойство 3

$9 - 5$ = $4$ рвём только циклы

Добавили к дереву ребро — появился цикл; удалили ребро — граф распался.

2,5 мин · теория (учитель решает пример сам)
Признак (обратное к свойству 3): если граф связный и рёбер на одно меньше, чем вершин, — это дерево. Идея: если бы в нём был цикл, удалили бы ребро цикла — граф остался бы связным; удаляя так рёбра, получили бы дерево с n вершинами и меньше чем n − 1 рёбрами — противоречие со свойством 3.
Пример: шестиугольник с тремя диагоналями 1–3, 3–5, 5–1 (9 рёбер). Клик 1 — зелёным выделено дерево из 5 рёбер (1–2, 1–3, 3–4, 3–5, 5–6); клик 2 — красным перечёркнуты 4 удалённых ребра (2–3, 4–5, 6–1, 1–5). Каждое удалённое ребро лежит на цикле, поэтому связность не теряется. Удалить меньше 4 нельзя: при 6 рёбрах и больше в связном графе на 6 вершинах есть цикл.
Вопрос: можно ли удалить ребро 1–2 вместо 2–3? (Да, получится другое дерево; ответ «4 ребра» от выбора не зависит.)

R05.2

Образец → сам · сколько рёбер удалить

От связного графа — к дереву

Образец: связный граф, $7$ вершин, $10$ рёбер

дерево: $7 - 1 = 6$ рёбер свойство 3

$10 - 6$ = $4$ удаляем лишние

граф связен рвали только циклы

Сам

Связный граф: $9$ вершин, $13$ рёбер. Удалить? $5$
К дереву из $10$ вершин добавили ребро. Есть цикл? да, $10$ рёбер
$6$ вершин, $5$ рёбер, есть цикл. Граф связный? нет

2,5 мин · практика
Образец: клик 1 — зелёное дерево 1–2, 2–3, 2–5, 5–7, 4–7, 3–6 (6 рёбер); после строк решения — красный пунктир на 4 удалённых рёбрах 1–4, 4–5, 5–6, 6–7. Проверено: оставшийся граф связен и без циклов.
1) 13 − (9 − 1) = 5. 2) Да: у дерева 9 рёбер, стало 10; связный граф с 10 вершинами и 10 рёбрами — не дерево, значит, цикл есть (ровно один). 3) Нет: если бы граф был связным, то при 6 вершинах и 5 рёбрах он был бы деревом (признак) — без циклов. Раз цикл есть, граф несвязный (например, треугольник и отдельно цепочка из 3 вершин).

R05.2

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

Сумма степеней дерева — $2 (n - 1)$

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

висячих $k$ , $n = 4 + k$

рёбер $n - 1 = 3 + k$

$12 + k = 2 (3 + k)$

$k$ = $6$

сумма степеней — удвоенное число рёбер (рёбер $n - 1$ )

Сам

$2$ вершины степени $3$ , остальные висячие. Висячих? $4$
$1$ вершина степени $5$ , остальные висячие. Вершин? $6$
из жизни $10$ домов соединяют трубами, чтобы вода дошла до всех, а труб — меньше всего. Труб? $9$

2,5 мин · практика
Образец: сумма степеней всегда вдвое больше числа рёбер (7 класс). Степени: 4 · 3 + k · 1 = 12 + k; рёбер n − 1 = 4 + k − 1 = 3 + k. Уравнение 12 + k = 6 + 2k даёт k = 6. Последний клик — пример такого дерева: 10 вершин, 9 рёбер, сумма степеней 18 ✓.
1) 6 + k = 2(2 + k − 1) ⇒ k = 4 (дерево «H»: 6 вершин, 5 рёбер). 2) 5 + k = 2k ⇒ k = 5, вершин 6 — это «звезда». 3) Наименьшая связная сеть из 10 домов — дерево (лишняя труба дала бы цикл, её можно убрать): 10 − 1 = 9 труб.
При нехватке времени задание 3 — в ДЗ.

R05.2

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

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

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

между любыми двумя вершинами

Висячих — хотя бы две

если вершин $n \geq 2$

Рёбер $n - 1$

$4$ вершины — $3$ ребра

Узнать дерево: связный + рёбер $n - 1$ (или без циклов + рёбер $n - 1$ ).

R05.2

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

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

Где ошибаются	Неверно	Верно
рёбер «столько же»	$10$ вершин — $10$ рёбер	рёбер $10 - 1 = 9$
« $n - 1$ ребро — значит, дерево»	$4$ вершины, $3$ ребра	нужна ещё связность: здесь цикл и отдельная вершина
длину пути считают по вершинам	$A B C$ : длина $3$	длина $2$ — число рёбер
«у дерева может не быть висячих»	дерево из $5$ вершин без висячих	при $n \geq 2$ висячих хотя бы две

R05.2

Найди ошибку

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

а) В дереве $15$ рёбер. Сколько вершин?

$15 - 1 = 14$ вершин

вершин на одну больше, чем рёбер

$15 + 1 = 16$

б) Связный граф, $7$ вершин, $7$ рёбер

«связный — значит, дерево»

у дерева $7 - 1 = 6$ рёбер; лишнее ребро — цикл

не дерево

в) $3$ вершины степени $3$ , остальные $k$ висячие

рёбер $3 + k$ ; $9 + k = 2 (3 + k)$ , $k = 3$

рёбер $n - 1 = 2 + k$

$9 + k = 2 (2 + k)$ , $k = 5$

R05.2

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

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

Сколько вершин и рёбер у дерева на рисунке? $8$ и $7$
Назовите висячие вершины $R, S, U, V$
Путь из $R$ в $U$ и его длина $R N M P T U$ ; $5$
Удалили ребро $MP$ . Сколько частей? $2$
Дерево с $50$ вершинами: рёбер? $49$
Граф: $12$ вершин, $12$ рёбер. Может быть деревом? нет

R05.2

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

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

повыш.В дереве $2$ вершины степени $4$ , одна — степени $3$ , остальные висячие. Сколько висячих? $7$
повыш.Граф без циклов из $3$ частей-деревьев, всего $20$ вершин. Сколько рёбер? $17$
повыш.Из графа на рисунке (каждая вершина соединена с каждой) удаляют рёбра, чтобы получить дерево. Сколько удалить? $6$
докажитеВ дереве с $n \geq 2$ вершинами есть две висячие. концы самого длинного пути

3 мин · практика
В парах, по готовности; ответы — по клику. Задания 3–4 при нехватке времени — в ДЗ.
1) n = 3 + k, рёбер 2 + k; сумма степеней 4 + 4 + 3 + k = 11 + k = 2(2 + k) ⇒ k = 7 (10 вершин, 9 рёбер, сумма 18 ✓).
2) В каждой части рёбер на одно меньше, чем вершин: сумма (вершин части − 1) по трём частям = 20 − 3 = 17.
3) У графа на рисунке 5 · 4 : 2 = 10 рёбер (каждая из 5 вершин соединена с 4 другими, каждое ребро посчитано дважды). Дерево на 5 вершинах — 4 ребра, удалить 10 − 4 = 6.
4) Возьмём самый длинный путь в дереве. Его конец — висячая вершина: если бы из него шло ещё ребро, то либо в вершину вне пути (тогда путь можно удлинить — противоречие), либо в вершину пути (тогда цикл — противоречие). Концов у пути два, значит, висячих хотя бы две.

R05.2 · ОГЭ

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

Дерево опыта: монету бросают трижды

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

$0, 375$

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

$0, 125$

3. Найдите вероятность того, что решка выпадет хотя бы раз.

$0, 875$

Дерево:

15

вершин,

14

рёбер,

8

висячих =

8

исходов.

2,5 мин · практика
Общее условие: симметричную монету бросают три раза. Дерево опыта — дерево в смысле урока: 1 + 2 + 4 + 8 = 15 вершин, 14 рёбер = 15 − 1; висячие вершины — 8 равновозможных исходов, каждому соответствует единственный путь от корня (свойство 1).
1) Благоприятны ООР, ОРО, РОО (подсвечены по клику): 3/8 = 0,375. 2) Только ООО: 1/8 = 0,125. 3) Противоположное событие к «ни разу решка»: 1 − 1/8 = 7/8 = 0,875. Проверено перебором 8 исходов (python).
В бланк ОГЭ — десятичная дробь без единиц: 0,375.

R05.2

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

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

Вариант 1

Путь из $A$ в $G$ , длина; число висячих $4$ ; $4$
Дерево с $23$ вершинами: рёбер? $22$
Связный граф: $8$ вершин, $11$ рёбер. Удалить до дерева? $4$
$3$ вершины степени $3$ , остальные висячие. Висячих? $5$

Вариант 2

Путь из $N$ в $S$ , длина; число висячих $4$ ; $4$
Дерево с $30$ рёбрами: вершин? $31$
Связный граф: $9$ вершин, $12$ рёбер. Удалить до дерева? $4$
$2$ вершины степени $4$ , остальные висячие. Висячих? $6$

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

Итог урока

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

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

Почему путь в дереве единственный?
Как найти висячую вершину «прогулкой»?
Сколько рёбер в дереве с $n$ вершинами?
Когда связный граф — дерево?

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

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

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

VIS8-020 · Свойства дерева

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

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

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

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

Объяснять, почему есть висячая вершина

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

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

Три графа: что вы видите?

Из любой вершины в любую — ровно один путь

Путь ищем «через общего предка»

Образец: путь из D в G и его длина

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

В каждом дереве есть висячая вершина

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

Образец: висячие вершины и степени

Сам: дерево из 5 вершин

Обрываем висячие вершины по одной

Рёбер на одно меньше, чем вершин

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

Сам

Лишние рёбра — это циклы

От связного графа — к дереву

Образец: связный граф, 7 вершин, 10 рёбер

Сам

Сумма степеней дерева — 2(n−1)

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

Сам

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

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

Висячих — хотя бы две

Рёбер n−1

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

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

а) В дереве 15 рёбер. Сколько вершин?

б) Связный граф, 7 вершин, 7 рёбер

в) 3 вершины степени 3, остальные k висячие

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

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

Дерево опыта: монету бросают трижды

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

Вариант 1

Вариант 2

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

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

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

VIS8-020 · Свойства дерева

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

Сам: дерево из $5$ вершин

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

Образец: связный граф, $7$ вершин, $10$ рёбер

Сумма степеней дерева — $2 (n - 1)$

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

Рёбер $n - 1$

а) В дереве $15$ рёбер. Сколько вершин?

б) Связный граф, $7$ вершин, $7$ рёбер

в) $3$ вершины степени $3$ , остальные $k$ висячие