Реферат: Некоторые основные алгоритмы обработки графов
Раздел 1.Некоторые основные алгоритмы обработки графов 1.1.Нахождение минимального пути в графеПуть в орграфе D из вершины v в вершину w, где v w, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.
Назовем орграф D = (V,X) нагруженным, если на множестве дуг X определена некоторая функция l : X R, которую часто называют весовой функцией. Значение l(x) будем называть длиной дуги x. Предположим, что l(x) 0. Длиной пути П в нагруженном орграфе будем называть величину l(П), равную сумме длин дуг, входящих в П, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь.
Нагруженный орграф можно задать с помощью матрицы весов С(D) = {cij}nxn с элементами
l(vi,vj), если (vi,vj) X,
cij =
, если (vi,vj) X.
^ 1.1.1А л г о р и т м Д е й к с т р ы Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры. Заданы две системы двусторонних дорог с одним и тем же множеством городов (железные и шоссейные дороги). Найти минимальный по длине путь из города А в город В (который может проходить как по железным, так и по шоссейным дорогам) и места пересадок с одного вида транспорта на другой на этом пути.
Рассмотрим алгоритм Дейкстры, который позволяет определить минимальный путь в орграфе между двумя заданными вершинами при условии, что этот путь существует.
Пусть s – начальная вершина, t – конечная вершина. На каждой итерации любая вершина v имеет метку l*(v), которая может быть постоянной или временной. Постоянная метка l*(v) – это длина кратчайшего пути от s к v, временная метка l(v) – это вес кратчайшего пути из s в v, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.
Вторая метка (v) – это вершина, из которой вершина v получила свою метку.
А л г о р и т м Д е й к с т р ы
Данные: матрица весов С(D) орграфа D, начальная вершина s.
Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v V, а также последовательность вершин, определяющая кратчайший путь из s в v .
Положим l*(s) = 0 и будем считать эту метку постоянной. Для всех v V, v s, положим l*(v) = и будем считать эти метки временными. Положим p = s.
Для всех vГp с временными метками выполним: если l*(v)>l*(p)+l(p,v), то l*(v)=l*(p)+l(p,v) и (v) =р. Иначе l*(v) и (v) не менять, т.е. l*(v) = min (l*(t), l*(p)+cpv). (Идея состоит в следующем: пусть p – вершина, получившая постоянную метку l*(p) на
предыдущей итерации. Просматриваем все вершины vГp, имеющие временные метки. Метка l*(v) вершины vГp заменяется на l*(p)+l(p,v), если оказывается, что ее метка l*(v)>l*(p)+l(p,v). В этом случае говорим, что вершина v получила свою метку из вершины p, поэтому положим (v) = p. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l*(v) l*(p)+cpv, то метки остаются прежними.
Пусть V* - множество вершин с временными метками. Найдем вершину v* такую, что l*(v*) = min l*(v), v V*. Считать метку l*(v*) постоянной для вершины v*.
Положим p = v*. Если p = t, то перейдем к п.5 ( l*(t) – длина минимального пути ). Иначе перейдем к п.2.
Найдем минимальный путь из s в t, используя метки (v): П = s…(t)t.
Заметим, что, если продолжить работу алгоритма Дейкстры до тех пор, пока все вершины не получат постоянные метки, то мы получим расстояния от начальной вершины s до произвольной вершины графа.
^ 1.1.2А л г о р и т м Форда – Беллмана
Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Форда-Беллмана.
Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг C вычисляются некоторые верхние ограничения D[v] на расстояния от s до всех вершин vV. Каждый раз, когда мы устанавливаем, что D[u] + cuv < D[v], оценку D[v] улучшаем: D[v] = D[u] +cuv.
Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Можно показать, что значение каждой из переменных D[v] равно тогда d(s,v) - расстоянию от s до v. Заметим, что для того, чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Описанная общая схема является неполной, т.к. она не определяет очередности, в которой выбираются вершины u и v. Эта очередность оказывает сильное влияние на эффективность алгоритма. Опишем алгоритм Форда-Беллмана для нахождения расстояния от фиксированной точки s до всех остальных вершин графа.
Рассмотрим орграф D = (V,X), где V={v1,…,vn}.
А л г о р и т м Форда – Беллмана
Данные: матрица весов С(D) орграфа D, начальная вершина s.
Результат: расстояния от вершины s до всех вершин орграфа D: D[v] = d(s,v), v V.
Всем вершинам vV орграфа присвоим метку D[v] = csv. Вершине s присвоим метку D[s] = 0.
Положим k=1.
Выберем произвольную вершину v V \ {s}.
Выберем произвольную вершину u V.
Положим D[v] = min (D[v], D[u] + cuv).
Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.
Если вершина v пробежала еще не все множество вершин V \ {s}, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.
Если k < n-2, то положить k=k+1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D[v] будут равны расстояниям d(s,v) в орграфе D.
Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины s до вершины v.
Отметим, что закончить вычисления можно, когда выполнение цикла по k не вызывает изменения ни одной из переменных D[v].
Пример. Определим минимальные пути из вершины v1до всех остальных вершин в нагруженном орграфе D, изображенном на рис. 1.
v4
v1 5 2 2 v2
5 2
2 1 v3
12 v52
v6
Рис.1.
Ниже в таблице приведены матрица весов, а также все вычисления по шагам.
v1
v2
v3
v4
v5
v6
D(0)
D(1)
D(2)
D(3)
D(4)
v1
5
5
2
12
0
0
0
0
0
v2
2
7
5
5
5
v3
2
5
3
3
3
3
v4
2
5
4
4
4
4
v5
1
2
2
2
2
2
2
v6
12
9
9
7
7
На первом шаге всем вершинам vV орграфа присвоим метку D[v] = csv, где s = v1. Выберем следующую вершину v2. Ей присвоим метку D[v2] = min (D[v2], D[u] + cuv), где u V, т.е. D[v2] = min (D[v2], D[v3]+ c32, D[v4]+ c42, D[v5]+ c52, D[v6]+ c62) = (,5+2, 5+2, 2+, 12+) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.
Аналогично корректируются метки всех оставшихся вершин, а именно,
D[v3] = min (D[v3], D[v2]+c23, D[v4]+c43, D[v5]+c53, D[v6]+c63) = (5,7+, 5+, 2+1, 12+) = 3,
D[v4] = min (D[v4], D[v2]+c24, D[v3]+c34, D[v5]+c54, D[v6]+c64) = (5,7+, 3+, 2+2, 12+) = 4,
D[v5] = min (D[v5], D[v2]+ c25, D[v3]+ c35, D[v4]+ c45, D[v6]+ c65) = (2,7+, 3+, 4+, 12+) = 2,
D[v6] = min (D[v6], D[v2]+ c26, D[v3]+ c36, D[v4]+ c46, D[v5]+ c56) = (12,7+2, 3+, 4+, 2+) = 9.
Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n-2 = 4.
Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v1до всех остальных вершин. Например, длина минимального пути из v1 в v2равна 5, сам путь имеет вид: v1v5v3v2.
^ 1.1.3А л г о р и т м Ф л о й д а
Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда. Найти диаметр графа, т.е. максимум расстояний между всевозможными парами его вершин. ^ Найти медиану графа, т.е. такую вершину, сумма расстояний от которой до остальных минимальна. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города (столицы) больше N. Определить N-периферию для заданного N. ^ Найти все вершины графа, к которым существует путь заданной длины от выделенной его вершины. Найти сами пути.
Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз (поочередно для каждой вершины) один из описанных ранее алгоритмов. Однако оказывается, что n-кратное использование этих алгоритмов не является наилучшим методом. Рассмотрим более эффективный алгоритм для решения поставленной задачи – алгоритм Флойда.
Идея этого алгоритма следующая. Рассмотрим орграф D = (V,X), где V={v1,…,vn}. Обозначим через dij(m) длину кратчайшего из путей из vi в vj с промежуточными вершинами из множества {v1,…,vm}.
Тогда имеем следующие уравнения:
dij(0) = cij,
dij(m+1) = min ( dij(m), dim(m) + dmj(m)).
Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из vi в vj с промежуточными вершинами из множества {v1,…, vm,vm+1}. Если этот путь не содержит vm+1 , то dij(m+1) = dij(m) . Если же он содержит vm+1 , то, деля путь на отрезки от vi до vm+1 и от vm+1 до vj , получаем равенство dij(m+1) = dim(m) + dmj(m) . Приведенные уравнения дают возможность вычислить расстояния d(vi,vj) = dij(n) , где 1 i, j n.
А л г о р и т м Ф л о й д а
Данные: матрица весов С(D) орграфа D.
Результат: расстояния между всеми парами вершин D[i,j] = d(vi,vj).
Для всех i = 1,…,n , j = 1,…,n положим D[i,j] = cij .
Для всех i = 1,…,n положим D[i,i] = 0.
Положим m = 1.
Положим i = 1.
Положим j = 1.
D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ).
Если j < n, то положим j = j + 1 и переходим к шагу 6.
Если i < n, то положим i = i + 1 и переходим к шагу 5.
Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D[i,j] дают расстояния между вершинами vi и vj .
Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины vi до вершины vj.
Пример. Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рис.1. Все вычисления будем проводить с помощью матриц D.
m = 1 m = 2
v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0
5
5
2
12
v1
0
5
5
2
12
v2
0
2
v2
0
2
v3
2
0
v3
2
0
v4
2
0
v4
2
0
v5
1
2
0
v5
1
2
0
v6
0
v6
0
Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения, т.к. D[i,j] = min ( D[i,j], D[i,m] + D[m,j] ). Поэтому рассмотрим случай, когда i = 2 , а j = 3. Тогда D[2,3] = min ( D[2,3], D[2,1] + D[1,3] ) = min (,+5) = . Далее, j = 4, т.е. D[2,4] = min(D[2,4], D[2,1] + D[1,4] ) = min (,+5) = . Продолжаем процесс до тех пор, пока i 6 и j 6. Положим m = 2 и продолжим рассуждения дальше.
m = 3 m = 4
v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0
5
5
2
12
v1
0
7
5
5
2
9
v2
0
2
v2
0
2
v3
2
0
4
v3
2
0
4
v4
2
0
4
v4
2
0
4
v5
1
2
0
v5
3
1
2
0
5
v6
0
v6
0
m = 5 m = 6
v1
v2
v3
v4
v5
v6
v1
v2
v3
v4
v5
v6
v1
0
7
5
5
2
9
v1
0
5
3
4
2
7
v2
0
2
v2
0
2
v3
2
0
4
v3
2
0
4
v4
2
0
4
v4
2
0
4
v5
3
1
2
0
5
v5
3
1
2
0
5
v6
0
v6
0
Матрица D:
v1
v2
v3
v4
v5
v6
v1
0
5
3
4
2
7
v2
0
2
v3
2
0
4
v4
2
0
4
v5
3
1
2
0
5
v6
^ 1.2.Эйлеровы цепи и циклы
Пусть G – псевдограф. Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G.
Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.
Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени. Если указанное условие выполняется, то любая эйлерова цепь псевдографа G соединяет вершины нечетной степени.
Пусть G – связный мультиграф, степени вершин которого – четные числа.
^ Построить эйлеров цикл в графе.
А л г о р и т м построения эйлерова цикла
Данные: матрица инцидентности В(G) мультиграфа G.
Результат: последовательность ребер, образующих эйлеров цикл.
Выбрать произвольную вершину v.
Выбрать произвольное ребро x, инцидентное v, и присвоить ему номер 1. (Назовем это ребро “пройденным”).
Каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего вычеркнутого ребра.
Находясь в вершине w, не выбирать ребра, соединяющего w с v, если только есть возможность другого выбора.
Находясь в вершине w, не выбирать ребра, которое является “перешейком” (при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру).
После того, как в графе будут занумерованы все ребра, цикл = [xi1, xi2,…, xim], образованный ребрами с номерами от 1 до m, где m – число ребер в графе, есть эйлеров цикл.
Замечание. Прежде чем строить эйлеров цикл, проверить условие существования этого цикла.
^ Построить эйлерову цепь в графе.
Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе.
^ 1.3.Гамильтоновы цепи и циклы
Пусть G – псевдограф. Цепь (цикл) в G называется гамильтоновой (гамильтоновым), если она (он) проходит через каждую вершину псевдографа G ровно один раз. Простейшим достаточным условием существования гамильтоновых цепей и циклов в графе является его полнота. Граф G называется полным, если каждая его вершина смежна со всеми остальными вершинами. Необходимым условием существования гамильтоновых цепей и циклов в графе G является связность данного графа.
Приведем некоторые наиболее простые методы выделения гамильтоновых цепей и циклов в графе G =(V,X), где V = {v1 ,v2 ,…,vn}. Самым простым является метод перебора всевозможных перестановок vi1 ,vi2 ,…,vin множестваV. Для каждой из них проверяем, является ли vi1vi2…vin маршрутом вG. Если является, то vi1vi2 …vin- гамильтонова цепь вG, в противном случае переходим к другой перестановке. Тогда по окончании перебора будут выделены все гамильтоновы цепи в графе G. Аналогично для выделения гамильтоновых циклов перебираем всевозможные перестановки v1vi1vi2 …vin-1 множества V, для каждой из которых проверяем, является ли v1vi1vi2…vin-1v1маршрутом в G. Если является, то v1vi1vi2…vin-1v1 – гамильтонов цикл в G, в противном случае переходим к следующей перестановке. Тогда по окончании перебора будут выделены все гамильтоновы циклы в графе G. Очевидно, что при выделении гамильтоновых цепей придется перебрать n! перестановок, а при выделении всех гамильтоновых циклов - (n-1)! перестановок. При этом в случае полного графа ни одна из перестановок не окажется отброшенной, т.е. данный метод является эффективным для графов, близких к полным.
Отметим, что описанный метод не учитывает информации об исследуемом графе ^ G и является как бы ориентированным на самый “худший” случай, когда G – полный граф.
Для того, чтобы сократить число шагов в предложенном методе, рассмотрим следующий алгоритм. Предположим, что решение имеет вид последовательности <v1, ... vn>. Идея метода состоит в следующем: решение строится последовательно, начиная с пустой последовательности (длины 0). Далее, имея частичное решение <v1, ... vi>, ищем такое допустимое значение vi+1, которое еще не было использовано, добавляем его к пройденному частичному решению и продолжаем процесс для нового частичного решения <v1, ... vi+1>. В противном случае, если такого значения vi+1 не существует, возвращаемся к предыдущему частичному решению <v1, ... vi-1> и продолжаем процесс, пытаясь определить новое, еще не использованное допустимое значение vk. Такие алгоритмы носят название “алгоритмы с возвратом” (англ.: backtracking).
2 1
1 5 3 12 14
4
123 125 143 145
1234 1235 1253 1254 1432 1435 1452 1453
14321 14352
12341 12354 12534
14325 14521 14532
12345 12541 12543 14523
123541 125341 143521 145321
Рис. 2
Процесс поиска с возвращением удобно проиллюстрировать в терминах обхода в глубину в некотором дереве поиска, которое строится следующим образом. Каждая вершина дерева соответствует некоторому частичному решению <v1,...vi>, причем вершины, соответствующие последовательностям вида <v1,.. vi, y>, и являются преемниками вершины <v1,... vi>. Корнем данного дерева является пустая последовательность. В случае построения гамильтонова цикла в качестве корня может выступать любая вершина.
При обходе дерева в глубину вершины дерева посещаются в таком порядке: сначала посещаем корень дерева v1, а затем (если v1 – не висячая вершина) для каждого преемника vi корня v1 рекурсивно обращаемся к процедуре обхода в глубину для того, чтобы обойти все поддеревья с корнями vi в порядке, в котором упорядочены вершины vi как преемники корня v1.
Пример.
На рис.2 показаны граф и дерево, иллюстрирующее процесс нахождения всех гамильтоновых циклов с помощью алгоритма с возвратом.
Гамильтоновы циклы – 123541, 125341, 143521, 145321.
^ 1.3.1Генерирование всех перестановок заданного множества
Напомним, что перестановкой n-элементного множества X называется упорядоченный набор длины n, составленный из попарно различных элементов множества X. Опишем некоторые методы генерирования последовательности всех n перестановок n-элементного множества. Не нарушая общности будем рассматривать не исходное множество Х, а множество А={1,2,…n} – множество индексов элементов, т.к. между множеством элементов из Х и множеством индексов из А существует взаимно однозначное соответствие, которое задается в виде: xi i.
Будем предполагать, что элементы множества запоминаются в виде элементов массива Р1,…, Рn. Во всех методах элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных Рi и Рj, где 1i, jn. Эту операцию будем обозначать Рi :=: Рj. Очевидно, что она эквивалентна последовательности команд: а := Рi Рi := Рj Рj := а, где а – некоторая вспомогательная переменная.
Генерирование всех перестановок заданного множества в лексикографическом порядке
Данный метод легче всего понять, если в качестве переставляемых элементов взять числа 1,…,n. На множестве всех перестановок определим лексикографический порядок:
x1,x2,…xn < y1,y2,…,yn существует k1, такое что xk < yk и xp= yp для каждого p < k.
Заметим, что если вместо чисел 1,2,…, n взять буквы а,б,…,р с естественным порядком абв…р, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре.
Для примера приведем перестановки множества X = {1,2,3} в лексикографическом порядке:
123, 132, 213, 231, 312, 321.
Начиная с перестановки (1,2,…,n), переход от текущей перестановки P=(p1,p2,…,pn) к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляется последовательным выполнением следующих действий:
просмотр ^ Р справа налево в поисках самой правой позиции k, в которой pk<pk+1 (если такой позиции k нет, то текущая перестановка является последней и следует закончить генерацию);
просмотр P от pk слева направо в поисках наименьшего из таких элементов pm, что k<m и pk<pm; транспозиция элементов pk и pm и обращение отрезка pk+1,…, pn путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).
Например, для п=8 и Р=(2,6,5,8,7,4,3,1) имеем pk =5 и pm=7, результат транспозиции pk и pm - (2,6,7,8,5,4,3,1), результат обращения отрезка pk+1,…, pn переводит Р в перестановку (2,6,7,1,3,4,5,8), которая следует за Р в лексикографическом порядке.
Рекурсивный алгоритм генерирования всех перестановок заданного множества в лексикографическом порядке
Рассмотрим рекурсивный алгоритм генерирования перестановок в лексикографическом порядке. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:
^ в первой перестановке элементы идут в растущей последовательности, а в последней – в убывающей другими словами последняя перестановка является обращением первой, последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих возрастающим значениям элемента в первой позиции. Последние n-1 позиций блока, содержащего элемент р в первой позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в лексикографическом порядке.
В качестве примера рассмотрим генерирование всех перестановок для п=4. Таких перестановок будет 4!=24. Эти перестановки можно разбить на четыре блока, каждый из которых содержит 3!=6 перестановок, по значению элемента в первой позиции. В первом блоке на первом месте стоит 1, во втором – 2, в третьем – 3, в четвертом – 4. Далее рассмотрим блок с 1 на первом месте, для остальных аналогично. Для генерации всех перестановок оставшегося множества Х={2,3,4} выполним следующее: разобъем все перестановки на 3 блока по 2!=2 перестановки, соответствующих возрастающим значениям элемента в первой позиции, в первом блоке – 2, во втором – 3, в третьем – 4. Далее в каждом блоке генерируем все перестановки из оставшихся двух элементов в лексикографическом порядке (в первой из перестановок последние два элемента расположены в порядке возрастания). В результате получаем:
1
2
3
4
2
1
3
4
3
1
2
4
4
1
2
3
1
2
4
3
2
1
4
3
3
1
4
2
4
1
3
2
1
3
2
4
2
3
1
4
3
2
1
4
4
2
1
3
1
3
4
2
2
3
4
1
3
2
4
1
4
2
3
1
1
4
2
3
2
4
1
3
3
4
1
2
4
3
1
2
1
4
3
2
2
4
3
1
3
4
2
1
4
3
2
1
^
Генерирование всех перестановок заданного множества в антилексикографическом порядке
Антилексикографический порядок (обозначим ) определяется следующим образом:
x1,x2,…xn < y1,y2,…,y n существует такое kn, что xk yk и xp = yp для каждого p k..
Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.
Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:
в первой перестановке элементы идут в растущей последовательности, в последней – в убывающей другими словами, последняя перестановка – обращение первой,
последовательность всех перестановок можно разделить на n блоков длины (n-1), соответствующих убывающим значениям элемента в последней позиции. Первые n-1 позиций блока, содержащего элемент р в последней позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в антилексикографическом порядке.
Сгенерируем в антилексикографическом порядке все перестановки для n=4, получим
1
2
3
4
1
2
4
3
1
3
4
2
2
3
4
1
2
1
3
4
2
1
4
3
3
1
4
2
3
2
4
1
1
3
2
4
1
4
2
3
1
4
3
2
4
2
3
1
3
1
2
4
4
1
2
3
4
1
3
2
2
4
3
1
2
3
1
4
2
4
1
3
3
4
1
2
3
4
2
1
3
2
1
4
4
2
1
3
4
3
1
2
4
3
2
1
^ Построить гамильтонов цикл в графе, используя нерекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке
^ Построить гамильтонов цикл в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке
^ Построить гамильтонов цикл в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке.
^ Построить гамильтонову цепь в графе, используя нерекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в лексикографическом порядке ^ Построить гамильтонову цепь в графе, используя рекурсивный алгоритм генерации всех перестановок вершин в антилексикографическом порядке. Построить гамильтонов цикл в графе, используя алгоритм с возвратом. Построить гамильтонову цепь в графе, используя алгоритм с возвратом.
^ 1.4.Построение остова минимального веса
Граф G называется деревом, если он является связным и не имеет циклов.
Остовом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Остовное дерево связного нагруженного графа G с минимальной суммой длин содержащихся в нем ребер, будем называть остовом минимального веса или минимальным остовным деревом (МОД).
Рассмотрим граф G = (V,X), где V={v1,…,vn}.
^ Найти минимальный остов графа, используя алгоритм Краскала.
А л г о р и т м К р а с к а л а
Данные: матрица весов С(G) графа G.
Результат: матрица весов полученного остова, величина минимального остова.
Выберем в графе G ребро х минимального веса и построим граф G1, присоединяя к пустому графу Оn на множестве вершин V ребро х.
Если граф Gк уже построен и k < n-1, то строим граф Gк+1, присоединяя к графу Gк ребро y, имеющее минимальный вес среди ребер, не входящих в Gк и не составляющих циклов с ребрами из Gк.
В качестве иллюстрации рассмотрим нагруженный граф, изображенный на рис. 3а). На рис. 3б) представлено МОД данного графа (в скобках указан порядок присоединения ребер к МОД). Длина полученного МОД равна 10.
1 3 5 1 5
1 2 4 4 (1) (2) (4)
(3)
4 5 2 3 3 4 2 3
а) б)
Рис. 3
^ Найти минимальный остов графа, используя алгоритм Прима.
Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом этапе строится не просто ациклический граф, а дерево.
А л г о р и т м П р и м а
Данные: матрица весов С(G) графа G.
Результат: матрица весов полученного остова, величина минимального остова.
Выберем в графе G ребро х = v,w минимального веса и построим дерево G1 = (V1,X1), полагая V1 = {v,w}, X1 = {х}.
Если дерево Gк уже построено и k < n-1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Gк , выбираем ребро y минимального веса. Строим дерево Gк+1, присоединяя к Gк ребро y вместе с его не входящим в Gк концом.
^ 1.5.Поиск в графах
Существует много алгоритмов на графах, в основе которых лежит систематический перебор вершин графа, такой, что каждая вершина графа просматривается только один раз, и переход от одной вершины к другой осуществляется по ребрам графа. Остановимся на двух стандартных методах такого перебора: поиск в глубину и поиск в ширину.
Рассмотрим метод поиска в глубину в неориентированном графе G. Идея этого метода состоит в следующем. Начинаем поиск с некоторой фиксированной вершины v0, присвоим ей ПГ-номер: ПГ(v0)=1. Затем выбираем произвольную вершину w, смежную с v0, присваиваем ей ПГ-номер: ПГ(w)=2, и повторяем процесс уже от вершины w. Предположим, что в результате выполнения нескольких шагов этого процесса мы пришли в вершину v и пусть ПГ(v)=k. Далее действуем в зависимости от ситуации следующим образом:
если имеется новая, т.е. еще непросмотренная вершина u, смежная с v, то, присваивая ей ПГ-номер: ПГ(u)=k+1, продолжаем поиск, начиная с вершины u;
если же не существует ни одной новой, т.е. непросмотренной вершины u, смежной с v, то считаем, что вершина v просмотрена и возвращаемся в вершину, из которой мы попали в v, и продолжаем процесс поиска дальше.
Пример.
7 1 8
5 6 2 5
9
1 3 8
3 6
7 10
2 9 10
4 4
а) б)
Рис. 4
Поиск в глубину завершается, когда все вершины графа просмотрены. Если в результате работы алгоритма произошел возврат в начальную вершину v0, но при этом не все вершины графа просмотрены, то необходимо выбрать произвольную вершину из непросмотренных и продолжить процесс поиска от этой вершины. В результате проведенного поиска пройденные ребра графа образуют вместе с пройденными вершинами одно или несколько деревьев. Если приписать пройденным ребрам ориентацию в соответствии с тем направлением, в каком они проходятся при выполнении поиска, то получится совокупность корневых деревьев, корнями которых служат начальные вершины.
Для графа, представленного на рис. 4 а), описанным методом были получены два корневых дерева, изображенных на рис 4б).
Рассмотрим идею поиска в ширину в неориентированном графе. Другое название этого метода – волновой.
Начинается поиск с произвольной вершины v. Ей приписывается номер 0. Вершину v считаем просмотренной и помещаем в очередь. Далее проходим все ребра {v, w}, инцидентные вершине v и ориентируем их из v в w. Всем вершинам w приписываем номер 1, считаем их просмотренными и помещаем в очередь. После этих действий вершина v удаляется из очереди.
Далее выбираем вершину u, которая находится в начале очереди. Пусть ей приписан номер k. Пройдем все ребра, соединяющие вершину u с еще непросмотренными вершинами w. Всем вершинам w присвоим номер k+1, будем считать их просмотренными и поместим в очередь в порядке их просмотра. После этого вершину u удаляем из очереди. Заканчивается поиск в ширину тогда, когда все вершины графа будут просмотрены.
Пример.
7(2)
5(1) 6(2)
1(0) 3(1)
2(1) 4(1)
Рис. 5
На рис 5 в скобках указаны номера вершин графа, которые были ими получены в результате поиска в ширину.
Рассмотренная методика поиска в глубину и в ширину переносится и на ориентированные графы.
Рассмотренные методы поиска в глубину и в ширину могут быть применены для нахождения путей (маршрутов) в орграфах (графах), для выделения компонент связности (компонент сильной связности) графа (орграфа), а также для решения других задач теории графов.
^ Выделить компоненты сильной связности орграфа, используя алгоритм поиска в глубину (в орграфе поиск необходимо вести как в прямом, так и в обратном направлении). ^ Выделить компоненты сильной связности орграфа, используя алгоритм поиска в ширину (в орграфе поиск необходимо вести как в прямом, так и в обратном направлении). ^ Используя поиск в глубину найти компоненты связности в дополнении заданного графа. Используя поиск в ширину найти компоненты связности в дополнении заданного графа. Определить, верно ли, что для любой пары вершин заданного орграфа одна из этих вершин достижима от другой. Из графа удалить все вершины, от которых недостижима заданная. Вершина графа называется точкой сочленения, если ее удаление приводит к увеличению числа компонент связности. Найти все точки сочленения данного графа. Найти такую вершину заданного графа, которая принадлежит каждому пути между двумя выделенными (различными) вершинами и отлична от каждой из них.
еще рефераты
Еще работы по разное
Реферат по разное
Размышления об Эйлере, навеянные думами о прошлом, в свете проблемы устойчивости
18 Сентября 2013
Реферат по разное
Геологические исследования в области массивов Фишта и Оштена на Зап. Кавказе. Студ. Н. Морозова
18 Сентября 2013
Реферат по разное
Командиры полков разъезжались после встречи Нового года у командира дивизии. Последним уехал командир 332-го, майор Барабанов
18 Сентября 2013
Реферат по разное
Тема : Выполнение алгоритмов для исполнителя
18 Сентября 2013