Типовой расчет графов - (реферат)
p>г) Показана верхняя половина матрицы, т. к. матрица весов неориентированного графа симметрична относительно главной диагонали.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оризменить ориентацию наименьшего числа ребер таким образом, чтобы в новом графе Гамильтонов цикл можно было указать.
а) Гамильтонов путь (ребра с измененной ориентацией показаны пунктиром):
