Скачать .docx Скачать .pdf

Реферат: Типовой расчет графов

Данная работа является типовым расчетом N2 по курсу"Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана. (Вариант N 17).

Сразу хочу сказать для своих коллег: Граждане! Имейтетерпение и совесть, поймите, что я это делаю для Вас с цельюпомочь разобраться в этой теме, а не просто свалить очередной предмет. Мне известно, как непросто сейчас с литературой, и с информацией вообще. Поиски неизвестно какой книгизанимают много времени, поэтому в конце я привел небольшойсписок литературы, составленный мной из различных источниковв дополнение к списку, написанному ранее в работе по графам(о постановке лаб. работ по алгоритму Прима и Дейкстра), которая, я надеюсь, есть в сети.

Содержание работы:

Типовой расчет состоит из 11-ти задач:

1, 2 и 3 задачи относятся к способам задания графов иопредению их характеристик, таких как диаметр, радиус и т.д.

4 и 5 задачи соответственно на алгоритм Прима и Дейкстра. Здесь я снова отсылаю Вас к более ранней работе (см.выше).

6-я задача о поиске максимального потока в сети (методФорда-Фалкерсона).

7-я задача - Эйлерова цепь (задача о почтальоне).

8-я задача - Гамильтонова цепь.

9-я задача - метод ветвей и границ применительно к задаче о коммивояжере.

10-я задача - задача о назначениях; венгерский алгоритм.

11-я задача - тоже методом ветвей и границ.

Gор(V,X)

Рис. 1

Задача1 Для неориентированного графа G, ассоциированного с графом Gор выписать (перенумеровав вершины) :

а) множество вершин V и множество ребер X, G(V,X);

б) списки смежности;

в) матрицу инцидентности;

г) матрицу весов.

д) Для графа Gор выписать матрицу смежности.

Нумерация вершин - см. Рис 1

а) V={0,1,2,3,4,5,6,7,8,9}

X={{0,1},{0,2},{0,3},{1,2},{1,4},{1,5},{1,6},{1,7},{2,3},{2,5},{3,8},{3,9},{4,5},{4,6},{5,3},{5,6},{5,8},{6,9},{7,8},{7,9},{8,9}}

В дальнейшем ребра будут обозначаться номерами в указанном порядке начиная с нуля.

б) Г0={1,2,3};

Г1={0,2,4,5,6,7};

Г2={0,1,3,5};

Г3={0,2,5,8,9};

Г4={1,5,6};

Г5={1,2,3,4,6,8};

Г6={1,4,5,9};

Г7={1,8,9};

Г8={1,3,5,7,9};

Г9={3,6,7,8};

в) Нумерация вершин и ребер соответственно п. а)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0
3 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0
4 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
5 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 1 1 0 0 0 0
6 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0
7 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0
8 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1
9 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1

г) Показана верхняя половина матрицы, т.к. матрица весов неориентированного графа симметрична относительно главной диагонали.

0 1 2 3 4 5 6 7 8 9
0 ¥ 8 3 5 ¥ ¥ ¥ ¥ ¥ ¥
1 ¥ 1 ¥ 2 2 4 5 ¥ ¥
2 ¥ 2 ¥ 5 ¥ ¥ ¥ ¥
3 ¥ ¥ 1 ¥ ¥ 1 6
4 ¥ 4 2 ¥ ¥ ¥
5 ¥ 2 ¥ 1 ¥
6 ¥ ¥ ¥ 2
7 ¥ 1 1
8 ¥ 6
9 ¥

д) Матрица смежности для графа Gор.

0 1 2 3 4 5 6 7 8 9
0 ¥ 1 1 1 ¥ ¥ ¥ ¥ ¥ ¥
1 -1 ¥ 1 ¥ 1 1 1 1 ¥ ¥
2 -1 -1 ¥ 1 ¥ 1 ¥ ¥ ¥ ¥
3 -1 ¥ -1 ¥ ¥ -1 ¥ ¥ 1 1
4 ¥ -1 ¥ ¥ ¥ 1 1 ¥ ¥ ¥
5 ¥ -1 -1 1 -1 ¥ 1 ¥ 1 ¥
6 ¥ -1 ¥ ¥ -1 -1 ¥ ¥ ¥ 1
7 ¥ -1 ¥ ¥ ¥ ¥ ¥ ¥ 1 1
8 ¥ ¥ ¥ -1 ¥ -1 ¥ -1 ¥ 1
9 ¥ ¥ ¥ -1 ¥ ¥ -1 -1 -1 ¥

