Контрольная работа № 2 по дискретной математике

ЗАДАНИЕ 1. Решить задачу коммивояжёра.
Исходные данные:
Значения элементов матрицы расстояний:
a(1,1)=μ a(2.1)=53 a(3.1)=32 a(4.1)=81
a(1.2)=25 a(2.2)= μ a(3.2)=72 a(4.2)=35
a(1.3)=15 a(2.3)=24 a(3.3)= μ a(4.3)=29
a(1.4)=13 a(2.4)=36 a(3.4)=18 a(4.4)= μ
a(1.5)=46 a(2.5)=75 a(3.5)=24 a(4.5)=38
a(5.1)=22 a(5.4)=76 a(5.2)=63 a(5.5)= μ
а(5.3)=34
ЗАДАНИЕ 2. Найти минимальную раскраску графа своего варианта с помощью алгоритма Магу. Определить хроматическое число.
ЗАДАНИЕ 3.
ЗАДАЧА о максимальном потоке на сети.
Исходные данные:
Дана сеть S(X,U)
x0 исток сети; x7 – сток сети, где x0 X; x7X.
1. Вычислить значение максимального потока на сети S, с помощью алгоритма
ФордаФалкерсона.
2. Построить минимальный разрез сети S.
Варианты значений пропускных ri,j способностей дуг сети (значения пропускных способностей дуг ri,j заданы по на-правлению ориентации дуг: от индекса i к индексу j):
r[0,1] = 19 r[4,7] = 34 r[6,3] = 13 r[5,7] = 23
r[0,2] = 15 r[4,2] = 18 r[6,7] = 35 r[5,4] = 26
r[0,3] = 20 r[2,5] = 21 r[2,1] = 11 r[6,5] = 41
r[1,4]=23 r[2,6]=15 r[3,2] = 32