r>
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, використовуючи алгоритми:
а) "Пошуку в глибину";
б) "Пошуку в ширину". p> Вихідна вершина - a.
а)
В
б)
В
Задача 4 Використовуючи алгоритм Прима знайти кістяк мінімальної ваги графа G. виписати код укладання на площині знайденого дерева, прийнявши за кореневу вершину a.
В
Вага знайденого дерева - 14.
Код укладання дерева: 000011000001111111.
Задача 5 Використовуючи алгоритм Дейкстра знайти Дерво найкоротших шляхів з вершини a графа G.
В
Вага знайденого шляху - 8.
Задача 6 Використовуючи алгоритм Форда - Фалкерсона, знайти максимальний потік у зваженій двуполюсной орієнтованої мережі {Gор, a, w}. Вказати розріз мінімальної ваги. br/>
Послідовність насичення мережі (насичені ребра ві...
