T₀=(X₀, U₀), …, T_n-1=(X_n-1,U_n-1).

Если вершина iXP, то ftr[i] равно собственному предку вершины в дереве TP. Если iXP, то ftr[i] указывает на вершину дерева, в которую ведет ребро веса key[i]. По определению key[i] равно расстоянию от вершины i до множества XP, иными словами

Если вершина i не смежна ни с одной из вершин XP, то key[i]=.

Дадим формальное описание алгоритма. Через Min(Q) обозначим функцию, значением которой является вершина iQ, имеющая минимальное значение метки key. Кроме того, эта функция удаляет вершину i из множества Q. Множество ребер минимального остова легко восстанавливаются по меткам ftr:

.

Алгоритм 8. Построение минимального остова. Алгоритм Прима.

Вход: Граф G, заданный списком ребер U и их весов.

Выход: массив ftr, определяющий минимальный остов.

1. for iX do key[i]:=

2. key[1]:=0; ftr[1]:=0

3. QX

4. while Q

5. do i:=Min(Q)

6. for j Q

7. do if (i,j)U & c[i,j]<key[j]

8. then ftr[j]:=i

9. key[j]:=c[i,j]

Теорема 14. Для связного графа G с n вершинами и m ребрами вычислительная сложность алгоритма Прима равна O(m log n).

Проиллюстрируем работу алгоритма 8 . На рисунке 18 изображены граф G и последовательность T _i, (i=1,…,n-1) связных ациклических подграфов, полученных после каждой итерации. Числа около ребер - их веса. Каждой вершине i приписана пара key[i] ftr[i], если вершина не принадлежит T _i, иначе указана лишь метка ftr[i] . Минимальным остовом является подграф T₄.

Рис.18. Построение минимального остова с помощью алгоритма Прима. (а) Граф G с весами ребер. (б) Последовательность подграфов T _i .

5. Кратчайшие пути в графе

Пусть G=(X,U) - орграф, на дугах которого задана весовая функция c, т.е. каждой дуге (i,j)U соответствует вес . Пусть P=<i₀,i₁,…,i_k> - путь из вершины i₀ в i_k, т.е. (i₀, i_k)-путь. Введем длину пути c(P):

Наименьшую из длин (s, t)-путей назовем расстоянием от s до t и будем обозначать как , а тот (s,t)-путь, длина которого равна, будем называть кратчайшим (s, t)-путём.

Задача о кратчайшем пути между фиксированными вершинами s и t формулируется следующим образом: в заданном орграфе G с двумя выделенными вершинами s и t найти кратчайший (s, t)-путь. Эту задачу можно рассматривать и в неориентированных графах, заменив каждое ребро (i,j) графа двумя дугами (i,j), (j,i) и считая, что веса обеих дуг равны весу ребра (i,j). Если в орграфе положить вес каждой дуги равной единице, то получим определение длины пути как числа входящих в него дуг. Кроме того, так как веса дуг могут быть отрицательными, то орграф может содержать контуры отрицательного веса. В этом случае расстояние между некоторыми парами вершин становится неопределенным, поскольку, обходя этот контур достаточное число раз, можно построить путь между этими вершинами с длиной, меньшей любого наперед заданного числа.

Для представления пути будем использовать метки вершин ftr[i], указывающие на "предшественника" вершины i в пути. Для начальной вершины пути эта метка не определена. Подграф, порожденный множеством дуг вида (ftr[i],i), iX, ftr[i]nil, будем обозначать G_ftr.

Лемма 18. Пусть G=(X,U) - орграф с весовой функцией c. Тогда верны следующие утверждения:

1) если <i₀,i₁,…,i_k> - кратчайший (i₀, i_k)-путь, то <i_q,i_q+1,…,i_r> - кратчайший (i_q,i_r)-путь, 0q<lk;

2) если P - кратчайший (s,t)-путь и (i,t) - последняя дуга этого пути, то

;

3) для любой дуги (i,j)U и вершины sX

.