Задача 2 Найти диаметр D(G), радиус R(G), количество центров Z(G) для графа G ; указать вершины, являющиеся центрами графа G.

D(G)=2

R(G)=2

Z(G)=10

Все вершины графа G(V,X) являются центрами.

Задача 3 Перенумеровать вершины графа G, используя алгоритмы:

а) "поиска в глубину";

б) "поиска в ширину".

Исходная вершина - a.

а)

б)


Задача 4 Используя алгоритм Прима найти остов минимального веса графа G. выписать код укладки на плоскости найденного дерева, приняв за корневую вершину a.

Вес найденного дерева - 14.

Код укладки дерева: 000011000001111111.

Задача 5 Используя алгоритм Дейкстра найти дерво кратчайших путей из вершины a графа G.

Вес найденного пути - 8.

Задача 6 Используя алгоритм Форда - Фалкерсона, найти максимальный поток во взвешенной двуполюсной ориентированной сети {Gор , a , w}. Указать разрез минимального веса.

Последовательность насыщения сети (насыщенные ребра отмечены кружечками):

1-й шаг

2-й шаг

3-й шаг

4-й шаг

5-й шаг

6-й шаг

7-й шаг

Окончательно имеем:

Как видно из рисунка, ребра {6,9},{7,9},{3,9}, питающие вершину w, насыщенны, а оставшееся ребро {8,9}, питающееся от вершины 8, не может получить большее значение весовой функции, так как насыщенны все ребра, питающие вершину 8. Другими словами - если отбросить все насыщенные ребра, то вершина w недостижима, что является признаком максимального потока в сети.

Максимальный поток в сети равен 12.

Минимальный разрез сети по числу ребер: {{0,1},{0,2},{0,3}}. Его пропускная способность равна 16

Минимальный разрез сети по пропускной способности: {{6,9}, {7,9}, {3,9}, {3,8}, {5,8}, {7,8}}. Его пропускная способность равна 12.

Задача 7 (Задача о почтальоне) Выписать степенную последовательность вершин графа G.

а) Указать в графе G Эйлерову цепь. Если таковой цепи не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлерову цепь.

б) Указать в графе G Эйлеров цикл. Если такого цикла не существует, то в графе G добавить наименьшее число ребер таким образом, чтобы в новом графе можно было указать Эйлеров цикл.

Степенная последовательность вершин графа G:

(3,6,4,5,3,6,4,3,4,4)

а) Для существования Эйлеровой цепи допустимо только две вершины с нечетными степенями, поэтому необходимо добавить одно ребро, скажем между вершинами 4 и 7.

Полученная Эйлерова цепь: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3.

Схема Эйлеровой цепи (добавленное ребро показано пунктиром):

б) Аналогично пункту а) добавляем ребро {3,0}, замыкая Эйлерову цепь (при этом выполняя условие существования Эйлерова цикла - четность степеней всех вершин). Ребро {3,0} кратное, что не противоречит заданию, но при необходимости можно ввести ребра {0,7} и {4,3} вместо ранее введенных.

Полученный Эйлеров цикл: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3,0.

Схема Эйлерова цикла (добавленные ребра показаны пунктиром):

Задача 8

а) Указать в графе Gор Гамильтонов путь. Если такой путь не существует, то в графе Gор изменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов путь можно было указать.

б) Указать в графе Gор Гамильтонов цикл. Если такой цикл не существует, то в графе Gор изменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов цикл можно было указать.

а) Гамильтонов путь (ребра с измененной ориентацией показаны пунктиром):

б) Гамильтонов цикл (ребра с измененной ориентацией показаны пунктиром):


Задача 9 (Задача о коммивояжере) Дан полный ориентированный симметрический граф с вершинами x1, x2,...xn.Вес дуги xixj задан элементами Vij матрицы весов. Используя алгоритм метода ветвей и границ, найти Гамильтонов контур минимального (максимального) веса. Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение, рассмотрев матрицу с элементами ,где . Выполнить рисунок.

Исходная таблица.

x1 x2 x3 x4 x5 x6
x1 ¥ 3 7 2 ¥ 11
x2 8 ¥ 06 ¥ 4 3
x3 6 05 ¥ 7 ¥ 2
x4 6 ¥ 13 ¥ 5 ¥
x5 3 3 3 4 ¥ 5
x6 8 6 ¥ 2 2 ¥

Таблица Е 14

