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

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



Данная работа  является  типовым  расчетом  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, используя алгоритмы:

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

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

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

а)



б)




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







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



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

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







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



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



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

1-й шаг





2-й шаг





3-й шаг





4-й шаг



5-й шаг





6-й шаг





7-й шаг



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





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

	Максимальный поток в сети равен 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 с.