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

Свойства деревьев. Плоские графы

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

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

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

R05.3 · R05.4

Цели урока

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

Доказывать единственность пути

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

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

$Р = В - 1$ в дереве, $Р = В - k$ в лесу; находить висячие вершины по степеням (ПР-4)

Узнавать дерево по признаку

и находить, сколько рёбер удалить из связного графа (ПР-4)

Понимать, что такое плоский граф

перерисовывать граф без пересечений, считать грани, применять $В - Р + Г = 2$

1 мин · теория
ПР-4: «Иметь представление о дереве, о вершинах и рёбрах дерева, использовании деревьев при решении задач в теории вероятностей, в других учебных математических курсах и задач из других учебных предметов». Плоские графы — единица R05.4; деятельность по ФРП: «свойства плоских графов». Формула Эйлера — главное свойство плоских графов, выводится из свойства «рёбер на одно меньше, чем вершин».
Связь с вероятностью: исход опыта — путь от корня к листу дерева опыта; путь единственный — поэтому исходы = листья (сл. 20).

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

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

Какой из графов — дерево?

Какой граф — дерево? Г1
Вершин и рёбер у Г1 $6$ и $5$
Висячие вершины Г1 $a, c, e, f$
Почему Г2 — не дерево? цикл $p q r s$

Почему Г3 — не дерево? несвязный
Сумма степеней вершин Г2 $10$
Листьев: опыт «монета дважды» $4$

2 мин · практика
Ответы (по клику): 1) Г1 — связный и без циклов. 2) Вершины a, b, c, d, e, f; рёбра ab, cb, bd, de, df — 6 и 5. 3) Степени 1 у a, c, e, f. 4) В Г2 есть цикл p–q–r–s–p. 5) Г3 распался на две части {x, y} и {z, w, u, v}; циклов в нём нет — это «лес» из двух деревьев (пригодится на сл. 8). 6) Каждое из 5 рёбер даёт 2 в сумму степеней: $2 \cdot 5 = 10$ (степени 2, 2, 3, 2, 1). 7) ОО, ОР, РО, РР — 4 листа.
Подводка: у дерева Г1 рёбер на одно меньше, чем вершин; у Г2 рёбер столько же, сколько вершин (лишнее ребро дало цикл); у Г3 — на два меньше (две части). Это свойство докажем на сл. 6.

R05.3

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

Две вершины дерева соединяет ровно один путь

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

путь $E \to H$ : $E B A C G H$ длина $5$

Хотя бы один: дерево — связный граф.

Не больше одного: пусть путей два. Они расходятся в вершине $X$ и впервые снова встречаются в $Y$ — участки от $X$ до $Y$ образуют цикл. Противоречие.

Верно и обратное: если любые две вершины соединены ровно одним путём, граф — дерево.

2 мин · теория
Путь — последовательность вершин, в которой соседние соединены ребром и вершины не повторяются; длина пути — число рёбер (у пути E–B–A–C–G–H длина 5, вершин 6).
Доказательство от противного (клики: путь розовым → пунктир «второй путь» → строки). Если бы из E в H вёл второй путь, то, идя по обоим путям из E, найдём вершину X, после которой пути расходятся, и первую после X вершину Y, где они снова встречаются. Два участка X…Y без общих внутренних вершин вместе дают цикл, а в дереве циклов нет.
Обратное утверждение (углублённый уровень): если путь между любыми двумя вершинами есть — граф связный; если бы в нём был цикл, две его соседние вершины соединялись бы двумя путями (ребром и остальной частью цикла). Значит, граф — дерево. Вопрос классу: можно ли в дереве «вернуться» в вершину, не проходя ребро дважды? (Нет — это и есть цикл.)

R05.3

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

Путь идёт через «развилку»

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

$7 \to 5 \to 2 \to 1$ поднимаемся: $9$ — в другой ветви

$1 \to 3 \to 6 \to 9$ спускаемся к $9$

длина $6$ рёбер, не вершин; путь единственный

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

