Графы. Деревья

1. Графы. Деревья

2. Графы

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

3. Графы

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

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

Информация и информационные процессы, 10 класс
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
петля
( A(B, C),
B(A, C, D),
C(A, B, С, D),
D(B, C) )
К.Ю. Поляков, Е.А. Ерёмин, 2013
http://kpolyakov.spb.ru

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

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

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

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

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

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

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

Информация и информационные процессы, 10 класс
8
Кратчайший путь (перебор)
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.
2
B
A
4
С
2
6
E
4
1
С
5
D
8
1
С
3
6
3
7
D
9
1
E
4
3
дерево возможных
путей
К.Ю. Поляков, Е.А. Ерёмин, 2013
D
7
http://kpolyakov.spb.ru

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

Информация и информационные процессы, 10 класс
9
Ориентированные графы (орграфы)
Рёбра имеют направление (начало и конец),
рёбра называю дугами.
Солнцево
12
8
Грибное
5
Ягодное
6
!
Весовая матрица
может быть
несимметрична!
К.Ю. Поляков, Е.А. Ерёмин, 2013
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

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

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