Рассмотрим задачу нахождения кратчайшего пути и расстояния из вершины s в остальные вершины. Обозначим через l[i] верхнюю оценку длины кратчайшего (s,i)-пути. Начальное значение l[s]=0 и l[i]= для остальных вершин. Применим следующую операцию пересчета оценки l[i] по дуге (r,i):

Эта операция сохраняет свойство l[i] быть верхней оценкой в силу леммы. При этом значение l[i] может только уменьшиться. Одновременно с уменьшением l[i] будем менять и ftr[i] (ftr[i]:=r).

Лемма 19. Если для всех iX , то подграф G_ftr является деревом кратчайших путей из вершины s.

5.1 Случай неотрицательных весов. Алгоритм Дейкстры

Пусть веса дуг орграфа G все неотрицательные. Алгоритм Дейкстры позволяет вычислить расстояния и кратчайшие пути из фиксированной вершины s. В основе алгоритма Дейкстры лежит принцип, заключающийся в последовательном вычислении расстояний сначала до ближайшей к s вершине, затем до следующей ближайшей и т. д. Первая ближайшая к вершине s - сама вершина s, т. е. . Пусть ближайшие k вершин к вершине s определены и для всех них вычислены расстояния, т.е. определено множество S={i₁,…, i_k}, что:

1) и ;

2) .

Найдем (k+1) ближайшую к s вершину орграфа G. Для каждой i S вычислим

.

Затем выберем такую вершину rS, что

.

Дадим формальное описание алгоритма. В процессе работы алгоритма поддерживается множество S. На каждой итерации алгоритм выбирает вершину iS с наименьшим l[i], добавляет к множеству S и применяет операцию пересчета по дугам, выходящим из i. Через Min(Q) обозначим функцию, значением которой является вершина iQ, имеющая минимальное значение l[i]. Кроме того, эта функция удаляет вершину i из множества Q.

Алгоритм 9 (Дейкстры). Построение кратчайших путей из вершины.

Вход: Орграф G, заданный списками смежности; веса дуг; вершина s.

Выход: расстояния l[i] от s до всех вершин, массив ftr .

1. for iX do l[i]:=

2. l[s]:=0

3. S :=

4. Q X

5. while Q nil

6. do i := Min(Q)

7. S := S {i}

8. for j Г [i] \ S

9. do if l[j] > l[i]+c_ij

10. then l[j]:=l[i]+ c_ij

11. ftr[j]:=i

Работа алгоритма Дейкстры показана на рис. 19.

На рис.19а дан орграф с функцией весов дуг. На рис. 19б изображено дерево кратчайших путей из вершины 1; около вершин указаны значения l[i] - длины кратчайшего пути из s в i. На рис.19в показаны состояния l[i] /ftr[i] для каждой вершины i после 1-ой, 2-ой и 4-ой итераций, т.к. состояния меток не изменялись после итерации 3 и 5. Вершины из S изображены жирными линиями.

Теорема 15. Алгоритм Дейкстры имеет сложность О(n²).



Рис.19. Алгоритм Дейкстры. (а) Орграф G с весами дуг. (б) Дерево кратчайших путей. (в) Состояния после 1-ой, 2-ой и 4-й итераций.

5.2 Общий случай. Алгоритм Форда-Беллмана

граф алгоритм вершина коммуникационный

Алгоритм Форда-Беллмана решает задачу о кратчайших путях из одной вершины в случае, когда веса дуг могут быть отрицательными. Если в орграфе имеется контур отрицательного веса, то алгоритм возвращает значение False. В противном случае он возвращает True, построив все кратчайшие пути из вершины s и определив их длину. Алгоритм также использует операцию пересчета по дуге.

Алгоритм 10 (Форда-Беллмана). Построение кратчайших путей из вершины.

Вход: Орграф G, заданный списком U дуг и их весов; выделенная вершина s.

Выход: расстояния l[i] от s до всех вершин, массив ftr .

1. for iX do l[i]:=

2. l[s]:=0

3. for k:=1 to |X|-1

4. do for (i,j) U