Путь из $4$ в $8$ и его длина $421368$ ; $5$
Самый длинный путь (диаметр) $7 \dots 8$ или $7 \dots 9$ ; $6$
Сколько всего путей в дереве? $36$

2,5 мин · практика
Образец: клик 1 — розовым подъём 7–5–2–1 до общей «развилки» (вершина 1), клик 2 — бирюзовым спуск 1–3–6–9, клик 3 — кольцо на развилке. Длина 3 + 3 = 6. Другого пути нет (свойство 1), поэтому длина пути — это расстояние между вершинами.
1) 4–2–1–3–6–8: 5 рёбер. 2) Диаметр — 6: пути 7–5–2–1–3–6–8 и 7–5–2–1–3–6–9; концы — висячие вершины. 3) Каждой паре вершин соответствует ровно один путь, поэтому путей столько же, сколько пар: $\frac{9 \cdot 8}{2} = 36$ (правило умножения, каждая пара посчитана дважды). Всё проверено перебором пар (python).

R05.3

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

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

Лемма. В дереве с $n \geq 2$ вершинами есть висячая вершина: конец самого длинного пути.

Убираем висячую вершину с её ребром — снова дерево; В и Р уменьшились на $1$ .

В конце $1$ вершина и $0$ рёбер: $В - Р = 1$ на каждом шаге.

Р = В - 1

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

n

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

n - 1

ребро.

2,5 мин · теория
Лемма (углублённый уровень — с доказательством). Возьмём самый длинный путь $u \dots v$ . Если бы у $v$ был ещё сосед $w$ , кроме предыдущей вершины пути: $w$ вне пути — путь можно удлинить; $w$ на пути — получился бы цикл. Значит, степень $v$ равна 1. Так же $u$ — висячая, поэтому висячих не меньше двух.
Доказательство свойства 2 (клики по рисунку): обрываем висячие 4, 5, 6, затем 2 и 3 (они стали висячими). Каждый раз граф остаётся связным и без циклов, а В и Р уменьшаются на 1 — таблица внизу: 6/5 → 5/4 → … → 1/0. Разность В − Р не меняется и в конце равна 1. Значит, и в исходном дереве $Р = В - 1$ .
Вопрос: почему после удаления висячей вершины граф остаётся связным? (Путь между любыми двумя оставшимися вершинами не проходит через висячую — внутри пути степень вершины не меньше 2.)

R05.3

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

Сколько в дереве висячих вершин?

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

висячих $L$ , $В = L + 3$ три «больших» вершины

$Р = В - 1 = L + 2$ свойство 2

$4 + 3 + 3 + L = 2 (L + 2)$ сумма степеней $= 2 Р$

$L =$ $6$ проверка — рисунком

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

Сам 2. Три вершины степени $3$ , остальные висячие. Висячих? $5$

Сам 3. Дерево: $6$ вершин, сумма степеней $12$ . Возможно? нет

R05.3

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

Лишние рёбра лежат на циклах

Признак. Связный граф и $Р = В - 1$ $\Rightarrow$ дерево.

Лес (без циклов, $k$ частей): $Р = В - k$ .

Связный граф: $В = 7$ , $Р = 10$ . Сколько рёбер удалить, чтобы получилось дерево?

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

$10 - 6 =$ $4$ каждый раз — ребро цикла

2 мин · теория (учитель решает пример сам)
Признак: пусть связный граф с $Р = В - 1$ имеет цикл. Удалим ребро цикла — связность сохранится; повторяя, получим дерево с теми же В вершинами, но меньше чем $В - 1$ рёбрами — противоречие со свойством 2. Лес: каждая из $k$ частей — дерево, $Р_{i} = В_{i} - 1$ ; складываем: $Р = В - k$ .
Пример (клики): зелёным — дерево из 6 рёбер (1–2, 2–3, 2–5, 5–4, 5–6, 5–7); красным перечёркнуты 4 удалённых ребра (1–4, 3–6, 4–7, 6–7). Каждое удалённое ребро лежало на цикле, поэтому граф не распался. Ответ «4» не зависит от того, какие рёбра выбрать.
Число $Р - В + 1$ называют цикломатическим числом графа — названия не требуем, достаточно смысла «сколько рёбер лишние».