x1 x2 x3 x4 x5 x6
x1 ¥ 1 5 01 ¥ 7 2
x2 8 ¥ 01 ¥ 4 1
x3 6 00 ¥ 7 ¥ 00
x4 1 ¥ 8 ¥ 01 ¥ 5
x5 01 00 00 1 ¥ 00 3
x6 6 4 ¥ 00 00 ¥ 2
2

Дробим по переходу x2-x3:


Таблица 23 å=14+0=14

x1 x2 x4 x5 x6
x1 ¥ 1 01 ¥ 7
x3 6 ¥ 7 ¥ 06
x4 1 ¥ ¥ 01 ¥
x5 01 01 1 ¥ 00
x6 6 4 00 00 ¥

Таблица 23 å=14+1=15

x1 x2 x3 x4 x5 x6
x1 ¥ 1 5 01 ¥ 7
x2 7 ¥ ¥ ¥ 3 03 1
x3 6 00 ¥ 7 ¥ 00
x4 1 ¥ 8 ¥ 01 ¥
x5 01 00 05 1 ¥ 00
x6 6 4 ¥ 00 00 ¥

Продолжаем по 23. Дробим по переходу x3-x6:


Таблица 23E36 å=14+0=14

x1 x2 x4 x5
x1 ¥ 1 01 ¥
x4 1 ¥ ¥ 01
x5 01 01 1 ¥
x6 6 ¥ 00 00

Таблица 2336 å=14+6=20

x1 x2 x4 x5 x6
x1 ¥ 1 01 ¥ 7
x3 01 ¥ 1 ¥ ¥ 6
x4 1 ¥ ¥ 01 ¥
x5 00 01 1 ¥ 07
x6 6 4 00 00 ¥

Продолжаем по 2336. Дробим по переходу x4-x5:

Таблица 23E3645 å=14+0=14

x1 x2 x4
x1 ¥ 1 01
x5 01 01 1
x6 6 ¥ 00

Таблица 233645 å=14+1=15

x1 x2 x4 x5
x1 ¥ 1 01 ¥
x4 00 ¥ ¥ ¥ 1
x5 01 01 1 ¥
x6 6 ¥ 00 00

Продолжаем по 233645. Дробим по переходу x5-x1:

Таблица 23364551 å=14+1=15

x2 x4
x1 1 ¥ 1
x6 ¥ 00

Таблица 23364551 å=14+6=20

x1 x2 x4
x1 ¥ 1 01
x5 ¥ 01 ¥
x6 0 ¥ 00
6

Окончательно имеем Гамильтонов контур: 2,3,6,4,5,1,2.

Прадерево разбиений:

Задача 10 (Задача о назначениях) Дан полный двудольный граф Knn с вершинами первой доли x1, x2,...xn.и вершинами другой доли y1, y2,...yn..Вес ребра {xi,yj} задается элементами vij матрицы весов. Используя венгерский алгоритм, найти совершенное паросочетание минимального (максимального веса). Выполнить рисунок.

Матрица весов двудольного графа K55 :

y1 y2 y3 y4 y5
x1 2 0 0 0 0
x2 0 7 9 8 6
x3 0 1 3 2 2
x4 0 8 7 6 4
x5 0 7 6 8 3

Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.

Второй этап - нахождение полного паросочетания.

y1 y2 y3 y4 y5
x1 2 0 0 0 0
x2 0 7 9 8 6
x3 0 1 3 2 2
x4 0 8 7 6 4
x5 0 7 6 8 3

Третий этап - нахождение максимального паросочетания.

y1 y2 y3 y4 y5
x1 2 0 0 0 0 X
x2 0 7 9 8 6 X
x3 0 1 3 2 2
x4 0 8 7 6 4
x5 0 7 6 8 3
X X

Четвертый этап - нахождение минимальной опоры.

y1 y2 y3 y4 y5
x1 2 0 0 0 0
x2 0 7 9 8 6 5
x3 0 1 3 2 2 1
x4 0 8 7 6 4 2
x5 0 7 6 8 3 3
4

Пятый этап - возможная перестановка некоторых нулей.

y1 y2 y3 y4 y5
x1 3 0 0 0 0
x2 0 6 8 7 5 5
x3 0 0 2 1 1 1
x4 0 7 6 5 3 2
x5 0 6 5 7 2 3
4

Решение с ненулевым значением. Переход ко второму этапу.

Полное паросочетание:

y1 y2 y3 y4 y5
x1 3 0 0 0 0
x2 0 6 8 7 5
x3 0 0 2 1 1
x4 0 7 6 5 3
x5 0 6 5 7 2

Максимальное паросочетание:

