3 Порядок выполнения работы

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

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

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

Задание.

Дана сеть:

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

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

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

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

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

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

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

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

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

1. Дайте определение сети и потока в сети.

2. Дайте определение разреза.

3. Сформулируйте задачу о нахождении максимального потока.

4. Сформулируйте теорему Форда-Фалкерсона.

5. Опишите общий алгоритм поиска максимального потока.

6. Опишите метод нахождения увеличивающего пути.

Лабораторная работа № 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)

Фундаментальное множество циклов

Каркас (V,T) связного неориентированного графа G=<V,E> содержит N-1 ребро, где N — количество вершин G. Каждое ребро, не принадлежащее Т, т. е. любое ребро из Е-Т, порожда­ет в точности один цикл при добавлении его к Т. Такой цикл является элементом фундаментального множества циклов гра­фа G относительно каркаса Т. Поскольку каркас состоит из N—1 ребра, в фундаментальном множестве циклов графа G от­носительно любого каркаса имеется М-ЛЧ^циклов, где М — количество ребер в G.

Пример графа, его каркаса и множества фундаментальных циклов приведен на рисунке

Поиск в глубину является естественным подходом, исполь­зуемым для нахождения фундаментальных циклов. Строится каркас, а каждое обратное ребро порождает цикл относительно этого каркаса. Для вывода циклов необходимо хранить поря­док обхода графа при поиске в глубину (номера вершин) — мас­сив St, а для определения обратных ребер вершины следует «метить» (массив Gnum) в той очередности, в которой они про­сматриваются. Если для ребра <v,j> оказывается, что значение метки вершины с номером j меньше, чем значение метки вер­шины с номером v, то ребро обратное и найден цикл.

Начальная инициализация переменных

пит:=0;ук:=0;

For j:=2 Го N Do Gnum[j ] :=0;

Основная логика.

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

переменные: А - матрица смежности графа; St -массив для хранения номеров вершин графа в том порядке, в котором они используются при построении каркаса; ук - указатель записи в массив St; Gnum -для каждой вершины в соответствующем элементе массива фиксируется номер шага (num.) , на котором она просматривается при поиске в глубину. *}

Var j:Integer;

Begin

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

Inc (num);Gnum[v]:=num;

For j :=1 To N Do

If A[v,j]<>0 Then

If Gnum[j]=0 Then Circl[j] {*Вершина j

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

Else

If (j<>St[yk-l]) And (Gnum[j]<Gnum[v]) Then

<вывод цикла из St>(*j не предыдущая

вершина при просмотре, и она была

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

Dec (yk);

End;

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

Исследовательская работа — разработать программу нахождения всех циклов графа.