R05.3

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

Из скольких деревьев состоит лес?

Образец: граф без циклов, $В = 12$ , $Р = 9$

$9 = 12 - k$ , $k =$ $3$ $Р = В - k$

добавить $k - 1 = 2$ ребра и будет дерево

$Р = 11 = 12 - 1$ проверка

Сам

Лес: $20$ вершин, $4$ дерева. Рёбер? $16$
Связный граф: $В = 10$ , $Р = 15$ . Удалить до дерева? $6$
Связный граф: $В = 8$ , $Р = 8$ . Есть цикл? да

2 мин · практика
Образец: на рисунке три дерева (5, 4 и 3 вершины; рёбер 4 + 3 + 2 = 9). По формуле леса $k = В - Р = 3$ . Клик на рисунке — два зелёных пунктирных ребра соединяют части; циклов не появляется (соединяем разные части), граф стал связным — дерево с 11 рёбрами.
1) $20 - 4 = 16$ . 2) В дереве 9 рёбер, удалить $15 - 9 = 6$ . 3) Да: в дереве на 8 вершинах 7 рёбер; связный граф с 8 рёбрами — не дерево, а значит, в нём есть цикл (ровно один — можно обсудить с сильными учениками).

R05.3 · задача из жизни

Образец → сам · задача из жизни: дороги, сети, турниры

Сеть без лишних дорог — дерево

Образец: $10$ посёлков; из любого можно доехать в любой; дорог — как можно меньше. Сколько дорог?

лишних дорог нет $\Rightarrow$ нет циклов граф — дерево

дорог $10 - 1 =$ $9$ свойство 2

закрыли одну — сеть распалась путь был единственным

Сам 1. Электросеть $25$ домов без лишних проводов. Проводов? $24$

Сам 2. Связная сеть: $12$ компьютеров, $15$ кабелей. Сколько можно отключить, не нарушив связь? $4$

Сам 3. Турнир на вылет, $16$ команд. Сколько матчей? $15$

2 мин · практика
Образец (клики): строки 1–3, затем на карте: бирюзовым — 9 дорог; красный крест — закрыли дорогу 3–6; кольца — две части сети: {1, 2, 3, 4, 5, 8} (розовые) и {6, 7, 9, 10} (жёлтые). В дереве путь между посёлками 3 и 6 был единственным — это и была закрытая дорога. Вывод: в дереве каждое ребро — «мост».
1) $25 - 1 = 24$ . 2) Для связи достаточно дерева из $12 - 1 = 11$ кабелей: отключить можно $15 - 11 = 4$ (каждый раз — кабель, лежащий на цикле). 3) Каждый матч выбивает одну команду, выбыть должны $15$ — матчей $15$ . На языке деревьев: сетка турнира — дерево с $16$ листьями-командами и $15$ вершинами-матчами.

R05.4

Теория · плоский граф и его грани

Пересечение — свойство рисунка, а не графа

Плоский граф — граф, который можно нарисовать на плоскости так, что рёбра пересекаются только в вершинах.

Грань — часть плоскости, ограниченная рёбрами такого рисунка; внешняя часть — тоже грань.

Граф слева плоский: на рисунке справа $4$ грани.

Любое дерево — плоский граф; у его рисунка

1

грань.

2 мин · теория
Клики: 1 — перерисовываем тот же граф (вершины A, B, C, D, рёбра AB, BC, CD, DA, AC, BD): D переносим внутрь треугольника ABC; 2 — нумеруем грани: три треугольника ABD, BCD, CAD и внешняя грань — всего 4. Затем строки справа.
Важно: граф — это «кто с кем соединён», а не картинка. На левом рисунке рёбра AC и BD пересекаются (красный кружок), но это не вершина графа. Граф называется плоским, если существует хотя бы один рисунок без пересечений.
Дерево рисуем «по ярусам» (как дерево опыта): от корня вниз, ветви не пересекаются; ни одного цикла — ни одна часть плоскости не отгорожена, грань одна. Применение: печатные платы, схемы метро, карты — там пересечение проводов или дорог нежелательно.