5. do if l[j] > l[i]+c(i,j)

6. then l[j]:=l[i]+ c(i,j)

7. ftr[j]:=i

8. for (i,j) U

9. do if l[i]>l[j]+c(i,j)

10. then return False

11. return True

Теорема 16. Алгоритм Форда-Беллмана имеет сложность О(nm).

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

Пусть G=(X,U) связный граф. Эйлеровой цепью называется цепь графа, содержащая все ребра. Замкнутая эйлерова цепь называется эйлеровым циклом. Граф называется эйлеровым, если он содержит эйлеров цикл. Задача состоит в нахождении эйлеровой цепи или цикла.

Теорема Эйлера. Для связного графа G следующие условия эквивалентны:

1) G - эйлеров граф;

2) степени всех вершин графа четны;

3) множество ребер графа можно разбить на циклы.

Следствие 1. Если связный граф содержит 2k вершин нечетной степени, то множество ребер можно разбить на k цепей, каждая из которых соединяет вершины нечетной степени.

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

Этот раздел посвящен построению и анализу алгоритма, позволяющему в связном графе G с четными степенями вершин построить эйлеров цикл. Рассмотрим процесс нумерации ребер, называемый алгоритмом Флери, придерживаясь следующих правил:

1) начиная с произвольной вершины s, присваиваем некоторому ребру (s,q) номер 1 и переходим в вершину q;

2) пусть помечено k ребер и мы находимся в вершине i; тогда выбираем непомеченное ребро (i,j), присваиваем ему номер k+1 и переходим в вершину j; при этом если вершине i инцидентно несколько непомеченных ребер, то в первую очередь выбираем ребро, не являющееся мостом в подграфе, порожденном непомеченными ребрами.

Процесс заканчивается, когда все ребра будут перенумерованы.

Дадим формальное описание алгоритма. В алгоритме используются два стека SW и SR, элементами обоих стеков являются вершины графа G. Кроме того, введен массив List, элементы которого - списки вершин.

Алгоритм 11. Построение эйлерова цикла.

Вход: связный граф G без вершин нечетной степени, заданный списками смежности; начальная вершина s.

Выход: эйлерова цепь, представленная последовательностью вершин в SR.

1. SW:=nil; SR:=nil

2. SW s

3. for iX do list[i]:=Г[i]

4. while SWnil

5. do i:=top(SW) ; выбор первой вершины в стеке с удалением ее из стека;

6. if list[i]

7. then j:=top(list[i]) ; выбор первой вершины в списке и

удаление ее из списка;

8. list[j]:=list[j]\{i} ; удаление вершины i из списка;

9. SW i

10. SW j

11. else SR i

Принцип работы этого алгоритма заключается в следующем. Начиная с некоторой вершины s, строим цепь, удаляя ребра (строки 7 и 8) и запоминая вершины в стеке SW (строка 9 и 10), до тех пор пока множество смежности (list) очередной вершины не окажется пустым, т.е. выделена в графе некоторая замкнутую цепь. Тогда начинает работу оператор строки 12, который помещает вершины в SR. В результате либо будет обнаружена вершина с непустым списком смежности, либо стек SW окажется пустым.

Если исходный граф содержит 2k вершин нечетной степени, то этот алгоритм можно применить для разбиения множества ребер на k цепей. В этом случае необходимо добавить k ребер между вершинами нечетной степени, т.е.

превратить граф в эйлеров, подать его на вход алгоритма, а затем в полученном эйлеровом цикле удалить k дополнительно введенных ребер.

На рис. 20 изображен эйлеров граф и эйлеров цикл, построенный алгоритмом 9 (предполагается, что все списки вершин упорядочены по возрастанию номеров).

Рис.20. Построение эйлерова цикла графа G . Стек SR на выходе алгоритма.

Сложность алгоритма 9 равна O(m), где m - число ребер графа. Действительно, на каждой итерации цикла либо обнаруживается непомеченное ребро, что приводит к добавлению в стек SW вершины, инцидентной этому ребру, либо добавляется ребро к строящемуся эйлеровому циклу. Отсюда следует, что число повторений цикла равно O(m).

