Структуры и алгоритмы компьютерной обработки данных (стр. 6 )

Пример выполнения упражнения тренинга на умение № 1.

Постановка задачи поиска максимального потока: найти максимальный поток из в для транспортной сети (рисунок) с помощью алгоритма Форда – Фалкерсона:

Решение:

№	Алгоритм	Конкретные действия
1.	1-я итерация	1. . 2.1 (Второй шаг, первая итерация – подобное обозначение идет далее для всех шагов алгоритма). Производим помечивание вершин и дуг, результат показан на рисунке. Вершина 6 получила метку .
2.	2-я итерация	3.1. . 4.1. ; ; . 2.2. Заново осуществляется помечивание. Вершина 6 снова получает метку (смотри рисунок).
3.	3-я итерация	3.2. . 4.2. ; ; . 2.3. Осуществляется помечивание. При этом из вершины 3 прямых допустимых дуг не выходит, однако дуга 2–3 является допустимой в обратном направлении, и вершина 2 получает метку . Вершина 6 получает метку (смотри  рисунок).
4.	4-я итерация	3.3. . 4.3. ; ; ; ; . 2.4. Осуществляется помечивание. При этом из вершины 3 допустимые дуги не выходят. Вершина 6 не получает метку (смотри рисунок). Переходим к шагу 5.
5.		5. . Минимальный разрез образуют насыщенные дуги 3–6 и 5–6. Пропускная способность минимального разреза . Условия теоремы Форда – Фалкерсона выполняются задача решена правильно. Алгоритм Форда – Фалкерсона используется при решении многих практических задач. Одна из них – задача об источниках и потребителях.

3 ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

3.1 Получить задание у преподавателя по определению максимального потока.

3.2 Составить алгоритм программы, реализующей нахождение максимального потока в сети методом Форда-Фалкерсона.

3.3 Создать программу, реализующую реализующей нахождение максимального потока в сети методом Форда-Фалкерсона..

Задание. 

Дана сеть:

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

Варианты значений пропускных способностей дуг для задания:

4 СОДЕРЖАНИЕ ОТЧЕТА ПО РАБОТЕ

4.1 Исходное задание и цель работы.

4.2 Блок-схема программы по п.3.2.

4.3 Распечатка текста программы по п.3.3.

4.4 Контрольный пример и результаты машинного расчета.

4.5 Выводы по работе.

5 КОНТРОЛЬНЫЕ ВОПРОСЫ

Дайте определение сети и потока в сети. Дайте определение разреза. Сформулируйте задачу о нахождении максимального потока. Сформулируйте теорему Форда-Фалкерсона. Опишите общий алгоритм поиска максимального потока. Опишите метод нахождения увеличивающего пути.

ЛАБОРАТОРНАЯ РАБОТА № 9

ЦИКЛЫ В ГРАФАХ

1 ЦЕЛЬ РАБОТЫ

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

2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Эйлеровы циклы

Эйлеров цикл — это такой цикл, который проходит ровно один раз по каждому ребру.

Теорема. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечет­ной степени равно нулю.

Не все графы имеют эйлеровы циклы, но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее каранда­ша. Дан граф G, удовлетворяющий условию теоремы. Требует­ся найти эйлеров цикл. Используется просмотр графа методом поиска в глубину, при этом ребра удаляются. Порядок просмот­ра (номера вершин) запоминается. При обнаружении вершины, из которой не выходят ребра, мы их удалили, ее номер записы­вается в стек, и просмотр продолжается от предыдущей верши­ны. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, четность вершин (количество выходящих ребер) при этом не изменится. Процесс продолжается до тех пор, пока есть ребра. В стеке после этого будут записаны номера вершин графа в порядке, соответствующем эйлерову циклу.

Procedure Search(v:Integer);{*Глобальные

переменные: А - матрица смежности, CV - стек;

yk - указатель стека. *}

Var j:Integer;

Begin

For j:=1 To N Do

If A[v, j]<>0 Then Begin

A[v, j] :=0;A[j, v] :=0;

Search (j)

End;

Inc (yk);Cv[yk]:=v;

End;

Пример графа и содержимое сте­ка Cv после работы процедуры Search

 

Cv: 1356725432.

Гамильтоновы циклы

Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа. Сам цикл также на­зывается гамильтоновым. Не все связные графы гамильтоновы. На рисунке дан пример графа, не имеющего гамильтонова цикла.

Дан связный неориентированный граф G. Требуется найти все гамильтоновы циклы графа, если они есть. Метод реше­ния — перебор с возвратом (backtracking). Начинаем поиск ре­шения, например, с первой вершины графа. Предположим, что уже найдены первые k компонент решения. Рассматриваем ребра, выходящие из последней вершины. Если есть такие, что идут в ранее не просмотренные вершины, то включаем эту вер­шину в решение и помечаем ее как просмотренную. Получена компонента решения. Если такой вершины нет, то воз­вращаемся к предыдущей вершине и пытаемся найти ребро из нее, выходящее в другую вершину. Решение получено при про­смотре всех вершин графа и возможности достичь из последней первой вершины. Решение (цикл) выводится, и продолжается процесс нахождения следующих циклов. Пример графа и часть дерева перебора вариантов, показывающего механизм работы данного метода, приведен на рисунке.

Procedure Gm(к:Integer); {* к - номер итерации.

Глобальные переменные: А - матрица смежности; St - массив для хранения порядка просмотра вершин

графа; Nnew - массив признаков: вершина

просмотрена или нет. *}

Var j, v:Integer;

Begin

v:=St [k-1]; {*Номер последней вершины. *}

For j:=1 To N Do

If (A[v, j]<>0) Then {*Есть ребро между

вершинами с номерами v и j. *}

If (k=N+l) And (j=l) Then <вывод цикла>

Else

If Nnew[j] Then Begin {^Вершина

не просмотрена. *}

St[k]:=j;

Nnew[j]:=False;

Gm(k+1) ;

Nnew[j]:=True;

End;

End;

Фрагмент основной программы. St[l] :=l;Nnew[l]: =False; Gm(2)