R05.4

Образец → сам · перерисуйте граф без пересечений

Граф куба — плоский

Образец: вершины и рёбра куба

квадрат $1234$ — внутрь квадрата $5678$ рёбра те же

пересечений нет $\Rightarrow$ граф плоский

граней $6$ $5$ внутри и внешняя

Сам: плоский ли граф?

«Колесо»: цикл из $6$ вершин и центр, соединённый со всеми. Граней? да; $7$
Пятиугольник $A BC D E$ и диагонали $A C$ , $A D$ , $BE$ да: $BE$ — снаружи
«Три домика и три колодца», $9$ тропинок нет

2 мин · практика
Образец (клики): 1 — рядом с «объёмным» рисунком куба (два пересечения, красные кружки) появляется плоский рисунок: квадрат 1234 внутри квадрата 5678, рёбра 1–5, 2–6, 3–7, 4–8; 2 — грани: внутренний квадрат, 4 трапеции и внешняя грань — 6, как граней у куба. Затем строки решения.
1) Да, «колесо» нарисовано без пересечений: 6 треугольников и внешняя грань — 7 (В = 7, Р = 12). 2) Да: $A C$ и $A D$ — внутри пятиугольника, $BE$ проводим снаружи вокруг вершины $A$ ; граней 5 (В = 5, Р = 8). 3) Нет — классическая задача: граф «каждый из 3 домиков с каждым из 3 колодцев» не плоский. Сильным ученикам: в таком графе нет треугольников, значит, каждая грань ограничена хотя бы 4 рёбрами, $4 Г \leq 2 Р = 18$ , $Г \leq 4$ ; а по формуле Эйлера (сл. 13) $Г = 2 - 6 + 9 = 5$ — противоречие.

R05.4

Теория · формула Эйлера для плоского графа

Добавляем ребро — появляется грань

Начало — дерево: $В - Р = 1$ , $Г = 1$ , сумма $2$ .

Новое ребро делит грань на две: Р и Г выросли на $1$ — значение $В - Р + Г$ не изменилось.

В - Р + Г = 2

для связного графа, нарисованного без пересечений

2 мин · теория
Вывод (клики — панели 2–4, затем строки): начинаем с дерева-«звезды» (4 вершины, 3 ребра, 1 грань): $4 - 3 + 1 = 2$ . Каждое новое (розовое) ребро соединяет две вершины на границе одной грани и разрезает её на две части: Р + 1, Г + 1, а разность не меняется. В конце — граф K4 со сл. 11: $4 - 6 + 4 = 2$ .
Почему верно для любого связного плоского графа: внутри него можно выбрать дерево на всех вершинах (как на сл. 8), для него формула верна; остальные рёбра добавляем по одному, каждое делит грань — сумма остаётся равной 2.
Леонард Эйлер (1707–1783) открыл формулу для многогранников: вершины − рёбра + грани = 2 (куб: $8 - 12 + 6 = 2$ ).

R05.4

Образец → сам · формула Эйлера

Сколько граней у плоского графа?

Образец: связный плоский граф, $В = 10$ , $Р = 15$

$Г = 2 - В + Р$ выразили из формулы Эйлера

$Г = 2 - 10 + 15 =$ $7$

проверка: $1 + 5 + 1 = 7$ центр, «трапеции», внешняя

Сам 1. Граф куба: $В = 8$ , $Р = 12$ . Граней? $6$

Сам 2. Связный плоский граф: $В = 6$ , $Г = 4$ . Рёбер? $8$

Сам 3. Дерево из $12$ вершин. Сколько граней? $1$

R05.3 · R05.4

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

Что мы знаем о деревьях и плоских графах

Свойство	Формулировка	Как применяем
единственность пути	две вершины — ровно один путь	длина пути, число путей = число пар
висячая вершина	при $n \geq 2$ их не меньше двух	концы самого длинного пути
вершины и рёбра	$Р = В - 1$	степени, листья, сети без лишних связей
признак дерева	связный и $Р = В - 1$	удалить $Р - В + 1$ рёбер
лес из $k$ деревьев	$Р = В - k$	число частей, сколько рёбер добавить
плоский граф	$В - Р + Г = 2$	грани, рёбра; дерево — $1$ грань

