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

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

Таблица