Graphs_Bunimovich_10_ready

1.

Графы: связность, деревья, планарность
10 класс
По §3 и §4 учебника Бунимовича
С дополнительными задачами и
доказательствами
A
E
B
D
C
01

2.

Граф как модель связей
Вершины представляют объекты.
Рёбра показывают связи между ними.
Парк
В транспортной сети вершины — станции,
рёбра — прямые участки пути.
Школа
Вокзал
Музей
1. Что служит вершинами и рёбрами в графе знакомств?
2. Сколько вершин и рёбер на транспортной схеме?
02

3.

Один граф, разные рисунки
Граф задают вершины и соединения.
Длина и форма линии на рисунке могут
меняться.
A
A
B
Пересечение линий без отмеченной вершины
не создаёт новой вершины.
C
D
C
D
B
3. Почему два рисунка справа задают один граф?
4. Является ли пересечение AC и BD новой вершиной?
03

4.

Неориентированный и ориентированный граф
В неориентированном графе ребро можно
проходить в обе стороны.
A
B
A
B
D
C
D
C
В ориентированном графе направление задаёт
стрелка.
Двусторонние дороги
Односторонние дороги
5. Можно ли пройти из A в D по стрелкам?
6. Можно ли пройти из D в A по стрелкам?
04

5.

Взвешенный граф
Вес ребра — число, связанное с ребром:
расстояние, время или стоимость.
B
Длина маршрута в рёбрах и сумма весов —
разные величины.
4 км
3 км
A
C
10 км
7. Какой маршрут из A в C короче по расстоянию?
8. Сколько рёбер содержит этот маршрут?
05

6.

Мультиграф и петля
Кратные рёбра соединяют одну и ту же пару
вершин.
Петля соединяет вершину с самой собой.
Простой граф не содержит петель и кратных
рёбер.
A
B
3 кратных ребра AB и петля в B
9. Сколько рёбер изображено, если петля считается одним ребром?
10. Что нужно удалить, чтобы получить простой граф?
06

7.

Матрица смежности
Строки и столбцы соответствуют вершинам.
1 означает наличие ребра, 0 — его отсутствие.
Для простого неориентированного графа
матрица симметрична.
a
b
c
d
e
a
0
1
1
0
1
b
1
0
1
0
0
c
1
1
0
1
1
d
0
0
1
0
1
e
1
0
1
1
0
11. Перечислите соседей вершины c.
12. Сколько рёбер задаёт эта матрица?
07

8.

Рисунок по матрице
Алгоритм для простого графа:
1. Обозначить все вершины.
2. Для каждой 1 выше главной диагонали
провести ребро.
3. Нижнюю половину повторно не учитывать.
b
c
a
d
e
13. Проверьте рисунок по матрице предыдущего слайда.
14. Запишите матрицу для цепи A–B–C.
08

9.

Матрица ориентированного графа
В строке x и столбце y стоит 1, если есть
стрелка из x в y.
Симметрия не обязательна.
Сумма строки — число выходящих стрелок,
сумма столбца — входящих.
A
B
C
D
A
0
1
0
0
B
0
0
1
0
C
1
0
0
1
D
0
0
0
0
15. Сколько стрелок входит в C и сколько выходит из C?
16. Восстановите ориентированный граф по матрице.
09

10.

Степень вершины
Степень вершины — число концов рёбер в этой
вершине.
A
B
D
C
Изолированная вершина имеет степень 0.
В простом графе с n вершинами степень не
превосходит n − 1.
deg A = 3
deg C = 3
deg B = 2
deg D = 2
17. Какова максимальная степень в простом графе с 12 вершинами?
18. Какова степень B на слайде 6 с тремя рёбрами AB и петлёй?
10

11.

Сумма степеней вершин
Теорема: сумма степеней равна 2m, где m —
число рёбер.
A
B
D
C
Доказательство: у каждого ребра два конца.
При подсчёте степеней каждое ребро
учитывается дважды.
3 + 2 + 3 + 2 = 10 = 2 · 5
19. Сумма степеней равна 38. Сколько рёбер?
20. Может ли сумма степеней быть равной 27?
11

12.

Чётность и одинаковые степени
Число вершин нечётной степени чётно: сумма нечётных степеней должна быть чётной.
В простом графе с n > 1 хотя бы две степени совпадают. Степени 0 и n − 1 не могут встречаться
одновременно.
21. Можно ли построить граф на 7 вершинах со всеми степенями 3?
22. Могут ли степени простого графа быть 0, 1, 2, 3, 4?
12

13.

Путь и цепь: определения учебника
Путь (маршрут) — последовательность вершин,
соседние из которых соединены ребром.
Повторения разрешены.
Цепь — путь без повторения рёбер.
Вершины в цепи могут повторяться.
B
A
C
D
23. Является ли A–B–C–A–D цепью?
24. Является ли A–B–A–D цепью?
13

