Вопросы к экзамену по курсу “Дискретная математика” (стр. 5 )

1)

Элементы первого столбца и первой строки выделены бирюзовым цветом.

Оптимизируемые значения на данном шаге - фиолетовым.

Имеем: было

Стало:

было

Стало:

Переписываем обновленные матрицы и переходим ко второму этапу.

2)

∞,1	∞,1	7,3	∞,1	3,5
∞,2	∞,2	∞,2	1,4	1,5
∞,3	∞,3	∞,3	∞,3	2,5
∞,4	∞,4	7,3	∞,4	∞,4
6,1	10,2	13,1	2,4	9,1

Оптимизации на втором шаге не происходит.

3)

∞,1	∞,1	7,3	∞,1	3,5
∞,2	∞,2	∞,2	1,4	1,5
∞,3	∞,3	∞,3	∞,3	2,5
∞,4	∞,4	7,3	∞,4	∞,4
6,1	10,2	13,1	2,4	9,1

Оптимизация матриц на данном шаге:

было

Стало:

4)

∞,1	∞,1	7,3	∞,1	3,5
∞,2	∞,2	∞,2	1,4	1,5
∞,3	∞,3	∞,3	∞,3	2,5
∞,4	∞,4	7,3	∞,4	9,3
6,1	10,2	13,1	2,4	9,1

Оптимизация матриц на данном шаге:

было

Стало:

было

Стало:

5)

∞,1	∞,1	7,3	∞,1	3,5
∞,2	∞,2	8,4	1,4	1,5
∞,3	∞,3	∞,3	∞,3	2,5
∞,4	∞,4	7,3	∞,4	9,3
6,1	10,2	9,4	2,4	9,1

Оптимизация матриц на данном шаге:

Работа алгоритма Флойда завершена. Получаеи ответ: дистанционную матрицу и маршрутную матрицу .

9,5	13,5	7,3	5,5	3,5
7,5	11,5	8,4	1,4	1,5
8,5	12,5	11,5	4,5	2,5
15,3	19,3	7,3	11,3	9,3
6,1	10,2	9,4	2,4	9,1

Решаем задачу маршрутизации: найти

Имеем -текущая вершина.

6. Теория графов. Оптимизационные задачи на графах. Алгоритм  Фор да-Фалкерсона для нахождения максимального потока в  сети.

Сеть, в которой - начальная вершина(источник),

  - конечная вершина (сток)

заданна массивом взвешенных ребер, в котором вес ребра - его пропускная способность.

			ves(r)
1	1	2	1
2	2	4	1
3	1	4	3
4	2	3	3
5	1	3	1
6	3	4	3

Найти максимальный поток в графе методом Форда-Фалкерсона.

Строим остаточный граф сети, т. е. остатка пропускных способностей дуг.

Выполняем итерации алгоритма Форда-Фалкерсона.

BFS - дерево поиска в текущем остаточном графе из вершины s.

Комментарий: В процессе BFS поиска из начальной вершины s=1 получен кратчайший путь , ведущий в сток t=4 и состоящий из одной  прямой дуги , имеющей добавочную пропускную способность 3. Поэтому вдоль найденного пути текущий поток в сети может быть наращен на величину . Получаем основную сеть следующего этапа с модифицированным(увеличенным) потоком :

Найденный путь прорисовываем в текущем остаточном графе. При прохождении по остаточному графу вдоль прямой дуги ее вес (т. е. остаток уменьшается, а вес обратной дуги, показывающей запас на прямой дуге увеличивается и наоборот.

  Строим новый остаточный граф(дуги с нулевым весом не рисуются):

Видим, что в данном случае остаточный граф содержит обратные дуги, которые определяют возможность заема потока.

3. BFS - дерево поиска из вершины s в полученном остаточном графе.