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

1. Основные понятия теории графов

ДУГА {A,B}
Ориентированный Граф G(V,E)
A
B
D
C
ВЕРШИНА D
ДУГА {B,A}
ЦИКЛ (Петля)
МНОЖЕСТВО ВЕРШИН
МНОЖЕСТВО ДУГ

Неориентированный Граф G(V,E)
A
B
D
C
ВЕРШИНА А
(B,A)=(A,B)
МНОЖЕСТВО ВЕРШИН
МНОЖЕСТВО РЕБЕР
РЕБРО (A,B)
E
ИЗОЛИРОВАННАЯ ВЕРШИНА
ВИСЯЧАЯ ВЕРШИНА

Ориентированные и неориентированные графы
Ориентированный граф G(V,E),
V = {1,2,3,4,5,6} E = {{1,2}, {2,2}, {2,4}, {2,5}, {4,1}, {4,5}, {5,4}, {6,3}}
Неориентированный граф G(V,E),
V = {1,2,3,4,5,6} E = {(1,2), (1,5), (2,5), (3,6)}
Подграф графа (а), порожденный множеством вершин {1,2,3,6}

Основные понятия
Вершина графа
Смежная
Изолированная
Висячая
Степень вершины исходящая, входящая
Ребро (дуга) графа
Инцидентность
вес
Дуга-цикл
Совокупность дуг
Путь длины k
Цикл
Ациклический граф
Связный граф
Сильно связный граф
Полный граф
Пустой граф
Лес
Дерево в графе

Пути и циклы в графе
A
B
D
C
E
G
H
I
J
F

Изоморфизм графов
ИЗОМОРФНЫЕ ГРАФЫ
НЕИЗОМОРФНЫЕ ГРАФЫ

Подграфы
A
B
D
C
E
A
B
D
C
E
G(V,E)
G’(V’,E’)
G’ подграф G, если E’⊆E и V’ ⊆ V
G’ суграф G, если E’⊆E и V’ = V

Клики в графе
A
B
D
C
E
F
G

Двудольные графы
A
B
D
C
E
F
G

Планарные и плоские графы
A
B
D
C
E
F
A
B
D
C
E
F
Планарный граф
Плоский граф

2. Алгоритмы на графах

Минимальные покрывающие деревья
Имеется граф G(V,E)
Каждому ребру (u,v) задан неотрицательный вес w(u,v)
Задача: найти подмножество Т ⊆Е, связывающее все вершины, для которого минимален суммарный вес
w(T)=∑w(u,v)
(u,v)εT

Отличия теории и практики
A
B
C
D
A
B
C
D
A
B
C
D
А
B
C
кратчайшее дерево:
А - без дополнительных вершин
В - с дополнительной вершиной
С – дерево Штейнера

Алгоритм Краскала шаг 0
Суммарная длина деревьев = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 1
Суммарная длина деревьев = 1
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 2
Суммарная длина деревьев = 3
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 3
Суммарная длина деревьев = 5
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 4
Суммарная длина деревьев = 9
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 5
Суммарная длина деревьев = 13
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 6
Суммарная длина деревьев = 20
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 7
Суммарная длина деревьев = 28
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 8
Суммарная длина деревьев = 37
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Краскала шаг 9
Суммарная длина деревьев = 37
A
H
G
I
B
F
C
D
E
4
8
2
1
2
4
7
9

Алгоритм Прима
Начало алгоритма: с произвольной вершины
К текущему дереву присоединяется смежная вершина с кратчайшим ребром.
Окончание алгоритма: либо все вершины подключены, либо невозможно подключить ни одно ребро.

Алгоритм Прима шаг 0
Суммарная длина дерева = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 1
Суммарная длина дерева = 0
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 2
Суммарная длина дерева = 4
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 3
Суммарная длина дерева = 12
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 4
Суммарная длина дерева = 14
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 5
Суммарная длина дерева = 18
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 6
Суммарная длина дерева = 20
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 7
Суммарная длина дерева = 21
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 8
Суммарная длина дерева = 28
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 9
Суммарная длина дерева = 37
A
H
G
I
B
F
C
D
E
4
8
11
2
7
1
6
2
4
7
8
9
14
10

Алгоритм Прима шаг 10
Суммарная длина дерева = 37
A
H
G
I
B
F
C
D
E
4
2
1
2
4
7
8
9

КРАТЧАЙШИЕ ПУТИ В ГРАФЕ
Алгоритм Дейкстры (Дийкстры)
Алгоритм Ли
Алгоритм А* (А-звездочка)

Алгоритм Дейкстры
0
∞
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞
∞
3
2
Ищем путь из S ? V

Алгоритм Дейкстры
0
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞
3
2
∞
∞

Алгоритм Дейкстры
0
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
∞
3
2
5
10

Алгоритм Дейкстры
0
10
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
∞
5
∞
3
2

Алгоритм Дейкстры
0
8
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5
3
2
14
7

Алгоритм Дейкстры
0
8
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5
3
2
14
7

Алгоритм Дейкстры
0
8
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5
3
2
13
7

Алгоритм Дейкстры
0
8
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5
3
2
13
7

Алгоритм Дейкстры
0
8
V
10
5
7
2
9
1
8
4
6
U
S
X
Y
5
3
2
9
7

Алгоритм А*
(Алгоритм оптимального поиска)
S
V’
V
F
9
11
g(v)
h(v)
F(v)=g(v)+h(v)

Оценка длины пути
Точная длина
Минимальная оценка
Манхеттеновская длина

Алгоритм А*
g(v) – стоимость пути от финиша до вершины v.
h(v) – нижняя оценка стоимости пути от вершины v до старта.
f(v)=g(v)+h(v) – нижняя оценка стоимости пути от старта к финишу через вершину v.