14.

Цикл и простой цикл
Цикл — цепь, у которой совпадают начало и
конец.
B
Простой цикл не повторяет вершины, кроме
начальной и конечной.
Длина пути — число пройденных рёбер.
D
A
C
E
25. Является ли A–B–C–A–D–E–A простым циклом?
26. Найдите простой цикл длины 3.
14

15.

Эйлеров цикл
Эйлеров цикл проходит каждое ребро ровно
один раз и возвращается в начало.
B
Теорема Эйлера: в связном графе такой цикл
существует тогда и только тогда, когда все
степени чётны.
D
A
C
E
27. Укажите эйлеров цикл на рисунке.
28. Есть ли эйлеров цикл у графа со степенями 2, 2, 3, 3?
15

16.

Почему работает теорема Эйлера
Необходимость: каждому входу в вершину соответствует выход. Рёбра образуют пары.
Достаточность: строим замкнутую цепь. Если остались рёбра, строим ещё одну цепь из её
вершины и вклеиваем её в обход.
29. Почему обход в графе с чётными степенями не застрянет вне старта?
30. Почему связность важна для достаточности?
16

17.

Эйлеров путь и задача о мостах
Если в связном графе ровно две нечётные
вершины, есть незамкнутый эйлеров путь.
A
B
D
C
Он начинается и заканчивается в нечётных
вершинах.
При четырёх нечётных вершинах такого обхода
нет.
Начало A, конец C
A–B–C–D–A–C
31. Почему у графа справа нет эйлерова цикла?
32. В графе мостов Кёнигсберга степени 3, 3, 3, 5. Возможен ли обход?
17

18.

Связность и компоненты
Связный граф: между любыми двумя
вершинами существует путь.
A
Компонента связности — максимальная
связная часть графа.
Изолированная вершина — отдельная
компонента.
D
B
C
E
F
33. Сколько компонент на рисунке?
34. Сколько рёбер достаточно добавить, чтобы граф стал связным?
18

19.

Полный граф
Простой граф полный, если соединены все
пары различных вершин. Обозначение: Kₙ.
Каждая степень равна n − 1.
2m = n(n − 1), поэтому
m = n(n − 1)/2.
A
E
B
D
C
K₅: 5 вершин, 10 рёбер
35. Сколько рёбер в K₉?
36. Сколько матчей сыграют 12 команд в один круг?
19

20.

Мост и цикл
Мост — ребро, удаление которого увеличивает
число компонент связности.
A
Ребро является мостом тогда и только тогда,
когда оно не входит ни в один цикл.
C
D
B
37. Какое ребро является мостом?
38. Почему AB не является мостом?
20

21.

Дерево
Дерево — связный граф без циклов.
A
В дереве каждое ребро — мост.
Если после удаления xy остался путь из x в y, то
этот путь вместе с xy дал бы цикл.
B
D
C
E
F
39. Почему нарисованный граф является деревом?
40. Что произойдёт после удаления AC?
21

22.

Единственная цепь в дереве
Между любыми двумя вершинами дерева
существует единственная цепь.
A
Существование следует из связности.
Две разные цепи дали бы цикл между местом
расхождения и местом встречи.
B
D
C
E
F
41. Найдите единственную цепь из E в F.
42. Может ли между двумя вершинами дерева быть несколько путей?
22

23.

Число рёбер дерева
Теорема: дерево с n вершинами имеет n − 1
ребро.
A
У дерева с n > 1 есть лист. Удаляем лист и его
ребро. Получаем меньшее дерево.
Повторяем до одной вершины: удалили n − 1
ребро.
B
D
C
E
F
43. Сколько рёбер в дереве с 2024 вершинами?
44. Связный граф имеет 8 вершин и 7 рёбер. Это дерево?
23

24.

Каркас транспортной сети
Остовное дерево, остов, каркас — дерево,
содержащее все вершины исходного связного
графа и часть его рёбер.
A
B
D
C
Удаление ребра цикла сохраняет связность.
Повторяем, пока циклов не останется.
Оранжевые рёбра образуют каркас
45. Сколько рёбер удалить при n = 7 и m = 11, чтобы получить остов?
46. Всегда ли каркас графа единственный?
24

25.

Корень и листья
Корневое дерево имеет выделенную вершину
— корень. Его удобно рисовать по уровням.
A
Лист — вершина степени 1.
В дереве с n > 1 есть как минимум два листа.
B
D
C
E
F
Корень A. Листья D, E, F
47. Сколько листьев может иметь дерево на 5 вершинах: минимум и максимум?
48. В дереве три вершины степени 3, остальные — листья. Сколько листьев?
25

26.