y1 y2 y3 y4 y5
x1 3 0 0 0 0 X
x2 0 6 8 7 5 X
x3 0 0 2 1 1
x4 0 7 6 5 3
x5 0 6 5 7 2
X X

Минимальная опора:

y1 y2 y3 y4 y5
x1 3 0 0 0 0 6
x2 0 6 8 7 5 7
x3 0 0 2 1 1 1
x4 0 7 6 5 3 2
x5 0 6 5 7 2 3
4 5

Перестановка нулей:

y1 y2 y3 y4 y5
x1 3 0 0 0 0 6
x2 0 6 8 7 5 7
x3 0 0 2 1 1 1
x4 0 7 6 5 3 2
x5 0 6 5 7 2 3
4 5

Полное паросочетание:

y1 y2 y3 y4 y5
x1 3 0 0 0 0 6
x2 0 6 8 7 5 7
x3 0 0 2 1 1 1
x4 0 7 6 5 3 2
x5 0 6 5 7 2 3
4 5

Максимальное паросочетание:

y1 y2 y3 y4 y5
x1 3 0 0 0 0 X
x2 0 6 8 7 5
x3 0 0 2 1 1 X
x4 0 7 6 5 3 X
x5 0 6 5 7 2
X X X

Минимальная опора:

y1 y2 y3 y4 y5
x1 3 0 0 0 0
x2 0 6 8 7 5 1
x3 0 0 2 1 1
x4 0 7 6 5 3
x5 0 6 5 7 2 2
3

Перестановка нулей:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3 1
x3 2 0 2 1 1
x4 2 7 6 5 3
x5 0 4 3 5 0 2
3

Полное паросочетание:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3
x3 2 0 2 1 1
x4 2 7 6 5 3
x5 0 4 3 5 0

Максимальное паросочетание:

y1 y2 y3 y4 y5
x1 5 0 0 0 0 X
x2 0 4 6 5 3 X
x3 2 0 2 1 1 X
x4 2 7 6 5 3
x5 0 4 3 5 0 X
X X X X

Минимальная опора:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3
x3 2 0 2 1 1
x4 2 7 6 5 3 1
x5 0 4 3 5 0

Перестановка нулей:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3
x3 2 0 2 1 1
x4 0 5 4 3 1 1
x5 0 4 3 5 0

Полное паросочетание:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3
x3 2 0 2 1 1
x4 0 5 4 3 1 1
x5 0 4 3 5 0

Максимальное паросочетание:

y1 y2 y3 y4 y5
x1 5 0 0 0 0 X
x2 0 4 6 5 3 X
x3 2 0 2 1 1 X
x4 0 5 4 3 1
x5 0 4 3 5 0 X
X X X X

Минимальная опора:

y1 y2 y3 y4 y5
x1 5 0 0 0 0
x2 0 4 6 5 3 3
x3 2 0 2 1 1
x4 0 5 4 3 1 1
x5 0 4 3 5 0
2

Перестановка нулей:

y1 y2 y3 y4 y5
x1 6 0 0 0 0
x2 0 3 5 4 2 3
x3 3 0 2 1 1
x4 0 4 3 2 0 1
x5 1 4 3 5 0
2

Полное паросочетание:

y1 y2 y3 y4 y5
x1 6 0 0 0 0
x2 0 3 5 4 2 3
x3 3 0 2 1 1
x4 0 4 3 2 0 1
x5 1 4 3 5 0
2

Максимальное паросочетание:

y1 y2 y3 y4 y5
x1 6 0 0 0 0 X
x2 0 3 5 4 2 X
x3 3 0 2 1 1 X
x4 0 4 3 2 0
x5 1 4 3 5 0 X
X X X X

Минимальная опора:

y1 y2 y3 y4 y5
x1 6 0 0 0 0
x2 0 3 5 4 2 4
x3 3 0 2 1 1
x4 0 4 3 2 0 1
x5 1 4 3 5 0 5
2 3

В результате имеем:

y1 y2 y3 y4 y5
x1 6 0 0 0 0
x2 0 1 3 2 2 4
x3 3 0 2 1 1
x4 0 2 1 0 0 1
x5 1 4 3 5 0 5
2 3

Исходный граф

Полученный граф:

Вес найденного совершенного паросочетания = 12.

Задача 11 Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины xi и yj).

Таблица Е (исходная). Строки - xi , столбцы - yj. å=0

1 2 3 4 5
1 2 01 03 02 02
2 06 7 9 8 6
3 01 1 3 2 2
4 04 8 7 6 4
5 03 7 6 8 3

