Графовые модели. Основные понятия. Задача Коммивояжёра. Тема 6

1. Тема 6. Графовые модели. Основные понятия. Задача коммивояжёра

ТЕМА 6. ГРАФОВЫЕ
МОДЕЛИ. ОСНОВНЫЕ
ПОНЯТИЯ. ЗАДАЧА
КОММИВОЯЖЁРА

2. Основные понятия

ОСНОВНЫЕ ПОНЯТИЯ
Графовые модели изучает специальная теория, называемая теорией графов.
Граф – это схема состоящая из вершин, соединённых между собой системой
линий, которая носит название рёбер графа.
1
2
5
3
4

3. Основные понятия

ОСНОВНЫЕ ПОНЯТИЯ
Рёбра могут быть ориентированными и неориентированными.
Ориентированным называется ребро, имеющее направление.
Ориентированное ребро также называется дугой.
Неориентированным – не имеющее направление.
Ориентированный граф (все
рёбра ориентированные)
A
Неориентированный граф
F
N
M
L
B
D

4.

ОСНОВНЫЕ ПОНЯТИЯ
Кратные величины. Если две вершины соединены более чем одним ребром,
то они называются кратными.
Если ребро берёт начало в вершине и в неё же возвращается, то оно
называется петлёй.
A
B
D
A
B
D

5. Основные понятия

ОСНОВНЫЕ ПОНЯТИЯ
Основоположником
теории
графов,
принято считать Леонарда Эйлера,
который в 1736г. сформулировал задачу о
Кёнигсбергских мостах.
C
Задача состоит в том, что нужно составить маршрут, проходящий через все
части суши. Маршрут начинается в любой
из них, проходит по каждому мосту 1 раз
и заканчивается в пункте выхода.
A
Эйлер изобразил в качестве вершин
участки суши, а в качестве рёбер моcты и
доказал, что задача не имеет решения.
D
B

6.

ОСНОВНЫЕ ПОНЯТИЯ
Сама теория графов стала развиваться в 30-х годах
XX в.
Основу теории графов составляет сеть. Сеть – это
граф, каждой дуге которого ставится в соответствие
число или несколько чисел.
Любая сеть характеризуется:
Структурой, которая показывает какие вершины и
как соединены между собой.
Параметрами дуг, которые могут отражать либо
время переезда, либо расстояние.
Каждая дуга обозначается(i-j), где i – это вершина из
которой берёт своё начало дуга, j – это вершина,
которой заканчивается соответствующая дуга.
F
7
N
2
4
1
5
M
9
L

7. Задача Коммивояжёра

ЗАДАЧА КОММИВОЯЖЁРА
Постановка задачи
От задачи о Кёнигсбергских мостах можно перейти к задаче составления
маршрута путешествия или задаче коммивояжёра. Её суть в следующем: нужно
составить маршрут, который проходит через все пункты по одному разу,
начинающийся и заканчивающийся в пункте выезда, такой, чтобы оптимизировать
некоторые параметры.

8. Условие задачи

УСЛОВИЕ ЗАДАЧИ
Из пункта i
1
2
5
3
4
1
2
3
4
5
1
0
1
8
14
10
2
10
0
9
10
8
В пункт j
3
4
25
25
10
15
0
20
24
0
25
27
5
10
2
10
15
0
В таблице приведено время переезда из пункта i в пункт j, причём в общем
случае ti-j≠tj-i, что может быть связано с неровностью дороги. Решение
происходит с помощью развёрнутых сетей дорог, для каждой сети составляются
маршруты, подсчитывается суммарное время переезда и далее находится
минимальное из всех F.

9. Решение

РЕШЕНИЕ
10
1
2
3
4
5
10
1
8
10
8
2
2
8
5
1
10
10
1
2
2
2
5
10
1
5
2
5
1
1
25
10
3
25
2
8
10
25
1
3
25
3
5
2
5
3
4
20
20
20
27
15
25
20
24
4
4
4
4
4
3
4
3
14
14
10
24
24
20
15
10
1
F=71 у.е.вр.
1
F=62 у.е.вр.
2
F=66 у.е.вр.
3
F=71 у.е.вр.
3
F=65 у.е.вр.
4
F=66 у.е.вр.
5
F=69 у.е.вр.
5
F=68 у.е.вр.

10. Ответ

ОТВЕТ
F (оптимальное) = 62 у.е.д
1
2
5
3
4