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

СОДЕРЖАНИЕ

Обобщенные задачи коммивояжера и их решение перебором.
Связь обобщенной задачи коммивояжера и

ЧАСТЬ 1

ОБОБЩЕННЫЕ ЗАДАЧИ КОММИВОЯЖЕРА

Содержательные постановки обобщенных задач коммивояжера

1. Разомкнутая постановка задачи: коммивояжер должен объехать

Основные отличия от «классических» постановок

1. К посещению коммивояжером обязательны только вершины

Графовая интерпретация «классической» замкнутой задачи коммивояжера

1

2

7

4

3

5

6

Гамильтонов

Подмножество «обязательных» вершин : {1, 2, 4}.

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

Обозначения и определения

Формальная постановка «классической» аддитивной замкнутой задачи коммивояжера

Формальная постановка обобщенной аддитивной замкнутой задачи коммивояжера

Решение обобщенной замкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2,

САМОСТОЯТЕЛЬНО

На орграфе G(X,U), заданном матрицей М, решить замкнутую обобщенную задачу коммивояжера

Графовая интерпретация «классической» разомкнутой задачи коммивояжера

1

2

7

4

3

5

6

L1=1,2,3,4,7,5,6

Формальная постановка «классической» аддитивной разомкнутой задачи коммивояжера

Подмножество «обязательных» вершин : {1, 2, 4}, стартовая вершина – «1»,

Формальная постановка «обобщенной» аддитивной разомкнутой задачи коммивояжера

Решение обобщенной разомкнутой задачи коммивояжера перебором (обязательными являются вершины 1, 2,

Самостоятельно

Решить перебором разомкнутую обобщенную задачу коммивояжера на графе G(X,U) при условии,

ЧАСТЬ 2

Связь задачи на разрыв контуров в сильносвязном орграфе и обобщенной

Алгоритм 1

Шаг 1. На сильносвязном планарном взвешенном орграфе G(X,U) определить величину

ПРИМЕР 1, шаг 1

1

2

3

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

ПРИМЕР 1 ШАГИ 2 - 4

1

3

2

3

4

2

1
2 1
3
7
9

2

4

1

3