Графы. Моделирование

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