§ 17. Графы

1. Моделирование

1
Моделирование
§ 17. Графы
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

2. Графы

Моделирование, 9 класс
2
Графы
«От посёлка Васюки три дороги идут в
посёлки Солнцево, Грибное и Ягодное.
Между Солнцевым и Грибным и между
Грибным и Ягодным также есть дороги.
Кроме того, есть дорога, которая идет
из Грибного в лес и возвращается
обратно в Грибное».
?
Как структурировать?
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

3. Графы

Моделирование, 9 класс
3
Графы
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
Граф – это набор вершин (узлов) и связей между ними
(рёбер).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

4. Матрица и список смежности

Моделирование, 9 класс
4
Матрица и список смежности
Матрица смежности
A
B
C
D
A
B
C
D
A
0
1
1
0
B
1
0
1
1
C
1
1
1
1
D
0
1
1
0
2
3
5
2
петля
Степень вершины – это количество связанных с ней
рёбер (петля считается дважды!).
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

5. Постройте матрицу смежности

Моделирование, 9 класс
5
Постройте матрицу смежности
A
A
D
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
B
D
D
C
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

6. Постройте матрицу смежности

Моделирование, 9 класс
6
Постройте матрицу смежности
A
A
D
D
B
C
B
A
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
D
A
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

7. Нарисуйте граф

Моделирование, 9 класс
7
Нарисуйте граф
A
A
B
C
D
0
1
1
B
0
1
0
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
1
1
0
D
1
0
0
A
A
B
C
D
1
0
1
B
1
1
0
C
0
1
D
1
0
1
1
http://kpolyakov.spb.ru

8. Нарисуйте граф

Моделирование, 9 класс
8
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
0 1
C D E
1 1 0
1 0 1
0 1
0
0
1 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
0
0
1 1
1 0
1 0
C D E
1 1 1
1 0 0
0 1
0
0
1 0
http://kpolyakov.spb.ru

9. Нарисуйте граф

Моделирование, 9 класс
9
Нарисуйте граф
A
B
C
D
E
A B
0
0
1 1
1 0
1 1
C D E
1 1 1
1 0 1
0 1
0
0
1 0
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
0
0
0 1
1 0
0 1
C D E
0 1 0
1 0 1
1 1
1
0
1 0
http://kpolyakov.spb.ru

10. Связность графа

Моделирование, 9 класс
10
Связность графа
A
C
B
D
!
Связный граф – это
граф, между любыми
вершинами которого
существует путь.
Солнцево
A
C
B
D
Грибное
Васюки
Ягодное
компоненты связности
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

11. Дерево – это граф?

Моделирование, 9 класс
11
Дерево – это граф?
!
Дерево – это связный граф без
циклов (замкнутых путей).
A
A
C
B
D
B
ABC
BCD
D
ABDC
CCC…
К.Ю. Поляков, Е.А. Ерёмин, 2018
H
C
E
F
G
J
дерево
http://kpolyakov.spb.ru

12. Взвешенные графы

Моделирование, 9 класс
12
Взвешенные графы
2
Солнцево
8
A
Грибное
12
5
B
Ягодное
Васюки
2
C
5
12
4
8
4
6
D
6
вес ребра
Весовая матрица:
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
A
B
C
D
12
8
B
12
5
6
C
8
5
2
4
D
6
4
http://kpolyakov.spb.ru

13. Постройте весовую матрицу

Моделирование, 9 класс
13
Постройте весовую матрицу
A
A
4
1
3
B
3
1
A
C
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
2
C
D
D
1
2
B
C
4
A
B
D
C
D
A
B
C
D
http://kpolyakov.spb.ru

14. Постройте весовую матрицу

Моделирование, 9 класс
14
Постройте весовую матрицу
2
A
D
1
3
A
4
B
A
B
C
D
К.Ю. Поляков, Е.А. Ерёмин, 2018
C
C
1
D
2
1
B
1
B
A
A
D
C
4
B
C
D
A
B
C
D
http://kpolyakov.spb.ru

15. Нарисуйте граф

Моделирование, 9 класс
15
Нарисуйте граф
A
A
B
C
D
B
4
C
3
4
3
D
2
6
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
6
A
B
C
D
A
B
C
2
2
3
4
5
D
3
4
5
http://kpolyakov.spb.ru