7. Цикломатическое число графа. Фундаментальные циклы и разрезы графа

Данный раздел посвящен установлению связи между структурами циклов и разрезов графа.

Рассмотрим связный граф G=(X,U). Любой цикл Z графа можно рассматривать как подмножество ребер множества U. Пусть M множество подмножеств ребер графа G. Рассмотрим операцию сложения по модулю 2 (симметрическая разность) над элементами из M:

,

а также операцию умножения на скаляр 0 или 1:

.

Так как аксиомы векторного пространства выполняются, то множеством с операцией образует векторное пространство над двоичной арифметикой. Множествоназывается зависимым или линейной комбинацией множеств {U₁,…,U_k}, если

.

Множество циклов называется независимым, если ни один из циклов не является линейной комбинацией остальных.

Максимальное (по числу элементов) независимое множество циклов называется фундаментальной системой циклов графа. Циклы такой системы называются фундаментальными, их число - цикломатическим числом (G) графа G.

Теорема 17. Если G =(X,U) граф с n вершинами, m ребрами и p компонентами связности, то

(G)=m-n+p.

Для построения фундаментальной системы циклов используем поиск в глубину. Поиск в глубину строит дерево ПВГ и разбивает множество U ребер графа G на множество UT древесных и множество UB обратных ребер. Число обратных ребер равно цикломатическому числу (G). Каждое обратное ребро uUB при добавлении к дереву ПВГ порождает простой цикл Z_u. Таким образом, множество {Z_u | uUB} является фундаментальной системой циклов.

Реализация такого подхода для связного графа представлена в алгоритме 12, где использованы ранее описанные массивы num и ftr. Для вершины i число num[i] определяет номер глубина, а ftr[i] - номер вершины (собственного предка) в дереве ПВГ. Для того, чтобы накапливать информацию о фундаментальных циклах, будем использовать массив стеков masQ[m-n+1], где m-n+1 - цикломатическое число связного графа. В стеке masQ[i] будем хранить последовательность вершин, определяющую i-й по порядку фундаментальный цикл. Граф G=(X,U) задается списками смежности Г[i], iX.

Алгоритм 12. Построение фундаментальной системы циклов связного графа.

Вход: Связный граф G, представленный списками смежности Г.

Выход: массив masQ, массивы num, ftr, число циклов nZ.

8. n:=0; m:=0

9. for iX

10. do num[i]:=0

11. ftr[i]:=0

12. n:=n+1

13. m:=m+|Г[i]| // |Г[i]| - число элементов списка Г[i]

14. m:=m/2

15. for i:=1 to m-n+1

16. do masQ[i]:=nil

17. k:=0 // счетчик глубины

18. nZ:=0 // счетчик фундаментальных циклов

19. ЦИКЛ(1)

ЦИКЛ(i)

8. k:=k+1; num[i]:=k

9. for j Г[i]

10. do if num[j]=0

11. then ftr[j]:=i

12. ЦИКЛ(j)

13. else if ftr[i]# j

14. then nZ:=nZ+1 // обнаружено обратное ребро

15. SAVE(i,j,nZ)

SAVE(i,j,nZ)

1. z:=i

2. while z#j

3. do masQ[nZ] z

4. z:=ftr[z]

5. masQ[nZ] j; masQ[nZ] i

Алгоритм 12 имеет сложность O(nm).

На рис. 21 показан граф G, дерево ПВК с корнем в вершине 1 и с метками num[i]/ftr[i] около каждой вершины i, а также фундаментальные циклы и состояние массива masQ по окончанию алгоритма. Списки смежности, задающие граф G, имеют вид: Г[1]={2,3,4,5}; Г[2]={1,3,4,5}; Г[3]={1,2,4}; Г[4]={1,2,3}; Г[5]={1,2}. В голове каждого из стеков masQ[i], содержащих вершины циклов Z_i, расположены две вершины, образующие обратное ребро.

