По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
4. Алгоритмы на графах 157 Var Begin For u:=l To N Do If Then If Then Begin ребро (v,u) в стеке>; Dvy (u,v) ; ) ; { определяющая минимальное из двух чисел. *} If Then <вывод компоненты>; End Else If (u<>p) And Then Begin не совпадает с предком вершины v. *} <сохранить ребро (v,u) в стеке>; End; End; Фрагмент основной логики: FillChar (Lowpg) ,0) ; For v:=l To N Do If Then Dvy(v,0) ; Мостом графа G называется каждое ребро, удаление которо- го приводит к увеличению числа связных компонент графа. Разработать программу нахождения всех мостов графа. Пока- жите, что мосты графа должны быть в каждом каркасе графа G. Каким образом знание мостов графа может изменить (уско- рить) логику нахождения всех его каркасов? 4.5. Циклы 4.5.1. Эйлеровы циклы Эйлеров цикл — это такой цикл, который проходит ровно один раз по каждому ребру. Теорема. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечет- ной степени равно нулю. 158 Алгоритмы на графах Не все графы имеют эйлеровы циклы, но если эйлеров цикл существует, то это означает, что, следуя вдоль этого цикла, можно нарисовать граф на бумаге, не отрывая от нее каранда- ша. Дан граф G, удовлетворяющий условию теоремы. Требует- ся найти эйлеров цикл. Используется просмотр графа методом поиска в глубину, при этом ребра удаляются. Порядок просмот- ра (номера вершин) запоминается. При обнаружении вершины, из которой не выходят ребра, мы их удалили, ее номер записы- вается в стек, и просмотр продолжается от предыдущей верши- ны. Обнаружение вершин с нулевым числом ребер говорит о том, что найден цикл. Его можно удалить, четность вершин (количество выходящих ребер) при этом не изменится. Процесс продолжается до тех пор, пока есть ребра. В стеке этого будут записаны номера вершин графа в порядке, соответствую- щем эйлерову циклу. Procedure переменные: А - матрица смежности, CV - стек; - указатель стека. *} Var Begin For To N Do If A[v,j]<>0 Then Begin A[v,j] Search (j) End; End; Пример графа и содержимое сте- ка после работы процедуры Se- arch. 4.5.2. циклы Граф называется гамильтоновым, если в нем имеется цикл, содержащий каждую вершину этого графа. Сам цикл также на- зывается гамильтоновым. Не все связные графы гамильтоновы. На рисунке дан пример графа, не имеющего гамильтонова цикла. Дан связный неориентированный граф G. Требуется найти все гамильтоновы циклы графа, если они есть. Метод реше- ния — перебор с возвратом (backtracking). Начинаем поиск ре- шения, например, с первой вершины графа. Предположим, что уже найдены первые k компонент решения. Рассматриваем 4. Алгоритмы на графах 159 ребра, выходящие из последней вершины. Если есть такие, что идут в ранее не просмотренные вершины, то включаем эту вер- шину в решение и помечаем ее как просмотренную. Получена компонента решения. Если такой вершины нет, то воз- вращаемся к предыдущей вершине и пытаемся найти ребро из нее, выходящее в другую вершину. Решение получено при про- смотре всех вершин графа и возможности достичь из последней первой вершины. Решение (цикл) выводится, и продолжается процесс нахождения следующих циклов. Пример графа и часть дерева перебора вариантов, показывающего механизм работы данного метода, приведен на рисунке. Procedure {* к - номер итерации. Глобальные переменные: А - матрица смежности; St - массив для хранения порядка просмотра вершин графа; - массив признаков: вершина просмотрена или нет. *} Var Begin v:=St {*Номер последней вершины. For N Do If (A[v,j]<>0) Then ребро между вершинами с номерами v и j . *} If (k=N+l) And (j=l) Then <вывод цикла> Else Then Begin не просмотрена. *} Nnew[j]:=False; Gm(k+1) ; Nnew[j]:=True; End; End; 160 4. Алгоритмы на графах Фрагмент основной программы. St[l] Gm(2) 4.5.3. Фундаментальное множество циклов Каркас (V,T) связного неориентированного графа G= содержит N-1 ребро, где N — количество вершин G. Каждое ребро, не принадлежащее Т, т. е. любое ребро из Е-Т, порожда- ет в точности один цикл при добавлении его к Т. Такой цикл является элементом фундаментального множества циклов гра- фа G относительно каркаса Т. Поскольку каркас состоит из N—1 ребра, в фундаментальном множестве циклов графа G от- носительно любого каркаса имеется циклов, где М — количество ребер в G. Пример графа, его каркаса и множества фундаментальных циклов приведен на рисунке. Поиск в глубину является естественным подходом, исполь- зуемым для нахождения фундаментальных циклов. Строится каркас, а каждое обратное ребро порождает цикл относительно этого каркаса. Для вывода циклов необходимо хранить поря- док обхода графа при поиске в глубину (номера вершин) — мас- сив St, а для определения обратных ребер вершины следует «метить» (массив в той очередности, в которой они про- сматриваются. Если для ребра Начальная инициализация переменных. For N Do Gnum[j ] :=0; 4. Алгоритмы на графах 161 Основная логика. Procedure А - матрица смежности графа; St - массив для хранения номеров вершин графа в том порядке, в котором они используются при построении каркаса; - указатель записи в массив St; - для каждой вершины в соответствующем элементе массива фиксируется номер шага , на котором она просматривается при поиске в глубину. *} Var Begin For j :=1 To N Do If A[v,j]<>0 Then If Then j не просмотрена.*} Else If (j<>St[yk-l]) And (Gnum[j] <вывод цикла из St>(*j не предыдущая вершина при и она была просмотрена ранее. *}; Dec (yk); End; Название «фундаментальный» связано с тем, что каждый цикл графа может быть получен из циклов этого множества. Для произвольных множеств А В определим операцию симметриче- ской разности Известно, что произвольный цикл графа G можно однозначно представить как симметриче- скую разность некоторого числа фундаментальных циклов. Одна- ко не при всех операциях симметрической разности получаются циклы (вырожденный случай). Исследовательская работа — раз- \ работать программу нахождения всех циклов графа. 4.6. Кратчайшие пути 4.6.1. Постановка задачи. Вывод пути Дан ориентированный граф веса дуг — где — количество вершин графа), начальная и ко- нечная вершины — Веса дуг записаны в матрице смеж- ности А, если вершины i и у не связаны дугой, то Путь между s t о ц е н и в а е т с я Н а й т и путь с минима- льной оценкой. 162 Алгоритмы на графах Пример. Кратчайший путь из 1 в 4 проходит через 3-ю и 2-ю вершины и имеет оценку 6. Особый случай — контуры с отри- цательной оценкой. Пример. При и обходя контур достаточное число раз, можно сделать так, что оценка пути между вершинами 1 и 5 будет меньше любого целого числа. Оценку пути на- зовем его весом или длиной. Будем рассматривать только графы без кон- туров отрицательного веса. Нам необходимо найти кратчайший путь, т. е. путь с мини- мальным весом, между двумя вершинами графа. Эта задача разбивается на две подзадачи: сам путь и значение минималь- ного веса. Обозначим ее через D[s,t]. Неизвестны алгоритмы, определяющие только D[s,t], все они определяют оценки от вершины s до всех остальных вершин графа. Определим D как Of Integer. Предположим, что мы определили зна- чения элементов массива D — решили вторую подзадачу. Опре- делим сам кратчайший путь. Для существует такая вер- шина v, что D[t]=D[v]+A[v,t]. Запомним v (например, в стеке). Повторим процесс поиска вершины и, такой, что и так до тех пор, пока не дойдем до верши- ны с номером s. Последовательность t, v, и, .,., s дает кратчай- ший путь. Procedure A - глобальные структуры данных. St - локальная структура данных для хранения номеров вершин. *} Var Procedure Print; содержимое St.*} Begin End; Begin <почистить St>; <занести вершину с номером t в St>; While vOs Do Begin и:=<номер вершины, для которой =D[u] +A[u,v]>; <занести вершину с номером v в St>; 4. Алгоритмы на графах 163 v:=u; End; End; Итак, путь при известном D находить мы умеем. Осталось научиться определять значения кратчайших путей, т. е. эле- менты массива D. Идея всех известных алгоритмов заключает- ся в следующем. По данной матрице весов вычисляются пер- воначальные верхние оценки. А затем пытаются их улучшить до тех пор, пока это возможно. Поиск улучшения, например для D[vJ, заключается в нахождении вершин и, таких, что D[u]+A[u,v] D[vJ можно заменить на D[u]+A[u,v]. 4.6.2. Алгоритм Дейкстры Дан ориентированный граф s — вершина-источ- ник; матрица смежности А Of Integer); для любых и, вес дуги неотрицательный Резуль- тат — массив кратчайших расстояний D. В данном алгоритме формируется множество вершин Т, для которых еще не вычислена оценка расстояние и, во-вторых (это главное), минимальное значение в В по множеству вершин, принадлежащих Т, считается окончательной оценкой для вер- шины, на которой достигается этот минимум. С точки зрения здравого смысла этот факт достаточно очевиден. Другой «за- ход» в эту вершину возможен по пути, содержащему большее количество дуг, а так как веса неотрицательны, то и оценка пути будет больше. Пример. Граф и его матрица смежности: В таблице приведена последовательность шагов (итераций) работы алгоритма. На первом шаге минимальное значение D достигается на второй вершине. Она исключается из множества Т, и улучшение оценки до оставшихся вершин (3,4,5,6) ищется не по всем вершинам, а только от второй. 164 4. Алгоритмы на графах Procedure (*А, D, N - глобальные величины. *} Var i,u: Integer; Of 1. Begin For i:=l To N Do i] ; D[s]:=0; T: While ] Do Begin и:=<то значение 1, при котором достигается T:=T-[u]; For To N Do If i In T Then +A[u, i] ) ; End; End; Время работы алгоритма 4.6.3. Пути в бесконтурном графе Дан ориентированный граф без контуров, веса дуг произвольны. Результат — массив кратчайших расстояний (длин) D от фиксированной вершины s до всех остальных. Утверждение — в произвольном бесконтурном графе вершины можно перенумеровать так, что для каждой дуги Пример. Введем следующие структу- ры данных: • массив определяет число дуг, входящих в вершину с но- мером • массив Num, Num[i] определяет новый номер вершины 4. Алгоритмы на графах 165 • массив St, для хранения номеров вершин, в которые захо- дит нулевое количество дуг. Работа с массивом осуществ- ляется по принципу стека; • переменная птп, текущий номер вершины. Суть алгоритма. Вершина i, имеющая нулевое значение Nu- mln (а такая вершина на начальном этапе обязательно есть в силу отсутствия контуров в графе), заносится в St, ей присваи- вается текущее значение птп (запоминается в и изменя- ются значения элементов для всех вершин, связанных с Процесс продолжается до тех пор, пока St не пуст. Трасси- ровка работы алгоритма для нашего примера приведена в таб- лице. № итерации начальная 1 2 3 4 5 6 Numln [2,2,2,1,0,1] [2,2,1,0,0,1] [1,2,0,0,0,1] [0,2,0,0,0,0] [0,1,0,0,0,0] [0,0,0,0,0,0] [0,0,0,0,0,0] Num [0,0,0,0,0,0] [0,0,0,0,1,0] [0,0,0,2,1,0] [0,0,3,2,1,0] [0,0,3,2,1,4] [5,0,3,2,1,4] [5,6,3,2,1,4] [5] [4] [3] [6,1] [1] [2] 0 1 2 3 4 5 6 Procedure {*A, Num — глобальные структуры данных. *} Var Of Integer; Begin For To N Do For To N Do If Then Inc(NumIn[j]) ; For To N Do If Then Begin End; While yk<>0 Do Begin For To N Do If A[u,i]<>0 Then Begin [i]) ; If Then Begin 166 4. Алгоритмы на графах End; End; End; End; Итак, пусть для графа G выполнено условие утверждения (вершины перенумерованы) и нам необходимо найти кратчай- шие пути (их длины) от первой вершины до всех остальных. Пусть мы находим оценку для вершины с номером Достаточ- но просмотреть вершины, из которых идут дуги в вершину с номером i. Они имеют меньшие номера, и оценки для них уже известны. Остается выбрать меньшую из них. Procedure Dist;{*D, А - глобальные величины. *} Var Begin D[l]:=0; For i:=2 To N Do D[i] значение матрице смежности с какой целью вычитается из максимальный элемент матрицы А.*} For N Do For Do If A[j Then : +A[j ) ; End; Процедура написана в предположении о том, что и — но- вые номера вершин и A[i,j] соответствует этим номерам. Одна- ко это не так. Новые номера по результатам работы предыду- щей процедуры хранятся в массиве Num. Требуется «стыковка» новых номеров и матрицы А. Как это сделать наи- лучшим образом? Время работы алгоритма 4.6.4. Кратчайшие пути между всеми парами вершин. Алгоритм Флойда Дан ориентированный граф с матрицей весов Of Integer). В результате должна быть сформиро- вана матрица D кратчайших расстояний между всеми парами вершин графа и кратчайшие пути. Идея алгоритма. Обозначим через оценку кратчайшего пути из £ в с промежуточными вершинами из множества [l..m]. Тогда имеем: и Второе равенство требует пояснения. Пусть мы на- ходим кратчайший путь из в у с промежуточными вершинами из множества Если этот путь не содержит вершину 4. Алгоритмы на графах 167 Если же он содержит эту вершину, то его можно разделить на две части: от i до и от до у. Время работы алгоритма Procedure Dist/ D - глобальные структуры данных. *} Var Begin For To N Do To N Do D[i,j] ; For i : = 2 To N Do D[i,i] For To N Do For To N Do For j:=l To N Do , End; Пример графа и значений мат- риц типа D при работе процеду- ры. Верхний индекс у D указывает номер итерации (значение m в процедуре Dist). Расстояния между парами вершин дает D. Для вывода са- мих кратчайших путей введем матрицу М того же типа, что и D. Элемент M[i,j] определяет предпоследнюю вершину крат- чайшего пути из i в у. Процедура Dist претерпит небольшие изменения. В том слу- чае, когда больше изменяется не только D[i,jJ, но и M[i,j]. M[i,j] присваивается значение M[m,j]. Для нашего примера изменения М выглядят следующим образом. Например, необходимо вывести кратчайший путь из 3-й вер- шины во 2-ю. Элемент М[3,2] равен 1, поэтому смотрим на элемент М[3,1]. Он равен четырем. Сравниваем М[3,4] с 3-й. Есть совпадение, мы получили кратчайший путь: Алгоритмы на графах Procedure пути между вершинами i и j . *} Begin If M[i,j]=i Then If Else (i, Else Begin All_Way (i ] ) ;All_Way ,j ] ; End; End; 4.7. Независимые и доминирующие множества Задача поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям, свойствам, возни- кает достаточно часто. 4.7.1. Независимые множества Дан неориентированный граф G=(V,E). Независимое множе- ство вершин есть множество вершин графа G, такое, что любые две вершины в нем не смежны, т. е. никакая пара вершин не соединена ребром. Следовательно, любое подмножество S, со- держащееся в V, и такое, что пересечение S с множеством вер- шин смежных с S пусто, является независимым множеством вершин. Пример. Множества вершин (1, 2), (3, 4, 5), (4, 7), (5, 6) независимые. Независи- мое множество называется максима- льным, когда нет другого независи- мого множества, в которое оно бы входило. Если Q является семейст- вом всех независимых множеств гра- фа G, то число называется числом независимости графа G, а множество S*, на котором этот максимум достигается, называется наибольшим независимым множеством. Для нашего примера a[G]=3, a S* есть (3, 4, 5). Понятие, противоположное максимальному независимому множеству, есть максимальный полный подграф (клика). В максимальном независимом множестве нет смежных вершин, в клике все вершины попарно смежны. Максимальное независи- мое множество графа G соответствует клике графа G', где G' — дополнение графа G. 4. Алгоритмы на графах 169 Для нашего примера дополнение G' приведено на следую- щем рисунке (часть а), клика графа соответствует максимальному независимому множеству графа G. Число неза- висимости графа G' равно 4, максимальное независимое мно- жество (2, 5, 7, 8), ему соответствует клика графа G (часть в). Метод генерации всех максимальных независимых множеств графа Задача решается перебором вариантов. «Изюминкой» являет- ся отсутствие необходимости запоминать генерируемые множе- ства с целью проверки их на максимальность путем сравнения с ранее сформированными множествами. Идея заключается в по- следовательном расширении текущего независимого множества — номер шага или номер итерации в процессе построения). Очевидно, что если мы не можем расширить текущее решение, то найдено максимальное независимое множество. Выведем его и продолжим процесс поиска. Будем хранить текущее решение в массиве Ss Of Integer), его первые элементов определяют текущее решение. Логика вывода решения очевидна (процедура Print). В процессе решения нам придется многократно рассматри- вать вершины графа, смежные с данной. При описании графа матрицей смежности — это просмотр соответствующей строки, при описании списками связи — просмотр списка. Упростим нахождение смежных вершин за счет использования нового способа описания графа. Используем множественный тип дан- ных. Введем тип данных: Type Of 1..N и переменную Var A:Array[l..N] Of Sset. Итак, чтобы определить вершины графа, смежные с верши- ной i, необходимо просто вызвать соответствующий элемент массива А. Пример. Основная сложность алгоритма в выборе очередной вершины графа. Введем переменную Gg для хранения номеров 170 4. Алгоритмы на графах вершин — кандидатов на расширение текущего реше- ния. Значение переменной формируется на каждом шаге k. Что является исход- ной информацией для фор- мирования Очевидно, что некоторое множество вершин, свое для каждого шага (итерации) Логически пра- вомерно разбить это множество вершин на не использованные ранее (Qp) и использованные ранее Изменение значений Qp и происходит при возврате на выбор ft-го элемента мак- симального независимого множества. Мы выбирали на шаге, например, вершину с номером i, и естественно исключение ее из Qp и при поиске следующего максимального независи- мого множества. Кроме того, при переходе к шагу с номером из текущих множеств Qp и для следующего шага не- обходимо исключить вершины, смежные с вершиной i, выбран- ной на данном шаге (из определения независимого множества), и, разумеется, саму вершину Итак, общая логика. Procedure Var Gg:Sset; Begin If (Qp=[ ]) And ]) Then Begin Print (к) ; множества кандидатов Gg для расширения текущего решения (к элементов в массиве Ss) по значениям Qp и - "черный ящик А".>; While Do Begin If i In Gg Then Begin Find Qp-A [i]-[i] , Qm-A [i] - ) <изменение Qp, Qm для этого уровня (значения к) и, изменение множества кандидатов Gg - "черный ящик Б".>; End; Inc(i) ; End; End; 4. Алгоритмы на графах 171 Продолжим уточнение логики. Нам потребуется простая функция подсчета количества элементов в переменных типа Sset. Function Var i, Begin For To N Do If i In A Then Inc(cnt) End; Используем метод трассировки для того, чтобы найти даль- нейшую логику уточнения решения. Будем делать разрывы таблицы для внесения пояснений в работу черных ящиков. 1 2 Qp [1-5] [4,5] |