Дискретная математика: "Графы" - (курсовая)
Дискретная математика: "Графы" - (курсовая)
Дата добавления: март 2006г.
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. Это не увеличит оценку. В итоге имеем совершенное паросочетание с минимальным весом:
Прадерево разбиений: