Категория: Другое

Модулярная арифметика, теория графов

Вариант - 6

Найти максимальный поток и минимальный разрез между вершинами s и t в транспортной сети с ориентированным графом G=(V, E) где

V={s, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, t}

E={(s, 1), (s, 2), (s, 3), (1, 2), (1, 4), (1, 5), (2, 6), (2, 9), (3, 2), (3, 6), (3, 7), (4, 5), (4, 8), (4, 11), (5, 8), (5, 10), (6, 1), (7, 10), (7, t), (8, t), (8, 9), (8, 12), (9, 6), (9, 10), (9, t), (10, t), (11, 1), (11, 12), (12, 13), (13, 8), (13, t),}.

Вес w_ij дуги (i, j) равен N(i²+j²)+i²+j²+i+j по модулю 10 (остаток от деления w_ij на 10). N есть номер варианта.

Решение выполнено с подробными пояснениями. Все формулы набраны в Ворд.