Введение в теорию графов презентация

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

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

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

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

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

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

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

Матрица смежности
- табличная форма представления графа
номера вершин
несмежные вершины

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

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

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

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

ПРЕОБРАЗОВАНИЕ ГРАФА В ОСТОВНОЕ СВЯЗНОЕ ДЕРЕВО МИНИМАЛЬНОГО ВЕСА.
цикломатическое число
γ = m – n + 1
m – количество ребер
n – количество вершин
V3
V4
R23
R15
R45
R35
R25
R34
V5
R12
V2
V1
γ = 8 – 5 + 1= 4

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

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

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

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