Алгоритмы на графах. Поиск в графе. Деревья. Связность
Дерево как произвольный связный неориентированный граф без циклов. Граф - конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин. Выбор структуры данных для представления графа. Поиск стягивающего дерева различными методами.
Рубрика | Программирование, компьютеры и кибернетика |
Вид | курсовая работа |
Язык | русский |
Дата добавления | 11.03.2010 |
Размер файла | 148,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство образования Республики Беларусь
Учреждение образования
«Гомельский государственный университет им. Ф. Скорины»
Курсовая работа
Алгоритмы на графах. Поиск в графе. Деревья. Связность
Исполнитель:
Студентка группы М-33
Лавриненко А.Ю.
Гомель 2007
Содержание
Введение
1. Поиск в графе
1.1 Поиск в глубину
1.2 Поиск в ширину
2. Деревья
2.1 Основные понятия. Стягивающие деревья
2.2 Порождение всех каркасов графа
2.3 Каркас минимального веса. Метод Краскала
2.4 Каркас минимального веса. Метод Прима
3. Связность
3.1 Достижимость
3.2 Определение связности
3.3 Двусвязность
Заключение
Литература
Введение
Определим граф как конечное множество вершин V и набор E неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и E будем обозначать буквами N и M. Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину, также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины u и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться.
Способы описания. Выбор соответствующей структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер.
Матрица смежности - это двумерный массив размерности N*N.
A[i,j]=
Для хранения перечня ребер необходим двумерный массив R
размерности M*2. Строка массива описывает ребро.
1. Поиск в графе
Множество алгоритмов на графах требует просмотра вершин графа. Рассмотрим их.
1.1 Поиск в глубину
Идея метода. Поиск начинается с некоторой фиксированной вершины v. Рассматривается вершина u, смежная с v. Она выбирается. Процесс повторяется с вершиной u. Если на очередном шаге мы работаем с вершиной q и нет вершин, смежных с q и не рассмотренных ранее (новых), то возвращаемся из вершины q к вершине, которая была до нее. В том случае, когда это вершина v, процесс просмотра закончен. Очевидно, что для фиксации признака, просмотрена вершина графа или нет, требуется структура данных типа:
Nnew : array[1..N] of boolean.
Пример. Пусть граф описан матрицей смежности A. Поиск начинается с первой вершины. На левом рисунке приведен исходный граф, а на правом рисунке у вершин в скобках указана та очередность, в которой вершины графа просматривались в процессе поиска в глубину.
Логика.
procedure Pg(v:integer);{Массивы Nnew и A глобальные}
var j:integer;
begin
Nnew[v]:=false; write(v:3);
for j:=1 to N do if (A[v,j]<>0) and Nnew[j] then Pg(j);
end;
Фрагмент основной логики.
...
FillChar(Nnew,SizeOf(Nnew),true);
for i:=1 to N do if Nnew[i] then Pg(i);
...
В силу важности данного алгоритма рассмотрим его нерекурсивную реализацию. Глобальные структуры данных прежние: A - матрица смежностей; Nnew - массив признаков. Номера просмотренных вершин графа запоминаются в стеке St, указатель стека - переменная yk.
procedure PG1(v:integer);
var St:array[1..N] of integer;yk:integer;t,j:integer;pp:boolean;
begin
FillChar(St,SizeOf(St),0); yk:=0;
Inc(yk);St[yk]:=v;Nnew[v]:=false;
while yk<>0 do begin {пока стек не пуст}
t:=St[yk]; {выбор “самой верхней“ вершины из стека}
j:=0;pp:=false;
repeat
if (A[t,j+1] <>0) and Nnew[j+1] then pp:=true
else Inc(j);
until pp or (j>=N); {найдена новая вершина или все вершины, связанные с данной вершиной, просмотрены}
if pp then begin
Inc(yk);St[yk]:=j+1;Nnew[j+1]:=false;{добавляем в стек}
end
else Dec(yk); {“убираем” вершину из стека}
end;
end
1.2 Поиск в ширину
Идея метода. Суть (в сжатой формулировке) заключается в том, чтобы рассмотреть все вершины, связанные с текущей. Принцип выбора следующей вершины - выбирается та, которая была раньше рассмотрена. Для реализации данного принципа необходима структура данных “очередь”.
Пример. Исходный граф на левом рисунке. На правом рисунке рядом с вершинами в скобках указана очередность просмотра вершин графа.
Приведем процедуру реализации данного метода обхода вершин графа.
Логика просмотра вершин.
procedure PW(v:integer);
var Og:array[1..N] of 0..N; {очередь}
yk1,yk2:integer;{указатели очереди, yk1 - запись; yk2 - чтение}
j:integer;
begin
FillChar(Og,SizeOf(Og),0);yk1:=0;yk2:=0;{начальная инициализация}
Inc(yk1);Og[yk1]:=v;Nnew[v]:=false;{в очередь - вершину v}
while yk2<yk1 do begin {пока очередь не пуста}
Inc(yk2);v:=Og[yk2];write(v:3);{“берем” элемент из очереди}
for j:=1 to N do {просмотр всех вершин, связанных с вершиной v}
if (A[v,j]<>0) and Nnew[j] then begin{если вершина ранее не просмотрена}
Inc(yk1);Og[yk1]:=j;Nnew[j]:=false;{заносим ее в очередь}
end;
end;
end;
2 Деревья
2.1Основные понятия. Стягивающие деревья
Деревом называют произвольный связный неориентированный граф без циклов. Его можно определить и по-другому: связный граф, содержащий N вершин и N-1 ребер, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью. Для произвольного связного неориентированного графа G=<V,E> каждое дерево <V,T>, где TE называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами.
Примечание. Понятие цикла будет дано позже. В данной теме ограничимся его интуитивным пониманием.
Число различных каркасов полного связного неориентированного помеченного графа с N вершинами было найдено впервые Кэли и равно N(N-2).
Пример. Граф и его каркасы.
Поиск стягивающего дерева (каркаса). Рассмотрим два алгоритма нахождения каркасов (одного), основанных на методах просмотра графа поиском в глубину и в ширину. Граф описывается матрицей смежности A, массив Nnew (array[1..N] of boolean) служит для хранения признаков. Значение Nnew[i], равное true, говорит о том, что вершина с номером i еще не просмотрена. Для хранения ребер, образующих каркас, будем использовать структуру данных Tree (array[1..2,1..N] of integer).
Известно, что как при поиске в глубину, так и при поиске в ширину просматриваются все вершины связного графа. Использование массива Nnew обеспечивает “подключение” очередного ребра к каркасу без образования циклов. Действительно, цикл образуется, если мы соединяем две просмотренные вершины. Но в нашем случае “подключается” ребро, соединяющее просмотренную вершину с непросмотренной. И наконец, по самой логике методов поиска в глубину и в ширину мы строим связный граф.
Построение каркаса для связного графа методом поиска в глубину.
procedure Tree_Depth(v:integer); {рекурсивная процедура}
{A, Nnew, Tree, yk - глобальные структуры данных}
var i:integer;
begin
Nnew[v]:=false;
for i:=1 to N do if (A[v,i]<>0) and Nnew[i] then begin
{добавляем ветвь в каркас}
Inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
Tree_Depth(i);
end;
end;
{фрагмент основной логики}
begin
FillChar(Nnew,SizeOf(Nnew),true);yk:=0;
Tree_Depth(1); {строим от первой вершины}
<вывод каркаса>;
end.
Построение каркаса для связного графа методом поиска в ширину.
procedure Tree_Width(v:integer);
{A, Tree, yk - глобальные структуры данных}
var Nnew:array[1..N] of boolean;
Turn:array[1..N] of integer;yr,yw,i:integer;
begin
FillChar(Nnew,SizeOf(Nnew),true);
FillChar(Turn,SizeOf(Turn),0);yr:=0;yw:=0;
Inc(yw); Turn[yw]:=v;Nnew[v]:=false;
while yw<>yr do begin
Inc(yr);v:=Turn[yr];
for i:=1 to N do if (A[v,i]<>0) and Nnew[i] then begin
Inc(yw);Turn[yw]:=i;Nnew[i]:=false;
Inc(yk);Tree[1,yk]:=v;Tree[2,yk]:=i;
end;
end;
end;
Пример. Граф и его каркасы, построенные методами поиска в глубину и в ширину. В круглых скобках указана очередность просмотра вершин графа при соответствующем поиске.
2.2 Порождение всех каркасов графа
Дано. Связный неориентированный граф G=<V,E>. Найти. Все каркасы графа. Каркасы не запоминаются. Их необходимо перечислить. Для порождения очередного каркаса ранее построенные не привлекаются, используется только последний. Множество всех каркасов графа G делится на два класса: содержащие выделенное ребро <v,u> и не содержащие. Каркасы последовательно строятся в графах G<v,u> и G-<v,u>. Каждый из графов G<v,u> и G-<v,u> меньше, чем G. Последовательное применение этого шага уменьшает графы до тех пор, пока не будет построен очередной каркас, либо графы станут несвязными и не имеющими каркасов.
Для реализации идеи построения каркасов графа G используются следующие структуры данных:
очередь - Turn (array[1..N] of integer) с нижним (down) и верхним (up) указателями;
массив признаков Nnew (см. предыдущее занятие);
список ребер, образующих каркас - Tree (см. предыдущее занятие);
число ребер в строящемся каркасе - numb.
Начальное значение переменных:
.....
FillChar(Nnew,SizeOf(Nnew),true);
FillChar(Tree,SizeOf(Tree),0);
Nnew[1]:=false;
{*в очередь заносим первую вершину*}
Turn[1]:=1; down:=1;up:=2; numb:=0;
......
Procedure Solve(v,q:integer);
{*v - номер вершины, из которой выходит ребро *}
{*q - номер вершины, начиная с которой следует искать очередное
ребро каркаса *}
var j:integer;
begin
if down>=up then exit;
j:=q;
while (j<=N) and (numb<N-1) do begin {*просмотр ребер, выходящих из вершины с номером v *}
if (A[v,j]<>0) and Nnew[j] then begin {*есть ребро, и вершины с номером j еще нет в каркасе *}
{*включаем ребро в каркас*}
Nnew[j]:=false;
inc(numb);Tree[1,numb]:=v;Tree[2,numb]:=j;
{*включаем вершину с номером j в очередь*}
Turn[up]:=j;inc(up);
Solve(v,j+1); {*продолжаем построение каркаса*}
{*исключаем ребро из каркаса*}
dec(up);Nnew[j]:=true; dec(numb);
end;
inc(j);
end;
if numb=N-1 then begin <вывод каркаса>; exit end;
{*все ребра, выходящие из вершины с номером v, просмотрены*}
{* переходим к следующей вершине из очереди и так до тех пор,
пока не будет построен каркас *}
if j=N+1 then begin inc(down);
Solve(Turn[down],1);
dec(down);
end;
end; {*Solve*}
2.3 Каркас минимального веса. Метод Краскала
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается перечнем ребер с указанием их веса. Массив P (array[1..3,1..N*(N-1) div 2] of integer). Результат. Каркас с минимальным суммарным весом Q=<V,T>, где TE.
Пример. Граф и процесс построения каркаса по методу Краскала.
Шаг 1. Начать с вполне несвязного графа G, содержащего N вершин.
Шаг 2. Упорядочить ребра графа G в порядке неубывания их весов.
Шаг 3. Начав с первого ребра в этом перечне, добавлять ребра в графе Q, соблюдая условие: добавление не должно приводить к появлению цикла в Q.
Шаг 4. Повторять шаг 3 до тех пор, пока число ребер в Q не станет равным N-1. Получившееся дерево является каркасом минимального веса.
Какие структуры данных требуются для реализации шага 3? Введем массив меток вершин графа (Mark:array[1..N] of integer). Начальные значения элементов массива равны номерам соответствующих вершин (Mark[i]=i для i от 1 до N). Ребро выбирается в каркас в том случае, если вершины, соединяемые им, имеют разные значения меток. В этом случае циклы не образуются. Для примера, приведенного выше, процесс изменения Mark показан в таблице.
Номер итерации |
Ребро |
Значения элементов Mark |
|
начальное значение |
- |
[1,2,3,4,5] |
|
1 |
<1,4> |
[1,2,3,1,5] |
|
2 |
<4,5> |
[1,2,3,1,1] |
|
3 |
<2,3> |
[1,2,2,1,1] |
|
4 |
<2,5> |
[1,1,1,1,1] |
И логика этого фрагмента.
procedure Chang_Mark(l,m:integer);
{массив Mark глобальный}
var i,t:integer;
begin
if m<l then begin t:=l;l:=m;m:=t end;
for i:=1 to N do if Mark[i]=m then Mark[i]:=l;
end;
Фрагмент основной части логики.
program Tree1;
const N=..;
var P:array[1..3,1..N*(N-1) div 2] of integer;
Mark:array[1..N] of integer;k,i,t:integer;
M:integer;{количество ребер графа}
begin
<ввод описания графа - массив P>;
<сортировка массива P по значениям весов ребер>;
for i:=1 to N do Mark[i]:=i;
k:=0;t:=M;
while k<N-1 do begin i:=1;
while (i<=t) and (Mark[P[1,i]]=Mark[P[2,i]]) and (P[1,i]<>0) do Inc(i);
Inc(k);
<вывод или запоминание ребра каркаса>;
Change_Mark(Mark[P[1,i]],Mark[P[2,i]]);
end;
end;
2.4 Каркас минимального веса. Метод Прима
Дано. Связный неориентированный граф G=<V,E>. Ребра имеют вес. Граф описывается матрицей смежности A (array[1..N,1..N] of integer). Элемент матрицы, не равный нулю, определяет вес ребра. Результат. Каркас с минимальным суммарным весом Q=<V,T>, где TE.
Отличие от метода Краскала заключается в том, что на каждом шаге строится дерево, а не ациклический граф. Для реализации метода необходимы две величины множественного типа SM и SP (set of 1..N). Первоначально значением SM являются все вершины графа, а SP пусто. Если ребро <i,j> включается в T, то номера вершин i и j исключаются из SM и добавляются в SP.
Пример. Граф и его каркас.
Логика построения каркаса
procedure Tree2;
{A - глобальная структура данных}
var SM,SP:set of 1..N; min,i,j,l,k,t:integer;
begin
min:=maxint; SM:=[1..N];SP:=[];{включаем первое ребро в каркас}
for i:=1 to N-1 do for j:=i+1 to N do
if (A[i,j]<min) and (A[i,j]<>0) then begin min:=A[i,j];l:=i;t:=j; end;
SP:=[l,t];SM:=SM-[l,t]; <выводим или запоминаем ребро <l,t>>;
{основной цикл}
while SM<>[] do begin
min:=maxint;l:=0;t:=0;
for i:=1 to N do if Not(i in SP) then for j:=1 to N do
if (j in SP) and (A[i,j]<min) and (A[i,j]<>0) then
begin min:=A[j,k]; l:=i;t:=j;end;
SP:=SP+[l];SM:=SM-[l]; <выводим или запоминаем ребро <l,t>>;
end;
end;
3. Связность
3.1 Достижимость
Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Простой путь - это путь, в котором каждая дуга используется не более одного раза. Элементарный путь - это путь, в котором каждая вершина используется не более одного раза. Если существует путь из вершины графа v в вершину u, то говорят, что u достижима из v. Матрицу достижимостей R определим следующим образом:
R[v,u]=
Множество R(v) - это множество таких вершин графа G, каждая из которых может быть достигнута из вершины v. Обозначим через Г(v) множество таких вершин графа G, которые достижимы из v с использованием путей длины 1. Г2(v) - это Г(Г(v)), то есть с использованием путей длины 2 и так далее. В этом случае:
R(v)={v}Г(v)Г2(v)...Гp(v).
При этом p - некоторое конечное значение, возможно, достаточно большое.
Пример(для рисунка).
R(1)={1}{2,5}{1,6}{2,5,4}{1,6,7}={1,2,4,5,6,7}
Выполняя эти действия для каждой вершины графа, мы получаем матрицу достижимостей R.
procedure Reach; {формирование матрицы R, глобальной переменной}
{исходные данные - матрица смежности A, глобальная переменная}
var S,T:set of 1..N;i,j,l:integer;
begin
FillChar(R,SizeOf(R),0);
for i:=1 to N do begin {достижимость из вершины с номером i}
T:=[i];
repeat
S:=T;
for l:=1 to N do if l in S then{по строкам матрицы A, принадлежащим множеству S}
for j:=1 to N do if A[l,j]=1 then T:=T+[j];
until S=T;{если T не изменилось, то найдены все вершины графа, достижимые из вершины с номером i}
for j:=1 to N do if j in T then R[i,j]:=1;
end;
end;
Матрицу контрдостижимостей Q определим следующим образом:
Q[v,u]=
Множеством Q(v) графа G является множество таких вершин, что из любой его вершины можно достигнуть вершину v. Из определения следует, что столбец v матрицы Q совпадает со строкой v матрицы R, то есть Q=Rt, где Rt - матрица, транспонированная к матрице достижимостей R.
Для примера на рисунке матрицы A, R и Q имеют вид:
0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0
1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0
0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 0
A= 0 0 0 0 0 0 1 R= 0 0 0 1 0 1 1 Q= 1 1 1 1 1 1 1
1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 1 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1
Дополнения.
1. Граф называется транзитивным, если из существования дуг (v,u) и (u,t) следует существование дуги (v,t). Транзитивным замыканием графа G=(V,E) является граф Gz=(V,EE'), где E' - минимально возможное множество дуг, необходимых для того, чтобы граф Gz был транзитивным. Разработать программу для нахождения транзитивного замыкания произвольного графа G.
2. R(v) - множество вершин, достижимых из v, а Q(u) - множество вершин, из которых можно достигнуть u. Определить, что представляет из себя множество R(v)Q(u). Разработать программу нахождения этого типа множеств.
3.2 Определение связности
Определения. Неориентированный граф G связен, если существует хотя бы один путь в G между каждой парой вершин i и j. Ориентированный граф G связен, если неориентированный граф, получающийся из G путем удаления ориентации ребер, является связным. Ориентированный граф сильно связен, если для каждой пары вершин i и j существует по крайней мере один ориентированный путь из i в j и по крайней мере один из j в i. Максимальный связный подграф графа G называется связной компонентой графа G. Максимальный сильно связный подграф называется сильно связной компонентой.
Рассмотрим алгоритм нахождения сильных компонент графа. Идея достаточна проста. Для вышеприведенного примера значение
R(1)={1}{2,5}{6}{4}{7}={1,2,4,5,6,7}, а Q(1)={1} {2,5} {3}.
Пересечение этих множеств дает множество C(1)={1,2,5} вершин графа G, образующих сильную компоненту, которой принадлежит вершина графа с номером 1. Продолжим рассмотрение:
R(3)={1,2,3,4,5,6,7}, Q(3)={3} и C(3)={3}; R(4)={4}{7}{6}={4,6,7}
и Q(4)={4}{6}{7}={4,6,7} и С(4)={4,6,7}.
Итак, мы нашли сильные компоненты графа G. Граф G*=(V*,E*) определим так: каждая его вершина представляет множество вершин некоторой сильной компоненты графа G, дуга (i*, j*) cуществует в G* тогда и только тогда, когда в G существует дуга (i,j), такая, что i принадлежит компоненте, соответствующей вершине i*, а j - компоненте, соответствующей вершине j*. Граф G* называется конденсацией графа G.
Дополнения.
1. Доказать, что в конденсации графа не содержится циклов.
2. Доказать, что в ориентированном графе каждая вершина i может принадлежать только одной сильной компоненте.
3. В графе есть множество вершин P, из которых достижима любая вершина графа и которое является минимальным в том смысле, что не существует подмножества в P, обладающего таким свойством достижимости. Это множество вершин называется базой графа. Показать, что в P нет двух вершин, которые принадлежат одной и той же сильной компоненте графа G.
Показать, что любые две базы графа G имеют одно и то же число вершин. Разработать программу нахождения базы графа. Схема решения. База P* конденсации G* графа G состоит из таких вершин графа G*, в которые не заходят ребра. Следовательно, базы графа G можно строить так: из каждой сильной компоненты графа G, соответствующей вершине базы P* конденсации G*, надо взять по одной вершине - это и будет базой графа G.
3.3 Двусвязность
Иногда недостаточно знать, что граф связен. Может возникнуть вопрос, насколько “сильно связен” связный граф. Например, в графе может существовать вершина, удаление которой вместе с инцидентными ей ребрами разъединяет оставшиеся вершины. Такая вершина называется точкой сочленения, или разделяющей вершиной. Граф, содержащий точку сочленения, называется разделимым. Граф без точек сочленения называется двусвязным или неразделимым. Максимальный двусвязный подграф графа называется двусвязной компонентой или блоком.
Пример. Разделимый граф и его двусвязные компоненты. Точки сочленения вершины с номерами 4, 5 и 7.
Точку сочленения можно определить иначе. Вершина t является точкой сочленения, если существуют вершины u и v, отличные от t, такие, что каждый путь из u в v (предполагаем, что существует по крайней мере один) проходит через вершину с номером t.
Наша задача - найти точки сочленения и двусвязные компоненты графа. Основная идея. Есть двусвязные компоненты G1, G2, G3, G4 и G5 и точки сочленения 1, 2, 3. Осуществляем поиск в глубину из вершины t, принадлежащей G1. Мы можем перейти из G1 в G2, проходя через вершину 1. Но по свойству поиска в глубину все ребра G2 должны быть пройдены до того, как мы вернемся в 1. Поэтому G2 состоит в точности из ребер, которые проходятся между заходами в вершину 1. Для других чуть сложнее. Из G1 попадаем в G3, затем в G4 и G5. Предысторию процесса прохождения ребер будем хранить в стеке. Тогда при возвращении в G4 из G5 через вершину 3 все ребра G5 будут на верху стека. После их удаления, то есть вывода двусвязной компоненты из стека, на верху стека будут ребра G4, и в момент прохождения вершины 2 мы можем их опять вывести. Таким образом, если распознать точки сочленения, то, применяя поиск в глубину и храня ребра в стеке в той очередности, в какой они проходятся, можно определить двусвязные компоненты. Ребра, находящиеся на верху стека в момент обратного прохода через точку сочленения, образуют двусвязную компоненту.
Итак, проблема с точками сочленения. Рассмотрим граф. В процессе просмотра в глубину все ребра разбиваются на те, которые составляют дерево (каркас), и множество обратных ребер. Обратные ребра выделены на рисунке более жирными линиями.
Что нам это дает? Пусть очередность просмотра вершин в процессе поиска в глубину фиксируется метками в массиве Num. Для нашего примера Num - (1,2,3,4,5,6,7,9,8). Если мы рассматриваем обратное ребро (v,u), и v не предок u, то информацию о том, что Num[v] больше Num[u], можно использовать для пометки вершин v и u как вершин, принадлежащих одной компоненте двусвязности. Массив Num использовать для этих целей нельзя, поэтому введем другой массив Lowpg и постараемся пометить вершины графа, принадлежащие одной компоненте двусвязности одним значением метки в этом массиве. Первоначальное значение метки совпадает со значением соответствующего элемента массива Num. При нахождении обратного ребра (v,u) естественной выглядит операция: Lowpg[v]:=Min(Lowpg[v],Num[u]) - изменения значения метки вершины v, так как вершины v и u из одной компоненты двусвязности. К этой логике необходимо добавить смену значения метки у вершины v ребра (v,u) на выходе из просмотра в глубину в том случае, если значение метки вершины u меньше, чем метка вершины v (Lowpg[v]:= Min(Lowpg[v],Lowpg[u])). Для нашего примера массив меток Lowpg имеет вид: (1,1,1,2,4,4,4,9,8). Осталось определить момент вывода компоненты двусвязности. Мы рассматриваем ребро (v,u), и оказывается, что значение Lowpg[u] больше или равно значению Num[v]. Это говорит о том, что при просмотре в глубину между вершинами v и u не было обратных ребер. Вершина v - точка сочленения, и необходимо вывести очередную компоненту двусвязности, начинающуюся с вершины v.
Итак, логика.
procedure Dvy(v,p:integer);{вершина p - предок вершины v}
{массивы A, Num, Lowpg и переменная nm - глобальные}
var u:integer;
begin
Inc(nm);Num[v]:=nm;Lowpg[v]:=Num[v];
for u:=1 to N do
if A[v,u]<>0 then if Num[u]=0 then begin
<сохранить ребро (v,u) в стеке>;
Dvy(u,v);
Lowpg[v]:=Min(Lowpg[v],Lowpg[u]);
{функция, определяющая минимальное из двух чисел }
if Lowpg[u]>=Num[v] then <вывод компоненты>;
end
else if (u<>p) and (Num[v]>Num[u]) then begin
{u не совпадает с предком вершины v}
<сохранить ребро (v,u) в стеке>;
Lowpg[v]:=Min(Lowpg[v],Num[u]);
end;
end;
Фрагмент основной логики:
....
FillChar(Num,SizeOf(Num),0);
FillChar(Lowpg,SizeOf(Lowpg),0);
nm:=0;
for v:=1 to N do if Num[v]=0 then Dvy(v,0);
....
Дополнение. Мостом графа G называется каждое ребро, удаление которого приводит к увеличению числа связных компонент графа. Разработать программу нахождения всех мостов графа. Покажите, что мосты графа должны быть в каждом каркасе графа G. Каким образом знание мостов графа может изменить (ускорить) логику нахождения всех его каркасов?
Заключение
Итак, деревом называют произвольный связный неориентированный граф без циклов. Его можно определить и по-другому: связный граф, содержащий N вершин и N-1 ребер, либо граф, в котором каждая пара вершин соединена одной и только одной простой цепью. Для произвольного связного неориентированного графа G=<V,E> каждое дерево <V,T>, где TE называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называют ветвями, а остальные ребра графа - хордами.
Литература
Адельсон-Вельский Г.М., Диниц Е.А., Карзанов А.В. Потоковые алгоритмы.-М.:Наука,1975.
Берж К. Теория графов и ее применение. - М.: ИЛ, 1962.
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. - М.: Наука, 1990.
Зыков А. А. Теория конечных графов.-Новосибирск:Наука; Сиб. отд-ние, 1969.
Йенсен П., Барнес Д. Потоковое программирование.-М.:Радио и связь,1984.
Касьянов В.Н., Сабельфельд В.К. Сборник заданий по практикуму на ЭВМ. - М.: Наука, 1986.
Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.
Кофман А. Введение в прикладную комбинаторику.-М.:Наука,1975.
Липский В. Комбинаторика для программистов.-М.:Мир, 1988.
Майника Э. Алгоритмы оптимизации на сетях и графах.-М.:Мир,1981.
Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях.-Новосибирск: Наука; Сиб. отд-ние, 1990.
Окулов С.М.Конспекты занятий по информатике (алгоритмы на графах). Учебное пособие для студентов и учителей школ. - Киров, 1996.
Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация: Алгоритмы и сложность.-М.:Мир,1985.
Свами М., Тхуласираман К. Графы, сети и алгоритмы.- М.:Мир,1984.
Филипс Д., Гарсиа-Диас А. Методы анализа сетей. - М.: Мир, 1984.
Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях.-М.:Мир,1963.
Фрэнк Г., Фриш И. Сети, связь и потоки.-М.:Связь,1978.
Харари Ф. Теория графов.-М.:Мир,1973.
Ху Т. Целочисленное программирование и потоки в сетях.- М.:Мир,1974.
Подобные документы
Алгоритмы, использующие решение дополнительных подзадач. Основные определения теории графов. Поиск пути между парой вершин невзвешенного графа. Пути минимальной длины во взвешенном графе. Понятие кратчайшего пути для графов с помощью алгоритма Флойда.
реферат [39,6 K], добавлен 06.03.2010Сбалансированные многоходовые деревья поиска. Исследование структуры B+-дерева, её основные операции. Доказательство их вычислительной сложности. Утверждение о высоте. Поиск, вставка, удаление записи, поиск по диапазону. B+-деревья в системах баз данных.
курсовая работа [705,5 K], добавлен 26.12.2013Разработка программного продукта для поиска максимально удалённых вершин в графе. Характеристика ориентированного, смешанного и изоморфного графов. Обзор способов представления графа в информатике. Алгоритм поиска пути. Графический интерфейс программы.
курсовая работа [384,0 K], добавлен 10.01.2015Методы поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям и свойствам. Понятие независимых множеств и порядок их генерации. Определение доминирующего множества. Основные этапы решения задачи о наименьшем разбиении.
контрольная работа [32,1 K], добавлен 11.03.2010Вершина в заданном графе с различным количеством вершин. Результаты обработки графа программой MyProject.exe. Сопряжение модулей программы. Модуль вывода матрицы смежности. Тесты черного ящика. Комбинаторное покрытие условий тестами черного ящика.
курсовая работа [44,8 K], добавлен 13.10.2012Определение понятия графа как набора вершин и связей между ними. Способы решения задач по программированию согласно теории графов на примерах заданий "Дороги", "Перекрестки", "Скрудж Мак-Дак", используя рекурсивные функции и рекуррентные соотношения.
курсовая работа [36,2 K], добавлен 10.03.2010Основные понятия и определения алгоритмов на графах. Связные графы без циклов, свободное дерево или дерево без корня. Ориентированные графы (орграфы), их использование для представления отношений между объектами. Матрицы смежности и инциденций.
презентация [93,9 K], добавлен 13.09.2013Разработка программы, находящей эйлеров путь в графе с количеством вершин n от 2 до 20. Входные и выходные данные. Алгоритм поиска эйлерова пути с возвратом массива, содержащего результат. Описание модулей. Проектирование тестов методами черного ящика.
курсовая работа [89,9 K], добавлен 25.02.2012Способы построения остовного дерева (алгоритма поиска в глубину и поиска в ширину). Вид неориентированного графа. Понятие и алгоритмы нахождения минимальных остовных деревьев. Последовательность построения дерева графов по алгоритмам Крускала и Прима.
презентация [22,8 K], добавлен 16.09.2013Понятие и базовые свойства ориентированного дерева. Обходы (способы нумерации вершин) в глубину и ширину. Представление бинарных графов с помощью указателей и массива, скобочной записи, списком прямых предков. Сбалансированность дерева двоичного поиска.
презентация [330,6 K], добавлен 19.10.2014