16. Нарисуйте граф

Моделирование, 9 класс
16
Нарисуйте граф
A
B
C
D
E
A B
4
4
3
2
7
C D E
3
7
2
6
6
1
1
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
2
2
5
3
6
C D E
5
6
3
1
1
http://kpolyakov.spb.ru

17. Нарисуйте граф

Моделирование, 9 класс
17
Нарисуйте граф
A B
A
B
C 2
D 2
E 6
2
C D E
2 2 6
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
C
D
E
A B
5
5
2
5
6
C D E
2
6
5
2
2
3
3
http://kpolyakov.spb.ru

18. Кратчайший путь (перебор)

Моделирование, 9 класс
18
Кратчайший путь (перебор)
A B
2
A
B 2
C 4 1
D
E 6
C D E
4
6
1
5 1
5
3
1 3
Определите кратчайший путь
между пунктами A и D.
A
2
B
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2018
D
7
http://kpolyakov.spb.ru

19. Кратчайший путь

Моделирование, 9 класс
19
Кратчайший путь
A B
2
A
B 2
C 4 1
D
7
E
C D E
4
1
7
3 5
3
3
5 3
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и E.
http://kpolyakov.spb.ru

20. Кратчайший путь

Моделирование, 9 класс
20
Кратчайший путь
A B
A
B
C 3
D 1
E
4
C D E
3 1
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

21. Кратчайший путь

Моделирование, 9 класс
21
Кратчайший путь
A B
A
B
C 3
D 1
E 1
4
C D E
3 1 1
4
2
Определите кратчайший
путь между пунктами A и B.
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

22. Кратчайший путь

Моделирование, 9 класс
22
Кратчайший путь
A B
A
B
C 3
D 1
E 4
4
C D E
3 1 4
4
2
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

23. Кратчайший путь

Моделирование, 9 класс
23
Кратчайший путь
A B
A
B
C
D 1
E
4
1
C D E
1
4
1
4 2
4
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
Определите кратчайший
путь между пунктами A и B.
http://kpolyakov.spb.ru

24. Ориентированные графы (орграфы)

Моделирование, 9 класс
24
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
Весовая матрица
может быть
несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2018
A
B
A
A
B
C
D
12
C
5
12
4
Васюки
8
4
D
6
B
12
C
8
5
D
6
4
4
http://kpolyakov.spb.ru

25. Нарисуйте орграф

Моделирование, 9 класс
25
Нарисуйте орграф
A B
A
B 2
C 3
D 1
E
C D E
3 1
4
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
A
B
C 3
D
E
4
2
C D E
5 1
6 4
3
3
http://kpolyakov.spb.ru

26. Нарисуйте орграф

Моделирование, 9 класс
26
Нарисуйте орграф
A B
A
B
C
D
E 4
4
C D E
3 1 4
4
2
2
2
К.Ю. Поляков, Е.А. Ерёмин, 2018
A B
A
B
C 3
D 1
E 1
4
2
1
C D E
1
4
1
4 2
4
2
http://kpolyakov.spb.ru

27. Количество путей из А в Ж

Моделирование, 9 класс
27
Количество путей из А в Ж
Б
1
Д
1+1+1=3
1
А
1
1+1+1+1+3=7
Ж
Г
В
!
1
Е 1
NЖ= NД + NБ + NГ + NВ + NЕ
К.Ю. Поляков, Е.А. Ерёмин, 2018
http://kpolyakov.spb.ru

28. Количество путей из А в К

Моделирование, 9 класс
28
Количество путей из А в К
Д
Б
B
З
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
Ж
И
http://kpolyakov.spb.ru

29. Количество путей из А в К

Моделирование, 9 класс
29
Количество путей из А в К
Д
Б
B
З
Е
А
К
Г
К.Ю. Поляков, Е.А. Ерёмин, 2018
Ж
И
http://kpolyakov.spb.ru

30. Количество путей из А в К

Моделирование, 9 класс
30
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru

31. Количество путей из А в К

Моделирование, 9 класс
31
Количество путей из А в К
Е
Б
B
Ж
А
К
Г
Д
К.Ю. Поляков, Е.А. Ерёмин, 2018
З
И
http://kpolyakov.spb.ru