Задача о кратчайшем пути

Дисциплина Дискретная математика

Вид работы	Контрольная
Дата	08.06.2021
Вариант	23

Задача 2. Задача  о кратчайшем пути.
Дан связанный взвешенный граф ((V,E),w). Требуется найти: 1) длины кратчайших маршрутов из фиксированной вершины vk  V во все остальные вершины; 2) кратчайший маршрут из вершины vk в наиболее удаленную от нее вершину.
Вес w и k=q0 определяются по коду {q0, q1, q2} из задачи 1.
23 = 0435
q0 = 0, q1 = 4, q2 = 3

Задача 3. Задача  о максимальном потоке.
1.	Номер варианта d=d10 перевести в двоичную запись, получить таким образом значения разрядов bi {0,1}, i=0,…,4
2.	Решить задачу о максимальном потоке для следующего графа, в котором пропускные способности c ребер зависят от параметров bi.
23 = 101112
b0=1; b1=0; b2=1; b3=1; b4=1;

Задача 4. Задача коммивояжера.
1.	Числа q0, q1, q2 берутся из задачи 1.
2.	Решить задачу коммивояжера с матрицей весов.
q0 = 0, q1 = 4, q2 = 3
∞	1	3	0	2
4	∞	4	3	∞
3	1	∞	0	4
0	3	3	∞	2
2	3	∞	3	∞