Читать курсовая по математике: "Задачи и алгоритмы дискретной математики" Страница 3

(Назад) (Cкачать работу)

1

1

3-5

2

2

4-5

3

1

. Следующий путь

6. Следующий путь

Больше аугументальных путей не осталось. Максимальный поток данной транспортной сети равен 7. 1.3 Реализация алгоритма программным методом Исходными данными в программной реализации будет матрица смежности. Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) - это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

В первой строке будет указано кол-во вершин нашего графа, например, 6. 10 5 0 0 8 0

0 0 5 3 0 4

0 0 4 5 10 0

0 0 0 4 0 9

0 0 0 0 5 6

0 0 0 0 0 0

Описание алгоритма работы программы:

. Подключаются необходимые библиотеки и объявляются переменные

. Считываются данные из текстового файла, который должен находиться в той же директории, что и исполняемый файл и называться data.txt

. Заполняется матрица пропускных способностей из файла

. Затем вызывается ф-ция max_flow (0, n-1) - это значит обход от 0, до (кол-во вершин - 1)

. В max_flow объявляется ряд переменных, обнуляется значение «maxflow» - максимальный поток.

. Создаем матрицу с нулевыми пропускными способностями

. Осуществляем обход в глубину, причем проходим зануленную матрицу

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

. Цикл выполняется n раз.

. Вывод результатов

Работа программы показана на рисунке 1.

Рисунок 1 - результат работы программы.

2. Минимальные остовные деревья: алгоритм Борувки 2.1 Формулировка задания Изучить задачу «минимального остовного дерева в графе» алгоритмом Борввки и решить ее ручным, а так же программными методами.

2.2 Изучение задачи Пусть G (V; E) связный неориентированный, тогда A - промежуточный остовный лес для графа V. На первом шаге A состоит из всех вершин G и пустого множества ребер. В начале очередной фазы алгоритма Борувки, для каждой компоненты связности промежуточного остовного леса выбирается «лидер» или «корень» - вершина, сопоставляемая каждой компоненте. Сделать это можно с помощью обхода A в глубину: вершина, с которой начинается обход очередной компоненты, и будет ее лидером.

Безопасным ребром E относительно некоторой компоненты связности K из A

Похожие работы