Дерево трёх бросков монеты
Каждый уровень соответствует очередному
броску.
О — орёл, Р — решка.
У каждого нетерминального состояния два
продолжения.
Для независимых бросков честной монеты
каждый полный исход имеет вероятность 1/8.
*
О
ОО
ООО
ООР
Р
ОР
ОРО
РО
ОРР
РОО
РР
РОР
РРО
РРР
49. Сколько листьев у дерева четырёх бросков?
50. Какова вероятность ровно двух орлов за три броска?
26

27.

Остановка при первом орле
*
Монету бросают до первого орла, но не
больше трёх раз.
Конечные исходы: О, РО, РРО, РРР.
Их вероятности различны:
1/2, 1/4, 1/8, 1/8.
О
Р
РО
РР
РРО
РРР
51. С какой вероятностью появится хотя бы один орёл?
52. Почему нельзя ответить 3/4, подсчитав листья?
27

28.

Планарный граф и плоский рисунок
Планарный граф можно нарисовать на
плоскости без пересечений рёбер вне вершин.
B
A
B
Плоский граф — такое изображение.
Наличие пересечений на одном рисунке ещё
не доказывает непланарность.
D
D
C
A
C
Два изображения K₄
53. Почему K₄ планарен?
54. Все ли деревья планарны?
28

29.

Два непланарных графа
K₅: каждая пара из пяти вершин соединена.
K₃,₃: каждая из трёх вершин одной группы
соединена с каждой из трёх вершин другой
группы.
Пример: три дома и три колодца.
A
E
A
B
C
X
Y
Z
B
D
C
K₅
K₃,₃
55. Сколько рёбер в K₃,₃?
56. Достаточно ли неудачных попыток рисования для доказательства?
29

30.

Грани и формула Эйлера
Грани — области плоскости, на которые рёбра
разбивают плоское изображение графа.
Внешнюю область тоже считают.
A
B
1
Для связного плоского графа:
В − Р + Г = 2.
D
2
C
3 (внешняя)
57. Проверьте формулу для рисунка: В = 4, Р = 5.
58. Сколько граней у связного плоского графа с 8 вершинами и 12 рёбрами?
30

31.

Доказательство формулы Эйлера
У дерева Р = В − 1 и одна грань. Поэтому В − Р + Г = 2.
Удаляем ребро цикла: Р уменьшается на 1 и две грани сливаются. Г тоже уменьшается на 1.
Выражение В − Р + Г сохраняется. Продолжаем до дерева.
59. Что происходит с числом граней при удалении ребра цикла?
60. Какова формула для плоского графа с k компонентами?
31

32.

Проверка планарности: расширение
Для простого планарного графа при В ≥ 3:
Р ≤ 3В − 6.
Если нет треугольников: Р ≤ 2В − 4.
Доказательство для связного графа: сумма длин границ граней равна 2Р. Получаем 2Р ≥ 3Г
(или 2Р ≥ 4Г). Подставляем Г = 2 − В + Р.
61. Докажите непланарность K₅ по первому неравенству.
62. Докажите непланарность K₃,₃ по второму неравенству.
63. Может ли простой планарный граф иметь 6 вершин и 13 рёбер?
64. Доказывает ли условие Р ≤ 3В − 6 планарность?
32

33.

Многогранники и итоговые задачи
Для выпуклого многогранника:
В − Р + Г = 2.
Обоснование: выбираем грань и растягиваем остальные на плоскость. Выбранной грани
соответствует внешняя область плоского графа.
65. Проверьте формулу Эйлера для куба.
66. У выпуклого многогранника 12 вершин и 20 граней. Сколько рёбер?
67. Дерево имеет 3 вершины степени 3 и 4 степени 2. Остальные — листья. Сколько листьев?
68. В сети 10 городов и 18 дорог. Сеть связна. Сколько дорог удалить для получения каркаса?
33

34.

Ответы к итоговым задачам
61. K₅: 10 > 3 · 5 − 6 = 9.
62. K₃,₃: 9 > 2 · 6 − 4 = 8.
63. Нет: 13 > 12.
64. Нет. K₃,₃ — контрпример.
65. Куб: 8 − 12 + 6 = 2.
66. Р = 12 + 20 − 2 = 30.
67. 5 листьев.
68. 18 − (10 − 1) = 9 дорог.
34

35.

Что нужно знать и уметь
Различать граф, мультиграф, ориентированный и взвешенный граф.
Строить матрицу смежности и читать её.
Использовать степени для подсчёта рёбер и проверки эйлерова обхода.
Находить компоненты, мосты и каркас.
Применять свойства деревьев и формулу Эйлера.
Основной источник: приложенный учебник, §3–§4, с. 47–68.
Расширение: обозначения Kₙ, точная формулировка критерия планарности,
оценки числа рёбер, формула для нескольких компонент и новые задачи.
35