Множество ребер графа G называется разрезом, если удаление их делает граф несвязным. Простым разрезом называется разрез, никакое собственное подмножество которого разрезом не является. Любой разрез S графа можно рассматривать как подмножество ребер множества U.

Множество разрезов называется независимым, если ни один из разрезов не является линейной комбинацией остальных.

Максимальное (по числу элементов) независимое множество разрезов называется фундаментальной системой разрезов графа. Разрезы такой системы называются фундаментальными, их число - рангом ^*(G) графа G.

Теорема 18. Если G =(X,U) граф с n вершинами, m ребрами и p компонентами связности, то ^*(G)=n-p.

Для построения фундаментальной системы разрезов используем поиск в глубину, дерево ПВГ и фундаментальную систему циклов {Z_u | uUB}. Число ребер дерева ПВГ равно рангу ^*(G) графа. Пусть u любое ребро из UT. Тогда выделим все фундаментальные циклы, которые содержат это ребро: . Множество ребер является разрезом. Таким образом, множество {S_u | uUT} является фундаментальной системой разрезов.

Реализация такого подхода для связного графа представлена в алгоритме 13, где использованы стеки masQ, массивы num и ftr, ранее построенные в алгоритме 12. Для того, чтобы накапливать информацию о фундаментальных циклах, будем использовать массив стеков masQS[n-1], где n-1 - ранг связного графа. В стеке masQS[i] будем хранить i-й по порядку фундаментальный разрез в виде последовательности ребер.



Рис.21. Построение фундаментальных циклов графа: а - граф G=(X,U); б - дерево ПВГ; в - фундаментальные циклы; г - массив стеков masQ.

Алгоритм 13. Построение фундаментальной системы разрезов связного графа.

Вход: Связный граф G, представленный списками смежности Г, массив фундаментальных разрезов masQ, массив ftr, число циклов nZ.

Выход: массив masQS, число разрезов nS.

1. n:=m:=0

2. for iX

3. do n:=n+1

4. for i:=1 to n-1

5. do masQS[i]:=nil

6. nS:=0 // счетчик фундаментальных разрезов

7. for iX

8. do if ftr[i]#0

9. then nS:=nS+1

10. РАЗРЕЗ(i,ftr[i],nS)

РАЗРЕЗ (i,j,nS)

1. masQS[nS](i,j) // ребро (i,j) помещается в стек первым

2. for k:=1 to nZ

3. do if PROV(i,j,k) // проверка принадлежности ребра (i,j) циклу

// masQ[k]

4. rmasQ[k] // считать из стека обратное ребро (r,s), связан-

5. smasQ[k] // ное с циклом Z_k

6. masQS[nS](r,s)

PROV(i,j,k)

1. Q masQ[k]

2. niQ;

3. while Q#nil

4. do njQ

5. if (ni=i and nj=j) or (ni=j and nj=i)

6. then Return TRUE

7. ni:=nj

8. Return FALSE

Фундаментальная система разрезов графа G, изображенного на рис.21 вместе с фундаментальными циклами Z₁,Z₂,Z₃, Z₄, состоит из 4-х разрезов:

S₁=<(2,1), (3,1), (4,1), (5,1)>; S₂= <(3,2), (3,1), (4,1), (4,2)>;

S₃=<(4,3), (4,1), (4,2)>; S₄=<(5,2), (5,1)>,

ребра которых располагаются в стеках masQS. На рис.22 показаны разрезы S₂ и S₄ ; ребра разрезов изображены пунктирной линией.

Рис. 22. Фундаментальные разрезы графа G: а - разрез S₂ ; б - разрез S₄.

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

Рекомендуемая литература

1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск: НИЦ "Регулярная и хаотическая динамика",2001.

2. Кормен Т.,Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.-М.-МЦНМО,1999.

3. Емеличев В.А.,Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.:Наука,1990.

4. Новиков Ф.А. Дискретная математика для программистов.-СПб.: Питер,2001.

Размещено на Allbest.ru