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

 

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

Данная работа  является  типовым  расчетом  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 с.

Типовой расчет графов Данная работа  является  типовым  расчетом  N2 по курсу "Дискретная математика" по теме "Графы",  предлагаем

Больше работ по теме: