Типовой расчет графов
¥
¥
-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 |
|
Таблица
23
36
å =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 |
¥ |
|
Продолжаем по
23
36.
Дробим по переходу x4-x5:
Таблица
23E36
45
å =14+0=14
|
x1 |
x2 |
x4 |
||
|
x1 |
¥ |
1 |
01 |
|
|
x5 |
01 |
01 |
1 |
|
|
x6 |
6 |
¥ |
00 |
|
Таблица
23
36
45
å =14+1=15
|
x1 |
x2 |
x4 |
x5 |
||
|
x1 |
¥ |
1 |
01 |
¥ |
|
|
x4 |
00 |
¥ |
¥ |
¥ |
1 |
|
x5 |
01 |
01 |
1 |
¥ |
|
|
x6 |
6 |
¥ |
00 |
00 |
|
Продолжаем по
23
36
45.
Дробим по переходу x5-x1:
Таблица
23
36
45
51
å =14+1=15
|
x2 |
x4 |
||
|
x1 |
1 |
¥ |
1 |
|
x6 |
¥ |
00 |
|
Таблица
23
36
45
51
å =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 |
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.),
обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus.
Помогаем в публикации. Правки вносим бесплатно.
Похожие рефераты: |