R05.3 · R05.4

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

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

Где ошибаются	Неверно	Верно
длина пути	путь $A B C D$ имеет длину $4$	длина — число рёбер: $3$
рёбра дерева	$10$ вершин — $10$ рёбер	$10 - 1 = 9$ рёбер
признак без связности	$4$ вершины и $3$ ребра — значит, дерево	треугольник и отдельная вершина: не дерево; нужна связность
плоский граф	на рисунке рёбра пересекаются — граф не плоский	может найтись рисунок без пересечений (граф куба)

R05.3 · R05.4

Найди ошибку

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

Задача: в дереве $4$ вершины степени $3$ , остальные висячие. Сколько всего вершин? Сколько граней у рисунка?

Висячих $x$ , вершин $4 + x$ .

Рёбер столько же: $4 + x$ .

$12 + x = 2 (4 + x)$ , $x = 4$ , вершин $8$ .

$Г = В - Р + 2 = 8 - 8 + 2 = 2$ .

Исправление

Рёбер $В - 1 = 3 + x$ (свойство 2)

$12 + x = 2 (3 + x)$ , $x = 6$ , вершин $10$

$Г = 2 - В + Р = 2 - 10 + 9 = 1$

Проверка: у дерева одна грань; сумма степеней $12 + 6 = 18 = 2 \cdot 9$ .

R05.3 · R05.4

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

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

Деревья и лес

Дерево: $30$ вершин. Рёбер? $29$
Дерево: $30$ рёбер. Вершин? $31$
Лес: $15$ вершин, $11$ рёбер. Деревьев? $4$

Признак и плоские графы

Связный граф: $В = 9$ , $Р = 8$ . Дерево? да
Граф: $В = 9$ , $Р = 8$ , есть цикл. Связный? нет
Связный плоский: $В = 6$ , $Р = 9$ . Граней? $5$

R05.3 · R05.4

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

Подумайте и обоснуйте

повыш.В дереве $2$ вершины степени $4$ , $3$ вершины степени $3$ , остальные висячие. Сколько висячих? $9$
повыш.Докажите: если в дереве есть вершина степени $k$ , то висячих вершин не меньше $k$ . по ветви — до листа
повыш.Связный плоский граф, $В = 8$ , каждая грань (и внешняя) — треугольник. Найдите Р и Г. $18$ и $12$
исследованиеСколько путей длины $2$ в «звезде»: центр и $6$ висячих? $15$

2,5 мин · практика
В парах, по готовности; ответы — по клику. Задания 3–4 при нехватке времени — в ДЗ.
1) $В = 5 + L$ , $Р = 4 + L$ ; $8 + 9 + L = 2 (4 + L)$ , $L = 9$ (В = 14, Р = 13, сумма $26$ ). 2) Пусть у $v$ соседи $w_{1}, \dots, w_{k}$ . Из $v$ идём в $w_{i}$ и дальше каждый раз по новому ребру, не возвращаясь, — путь обрывается в висячей вершине $l_{i}$ (вершин конечное число, циклов нет). Листья $l_{i}$ разные: если $l_{i} = l_{j}$ , то из $v$ в $l_{i}$ вели бы два разных пути (через $w_{i}$ и через $w_{j}$ ) — противоречит свойству 1.
3) Каждая грань — 3 ребра, каждое ребро граничит с 2 гранями: $3 Г = 2 Р$ . По Эйлеру $8 - Р + \frac{2}{3} Р = 2$ , $Р = 18$ , $Г = 12$ (проверено перебором, python). 4) Путь длины 2 проходит через центр и соединяет два листа: пар листьев $\frac{6 \cdot 5}{2} = 15$ .

R05.3 · ОГЭ

Формат ОГЭ · линия 10 · дерево опыта

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

Монету бросают $3$ раза. Найдите вероятность того, что орёл выпадет ровно $2$ раза.

исход ↔ единственный путь к листу свойство 1

