Введение в теорию графов

1. Введение в теорию графов

2. Граф

G = (V, R)
V – множество вершин
R - множество ребер, соединяющих пару вершин
R12
V2
R23
R25
V5
R35
V3
V1
R34
R15
R14
R45
V4
Мощность множества – количество вершин (ребер)

3. вершины

смежные
не смежные
- соединяются ребром
- не соединяются ребром
R12
V2
R23
V3
R25
V6
V1
V5
R35
R34
R15
R14
R45
V4
V6 – изолированная вершина

4. Степень вершины

- количество инцидентных ей ребер
V1
3
V2
3
V3
3
V4
3
V5
4
R12
V2
R23
R25
V5
R35
V3
V1
R34
R15
R14
R45
V4

5. Маршрут графа

- последовательность чередующихся
вершин и ребер
замкнутый
(цикл)
простая цепь
все вершины и ребра
различны
начальная и конечная
вершины совпадают
R12
V2
R23
R25
V5
R35
V3
V1
R34
R15
R14
R45
V4

6. Ориентированный граф

каждое ребро (дуга) имеет
одно
направление. Дуга – упорядоченная
пара вершин.
входящая степень
вершины
исходящая степень
вершины
- число входящих в
вершину дуг
- число исходящих
из вершины дуг

7.

Определите входящие и
исходящие степени вершин графа:
R21
V2
R23
R12
R32
R24
V1
R14
входящая
V1
V3
R34
V4
V2
V3
V4
исходящая

8. Взвешенный граф (сеть)

ребрам или
дугам графа поставлены
в соответствие числовые величины.
R21
V2
5
R12
4
R23
R32
R24
3
V3
V1
5
R14
8
7
5
R34
V4

9. Матрица смежности

- табличная форма представления графа
номера вершин
1
2
3
4
1
0
35
0
17
2
35
0
32
0
3
0
32
0
18
4
17
0
18
0
несмежные вершины

10.

составить матрицу смежности для
ориентированного графа:
5
V2
R12
4
R23
R32
R24
3
V3
V1
5
R14
8
7
5
R34
V4

11. Подграф

граф, у которого
все вершины и ребра
принадлежат исходному графу.
R12
V2
R23
R25
V5
R35
V3
V1
R34
R15
R12
V2
R14
R45
V4
V1
V5
V2
R23
R14
R45
R25
V5
R35
V3
R15
V4

12. Остовной связной подграф

подграф, содержащий все вершины исходного
графа и каждая вершина достижима из
любой другой.
V2
R23
R25
V5
R35
V3
V1
R12
R34
R15
R14
R45
V4
V2
R12
V5
R23
V1
R14
R35
V3
R34
V4

13. Дерево

граф, в котором нет циклов.
V2
R23
R25
V5
R35
V3
V1
R12
R34
R15
R14
R45
V4
V2
V1
V5
R23
R35
V3
R34
V4
остовное связное дерево

14. Преобразование графа в остовное связное дерево минимального веса.

цикломатическое число
γ=m–n+1
m – количество ребер
n – количество вершин
V2
R23
R25
V5
R35
V3
V1
R12
R34
R15
γ = 8 – 5 + 1= 4
R45
V4

15.

Преобразовать граф в остовные
связные деревья:
V2
R23
R25
V5
R35
V3
V1
R12
R34
R15
R45
V4

16. Алгоритм Крускала

Построение остовного связного дерева
минимального веса.
1. Удалить из графа все ребра
V2
R23
6
R25
8
V3
R12
10
7
3
R35
R34
V5
V1
остовной подграф с
изолированными вершинами.
V2
R15 6
V1
V5
R45 4
10
V4
V3
V4

17.

2. Сортировка ребер по возрастанию весов.
V2
R23
6
R25
8
V3
R12
10
7
3
V5
R35
R34
V1
R15 6
4 R14
R45
10
V4
R12
10
R34
R35
10
8
R25
7
R14
R23
R45 4
R15 3
6
6

18.

3. Ребра последовательно включают в остовное дерево по
возрастанию их весов:
10
R12
R34
V2
R23
V1
6
R25
7
3 R
15
V5
R25
7
R14
R45 4
V3
R35
10
8
R23
V4
R45 4
R15 3
6
6

19.

4. Алгоритм заканчивает работу, когда все вершины будут
объединены в одно множество. Оставшиеся ребра не
включаются в остовное дерево.
V2
R23
V3
V1
6
R25
7
R12
10
R34
10
8
3 R
15
V5
R35
R45 4
R14
V4
6
γ = 8 – 5 + 1= 4
вес графа = 3 + 4 + 6 + 7 = 20