Дробим по переходу x2 - y1:


Таблица Е21 å=0+8=8

2 3 4 5
1 00 02 01 00
3 01 2 1 1 1
4 4 3 2 02 4
5 4 3 5 03 3

Таблица 21 å=0+6=6

1 2 3 4 5
1 2 01 03 02 00
2 ¥ 1 3 2 01 6
3 01 1 3 2 2
4 04 8 7 6 4
5 03 7 6 8 3

Продолжаем по 21:

Дробим по переходу x4 - y1:

Таблица 21Е41 å=6+4=10

2 3 4 5
1 00 02 01 00
2 1 3 2 01
3 01 2 1 1 1
5 4 3 5 03 3

Таблица 2141 å=6+4=10

1 2 3 4 5
1 2 01 03 02 00
2 ¥ 1 3 2 01
3 01 1 3 2 2
4 ¥ 4 3 2 02 4
5 03 7 6 8 3

Продолжаем по Е21:

Дробим по переходу x5 - y5:

Таблица Е21Е55 å=8+2=10

2 3 4
1 00 01 00
3 01 2 1
4 2 1 01 2

Таблица Е2155 å=8+3=11

2 3 4 5
1 00 02 01 00
3 01 2 1 1
4 4 3 2 02
5 1 01 2 ¥ 3

Продолжаем по Е21Е55:

Дробим по переходу x3 - y2:

Таблица Е21Е55Е32 å=10+0=10

3 4
1 01 00
4 1 01

Далее решение очевидно: x1 - y3 и x4 - y4. Это не увеличит оценку.

В итоге имеем совершенное паросочетание с минимальным весом:

Прадерево разбиений:

Литература

1. Грешилов А.А. Как принять наилучшее решение в реальных условиях:-М.:Радио и связь, 1991.-320с.:ил.

2. Беллман Р. Динамическое программирование: Пер. с англ./Под ред. Н.Н. Воробьева.-М.: ИЛ, 1960.-400 с.

3. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования: Пер с англ./Под ред. А.А. Первозванского.-М.: Наука, 1965.-458 с.

4. Вентцель Е.С. Исследование операций.-М.: Сов. радио, 1972.-551 с.

5. Вильямс Н.Н. Параметрическое программирование в экономике (методы оптимальных решений):-М.:Статистика, 1976.-96с.

6. Гольштейн Е.Г., Юдин Д.Б. Новые направления в линейном программировании:-М.: Сов радио, 1966.- 524 с.

7. Зангвилл У.И. Нелинейное программирование: Пер. с англ./Под ред. Е.Г. Гольштейна.-М.: Сов радио, 1973.- 312 с.

8. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование (справочное руководство).-М.: Наука, 1964.-348 с.

9. Исследование операций. Методологические основы и математические методы: Пер. с англ./ Под ред. И.М. Макарова, И.М. Бескровного.-М.: Мир, 1981.- Т.1.-712 с.

10. Исследование операций. Модели и применение: Пер. с англ./ Под ред. И.М. Макарова, И.М. Бескровного.-М.: Мир, 1981.- Т.1.-712 с.

11. Лазарев В.Г., Лазарев Ю.В. Динамическое управление потоками информации в сетях связи.-М.: Радио и связь, 1983.- 216 с.

12. Мартин Дж. Системный анализ передачи данных.: Пер с англ./ Под ред. В.С. Лапина.-М.: Мир, 1975.- М.2.- 431 с.

13. Монаков В.М., Беляева Э.С., Краснер Н.Я. Методы оптимизации. Пособие для учителя.-М.: Просвещение, 1978.- 175с.

14. Муртаф Б. Современное линейное программирование: Теория и практика. Пер. с англ./Под ред. И.А. Станевичуса.- М.: Мир, 1984.- 224 с.

15. Рокафеллор Р. Выпуклый анализ: Пер. с англ./Под ред. А.Д. Иоффе, В.М. Тихомирова.-М.: Мир, 1973.- 469 с.

16. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации.- М.:- Наука, Физматгиз, 1986.- 326 с.

17. Ху Т. Целочисленное программирование и потоки в сетях: Пер. с англ./Под ред. А.А. Фридмана.- М.: Мир, 1974.-419 с.

18. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации: Пер. с англ./Под ред. Е.Г. Гольштейна. -М.:- Мир, 1972.- 240 с.

19. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ./ Под ред. Б.Г. Сушкова.- М.: Мир, 1984.- 496 с.

20. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование. Теория и конечные методы,- М.:- Физматгиз, 1963.- 775 с.