листьев $2 \cdot 2 \cdot 2 = 8$ , равновозможны; нужных $3$

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

Сам

Вероятность «хотя бы одна решка» $0, 875$
Сколько рёбер у этого дерева опыта? $14$
Монета $4$ раза: «все броски одинаковы» $0, 125$

2,5 мин · практика
Клики: 1 — розовым три пути с двумя орлами (ООР, ОРО, РОО); 2 — отметки у этих исходов; затем строки решения. Каждому листу соответствует ровно один путь от корня, поэтому исходы опыта — это листья дерева (8 равновозможных).
1) Противоположное — «три орла»: $1 - \frac{1}{8} = \frac{7}{8} = 0, 875$ . 2) Вершин $1 + 2 + 4 + 8 = 15$ , рёбер $15 - 1 = 14$ (свойство 2!). 3) Листьев $16$ , подходят ОООО и РРРР: $\frac{2}{16} = \frac{1}{8} = 0, 125$ . Проверено перебором исходов (python, itertools).
В бланк ОГЭ записывают десятичную дробь: «0,375».

R05.3 · R05.4

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

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

Вариант 1

Дерево: $18$ вершин. Рёбер? $17$
Лес из $3$ деревьев, $25$ вершин. Рёбер? $22$
Связный плоский: $В = 7$ , $Р = 10$ . Граней? $5$
Дерево: $3$ вершины степени $3$ , $1$ — степени $2$ , остальные висячие. Висячих? $5$

Вариант 2

Дерево: $23$ ребра. Вершин? $24$
Без циклов: $20$ вершин, $16$ рёбер. Частей? $4$
Связный плоский: $В = 9$ , $Г = 6$ . Рёбер? $13$
Дерево: $2$ вершины степени $3$ , $2$ — степени $2$ , остальные висячие. Висячих? $4$

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

Итог урока

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

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

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

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

Лес: $40$ вершин, $36$ рёбер. Деревьев?
Дерево: $3$ вершины степени $4$ , остальные висячие. Висячих?
Связный плоский граф: $В = 12$ , $Р = 18$ . Граней?
Тренажёр: reknow.ru/8/veroyatnost/8_veroyatnost_derevya.htm

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

VIS8U-018 · Свойства деревьев. Плоские графы

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

Свойства деревьев. Плоские графы

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

Доказывать единственность пути

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

Узнавать дерево по признаку

Понимать, что такое плоский граф

Какой из графов — дерево?

Две вершины дерева соединяет ровно один путь

Путь идёт через «развилку»

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

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

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

Сколько в дереве висячих вершин?

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

Лишние рёбра лежат на циклах

Из скольких деревьев состоит лес?

Образец: граф без циклов, В=12, Р=9

Сам

Сеть без лишних дорог — дерево

Образец: 10 посёлков; из любого можно доехать в любой; дорог — как можно меньше. Сколько дорог?

Пересечение — свойство рисунка, а не графа

Граф куба — плоский

Образец: вершины и рёбра куба

Сам: плоский ли граф?

Добавляем ребро — появляется грань

Сколько граней у плоского графа?

Образец: связный плоский граф, В=10, Р=15

Что мы знаем о деревьях и плоских графах

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

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

Задача: в дереве 4 вершины степени 3, остальные висячие. Сколько всего вершин? Сколько граней у рисунка?

Исправление

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

Деревья и лес

Признак и плоские графы

Подумайте и обоснуйте

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

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

Сам

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

Вариант 1

Вариант 2

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

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

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

VIS8U-018 · Свойства деревьев. Плоские графы

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

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

Образец: граф без циклов, $В = 12$ , $Р = 9$

Образец: $10$ посёлков; из любого можно доехать в любой; дорог — как можно меньше. Сколько дорог?

Образец: связный плоский граф, $В = 10$ , $Р = 15$

Задача: в дереве $4$ вершины степени $3$ , остальные висячие. Сколько всего вершин? Сколько граней у рисунка?

Монету бросают $3$ раза. Найдите вероятность того, что орёл выпадет ровно $2$ раза.