Элементы теории графов

1.

Элементы
теории графов
C
c
g
d
A
a
b
B
e
C
D
c
f
d
A
a
g
e
b
B
D
f
1

2.

Граф — пара
, где — множество вершин,
— множество рёбер, соединяющих вершины
Ориентированный граф
Неориентированный граф
C
A
C
F
A
D
D
E
E
B
F
B
вершина
вершина
Смешанный граф
C
A
F
D
E
B
2

3.

Связный неориентированный
C
A
F
D
E
B
Сильно связный
ориентированный
C
A
Слабо связный
ориентированный
C
F
A
D
D
E
B
F
E
B
3

4.

Несвязный неориентированный
C
A
C
F
F
A
D
E
B
Несвязный ориентированный
D
E
B
4

5.

…с петлями
Ориентированный циклический
C
A
C
F
A
D
F
D
E
E
B
B
Ориентированный ациклический
C
A
F
D
E
B
5

6.

Найдите количество путей и A в H
1
1
B
F
A
D
H
1
2
6
C
E
G
1
3
3
6

7.

Поиск кратчайшего пути: алгоритм Дейкстры
∞ 20
∞ 14 11
9
F
∞9
2
C
14
E
6
11
∞ 22 20
9
A
D
10
0
15
7
B
∞ 7
A
B
C
D
E
F
0
∞
∞
∞
∞
∞
0
7
9
∞
∞
14
7
9
22
∞
14
9
20
∞
11
20
20
11
20
20
20
A F
7

8.

Обход в ширину
A
B
C
D
H
E
F
G
A B C D E F G H
8

9.

Обход в глубину
A
B
C
D
G
D
H
F
H
E
E
C
B
F
G
A
A B E F D G H C
9