Обобщенные задачи коммивояжера и планарные графы презентация

задачи о максимальной циркуляции.

заданное подмножество городов, затратив минимум средств на путешествие либо минимум средств на максимальный переход.
2. Замкнутая постановка задачи: коммивояжер должен объехать заданное подмножество городов вернуться в город из которого стартовал, затратив минимум средств на путешествие либо минимум средств на максимальный переход.

заданного подмножества.
2. Отсутствует ограничение на число посещений каждой вершины.

контур а1=1,2,3,4,7,5,6,1 -.
Гамильтонов контур а2=5,3,4,6,1,2,7,5 -.

коммивояжера

2

5

1

4

3

Возможные решения: «желтый», «красный» или «зеленый» контуры (последний – сложный контур).

Исходный граф – полный, на рисунке показаны только возможные решения

3.)

2

3

4

1

12


12

1 5 9 1 3 10


4


2

при условии, что «обязательными» являются все вершины множества Х.
М

-.
L2=5,3,4,6,1,2,7 -.

Стартовая вершина первого пути.

Стартовая вершина второго пути.

терминальная – «4».

Графовая интерпретация обобщенной разомкнутой задачи коммивояжера

2

5

1

4

3

Возможные решения: «желтый», «красный» или «зеленый» пути (последний – сложный путь).

Исходный граф – полный, на рисунке показаны только возможные решения

3; стартовая – 1, терминальная - 3)

2

3

4

1

12


12

1 5 9 1 3 10


4


2

что : стартовой вершиной является первая, терминальной – третья, обязательными вершинами: 1, 2, 3.

1

4

3

2

3

2

4 5 7 9 11 1 2

10
8
6

3

задачи коммивояжера

минимального разреза R или максимальной циркуляции S.
Шаг 2. Построить орграф G’(X’,U’), двойственный графу G(X,U).
Шаг 3. Модифицировать G’(X’,U’), добавив к каждой дуге множества U’ параллельную и встречно ориентированную дугу с нулевым весом. Полученный орграф обозначить G”(X”,U”).
Шаг 4. На G”(X”,U”) решить обобщенную замкнутую задачу коммивояжера при условии, что множество обязательных вершин равно Х”. Длину пути коммивояжера обозначить R1.
Шаг 5. Сравнить величины R, S, и R1.

1
3 7

9

2
Контуры:
Y1 = 1-3-1;
Y2=2-3-2;
Y3=1-2-3-1.

2

3

1

3 1




2

2 1
3
7

9

2

4

1

3

0


1
0 7 0 9 0

2
0

3

3

4

1

2

0


0 2


3

1

R1 = 6.

максимальную циркуляцию S и минимальный разрез R, затем построить двойственный ему орграф G’(X’,U’), преобразовать его в G”(X”,U”), и на этом графе решить обобщенную задачу коммивояжера. Ответ R1 сравнить с S и R.
M