Матрицы смежности - самый худший с алгоритмической точки зрения способ. Это матрицы nm в строках перечисляются вершины, в столбцах - ребра (см. таблицу и рис. 8.3).

Матрица смежности

	1-2	1-3	1-4	2-3	3-4
1	1	1	1	0	0
2	1	0	0	1	0
3	0	1	0	1	1
4	0	0	1	0	1

Рис. 8.3. Модельный граф

Этот способ требует nm ячеек памяти, причем большинство из ячеек заняты нулями. Ответ на элементарный вопрос: «к каким вершинам ведут ребра из x?», требует перебора всех столбцов, т.е. m шагов.

Матрица инциденций имеет размер nn. Если существует ребро (x-y), то в клетках с координатами (x, y) и (y, x) ставится 1.

Матрица инциденций графа G (рис. 8.3):

	1	2	3	4
1	0	1	1	1
2	1	0	1	0
3	1	1	0	1
4	1	0	1	0

Независимо от числа ребер требуется объем памяти nn, но за один шаг можно ответить на вопрос: «существует ли ребро из x в y?».

Также граф можно представить в виде списка пар, соответствующих ребрам:

Список ребер графа G (рис. 8.3)

1	1	1	2	3
2	3	4	3	4

Объем памяти равен 2m, но попробуйте ответить на вопрос: «к каким вершинам ведут ребра из вершины x?».

Наиболее удобным машинным представлением графа являются списки инцидентности.

Каждой вершине vV ставим в соответствие список вершин, соединенных ребрами с вершиной v. Для неориентированного графа каждое ребро (v-u) будет представлено дважды: в списке для v и в списке для u. Начало каждого списка будет храниться в одномерном массиве НАЧАЛО длины n. По вершине v находим НАЧАЛО[v] - в этой ячейке хранится указатель на начало списка вершин, соединенных с v. Каждый элемент такого списка - запись, состоящая из двух полей:

Вершина	Указатель на следующую запись		UZL	NEXT

Если вершина 1 соединена с 2 и 3, то ее список выглядит как на рис. 8.4.

Рис. 8.4. Список инцидентности

Весь список для вершины v будем называть ЗАПИСЬ[v]. Цикл, перебирающий все элементы этого списка, будем записывать «for uЗАПИСЬ[v]».

Число ячеек памяти, необходимое для представления графа списками инцидентности, имеет порядок O(n+m).

Создадим ЗАПИСЬ[1] для списков инцидентности (рис. 8.5) графа G (рис. 8.3).

Рис. 8.5. Список инцидентности к графу с рис. 8.3

Указатели на начало каждой цепи объединены в массив НАЧАЛО и инициализируются перед созданием цепи (рис. 8.6).



Рис. 8.6. Первый шаг создания списков

Записи для ребер, выходящих из узла (1), создаются динамически. Рассмотрим подробно этот механизм (рис. 8.7).

Рис. 8.7. Шаги 2-5 создания списков

Очевидно, что запись, подключенная первой, оказывается в конце цепи, а последняя - в начале. Таким образом, дисциплина обслуживания соответствует стеку. Вообще, набор стандартных подпрограмм для работы с динамическими списками включает в себя процедуру вталкивания в стек push, функцию выталкивания из стека pop и функцию выталкивания из очереди poptail. Опишем их во фрагменте 1.

ФРАГМЕНТ 1

Procedure Push(Var p: PT; k: integer); {p - указатель на начало стека; k - вталкиваемый элемент} var p1: PT; begin {push} new(p1); {новая пустая запись} p1^.uzl:= k; {заполнение ее данными} p1^.next:= p; {помещение ее перед верхушкой стека} p:= p1 {указатель начала указывает на новую запись} end; {push}
Function Pop(Var p: PT): integer; {для непустого стека} {p - указатель на начало стека} var p1: PT; begin {pop} pop:= p^.uzl; {вытолкнем верхушку стека} p1:= p; {укажем p1 на обреченную запись} p:= p^.next; {верхушка стека - следующая запись} dispose(p1) {освобождение памяти} end; {pop}
Function Poptail(Var p: PT): integer; {для непустой очереди} {p - указатель на начало очереди} begin {poptail} if p^.next = NIL then {в очереди ровно один элемент} poptail:=pop(p) else {будем сдвигать указатель вправо, пока не найдем последний элемент списка} poptail:=poptail(p^.next) {рекурсия} end; {poptail}

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

ФРАГМЕНТ 2

CONST N = 4; {вершины} M = 5; {ребра} TYPE PT = ^ZT; ZT = record uzl: integer; next: PT end; VAR {глобальные переменные} START: array [1..N] of PT; {списки инцидентности}	procedure Make_Lists; var edge,u,v: integer; begin {Make_Lists} for edge:= 1 to M do begin write (' Начало и конец', edge, 'ребра'); readln(u,v); push(START[u], v); push(START[v], u); end; end; {Make_Lists} {Списки формируются по принципу стека, т.к. порядок элементов внутри списка не важен.}

8.2 Поиск в глубину в графе

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

а) алгоритм решения легко «погружается» в этот метод;

б) каждое ребро графа анализируется число раз, ограниченное константой.

Опишем классический метод поиска в неориентированном графе - метод поиска в глубину (depth first search) (рис. 8.8).

Общая идея следующая. Начинаем поиск с некоторой фиксированной вершины k (корня). Затем выбираем одну из смежных (соединенных ребрами) с ней вершин. Назовем эту вершину u. Далее процесс поиска повторяется от u.

Пусть на каком-то этапе мы находимся в вершине v. Если среди ее соседей есть хотя бы одна новая (еще непросмотренная) вершина w, то просматриваем ее. После этого w перестает быть новой, и дальнейший поиск продолжаем с w.

Если же у вершины v нет ни одной новой «соседки», то говорим, что v использована, и возвращаемся на шаг назад - в вершину, из которой попали в v. Просмотренные, но еще не использованные вершины накапливаются в стеке. Использованные вершины удаляются из стека. Когда стек опустеет, то у связного графа будут просмотрены все вершины, у несвязного - компонента связности, содержащая вершину k.

Рис. 8.8. Поиск в глубину из вершины 1

Вопрос. Когда следует прервать работу алгоритма, если мы ищем путь от 1 до 5? Где находится путь?

Поиск в глубину можно записать с помощью рекурсивной процедуры GL.

Логический массив НОВЫЙ - глобальная переменная.

1 procedure GL(v) {поиск в глубину из вершины v}

2 begin

3 НОВЫЙ[v]:= ложь;

3 for u ЗАПИСЬ[v] do {перебор всех соседей v}

4 if НОВЫЙ[u] then GL[u]

5 end; {v использована}

Поиск в глубину в произвольном (необязательно связном) графе проводится согласно следующему алгоритму:

1 begin

2 for v V do НОВЫЙ[v]:= истина ; {инициализация}

3 for v V do {перебор всех вершин графа}

4 if НОВЫЙ[v] then GL(v)

5 end. {поиск окончен, все вершины просмотрены}

Покажем теперь, что этот алгоритм просматривает каждую вершину в точности один раз и сложность его порядка O(n+m).

Первый вызов GL(v) для некоторой вершины v влечет за собой просмотр всех вершин компоненты связности графа, содержащей v. Это обеспечивает цикл 3 процедуры GL: после просмотра v будет вызвана GL для всех ее новых соседей.

Каждая вершина просматривается ровно один раз - просматриваются только новые вершины, сразу после просмотра НОВЫЙ[v]:= ложь.

Гарантия того, что будут просмотрены все вершины - цикл 3 основного алгоритма.

Оценим теперь вычислительную сложность алгоритма.

Циклы 2 и 3 основного алгоритма содержат n шагов, не считая вызовы процедуры GL. Строка 2 процедуры GL для всех вызовов повлечет O(n) шагов. Полное число шагов цикла 3 процедуры GL для всех рекурсивных вызовов будет порядка m - числа всех ребер, так как от вершины к ее соседям мы двигаемся по ребрам.

Суммарная сложность алгоритма О(n+m).

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

Рекурсия устраняется стандартным способом: каждая просмотренная вершина помещается в СТЕК и удаляется из стека после использования.

1 procedure GL_1(v); {поиск в глубину,начиная с v}

2 begin

3 СТЕК:= NIL; СТЕК <= v; {v помещается в СТЕК}

4 НОВЫЙ[v]:= ложь;

5 while СТЕК do

6 begin

7 verh:= top(СТЕК); {читаем верхний элемент}

{будем искать первую новую «соседку» элемента verh}

8 if НАЧАЛО[verh]=nil then b:= ложь

9 else b:= NOT(НОВЫЙ[НАЧАЛО[verh]^.uzl]);

{НАЧАЛО[verh]^.uzl-номер первой вершины в списке ЗАПИСЬ[verh]}

10 while b do

11 begin

12 НАЧАЛО[verh]:= НАЧАЛО[verh]^.next;

{переводим указатель НАЧАЛО на следующую запись в

списке ЗАПИСЬ[verh]}

13 if НАЧАЛО[verh]=nil then b:= ложь

14 else b:= NOT(НОВЫЙ[НАЧАЛО[verh]^.uzl])

{проверяем, будет ли вершина следующей записи новой}

15 end;

16 if НАЧАЛО[verh]=nil then {найдена новая вершина!}

17 begin

18 verh:= НАЧАЛО[verh]^.uzl;

19 СТЕК <= verh; {новая вершина помещена в СТЕК}

20 НОВЫЙ[verh]:= ложь

21 end

22 else {вершина verh использована}

23 verh <= СТЕК {удалить verh из СТЕКа}

24 end {while СТЕК <> NIL}

25 end; {procedure GL1}

Корректность процедуры GL_1 доказывается аналогично GL.

Ответ. Когда 5 попадет в стек. В стеке.

8.3 Поиск в ширину в графе

При поиске в глубину просмотренные, но еще не использованные вершины скапливались в стеке. Чем позднее была просмотрена вершина, тем раньше ее удаляли из стека. Заменим стек очередью.

Механизм подключения элемента к началу очереди полностью совпадает с вталкиванием в стек (процедура push). Механизм выталкивания из очереди (функции poptail) - первым из очереди удаляется первый попавший туда элемент.

Основная идея поиска в ширину - у вершины v просматриваются и помещаются в очередь сразу все ее новые «соседи», после чего v становится использованной и удаляется из очереди (рис. 8.9).



Рис. 8.9. Поиск в ширину из вершины 1

Поиск в ширину можно использовать для нахождения кратчайшего пути между парой фиксированных вершин s и t. Под кратчайшим путем мы понимаем путь с минимальным количеством ребер, так как пока все ребра графа имеют одинаковую длину (можно считать, что все ребра имеют единичную длину). Поскольку мы находим сразу всех соседей, поиск, как волна от источника, равномерно распространяется во все стороны (рис. 8.10). Поэтому в очереди сначала находятся все вершины, удаленные от s на расстояние 1, через некоторое время - все вершины, удаленные на расстояние 2 и т.д. Понятно, что путь, найденный таким образом, будет кратчайшим.

Рис. 8.10. Распространение волны

Процедура поиска в ширину WD:

1 procedure WD(v);

{поиск в ширину с началом в вершине v}

2 begin

3 ОЧЕРЕДЬ:= NIL; ОЧЕРЕДЬ <= v; НОВЫЙ[v]:= ложь;

{v помещается в очередь}

4 while ОЧЕРЕДЬ<>NIL do

5 begin

6 tail <= ОЧЕРЕДЬ;

{выталкивание из очереди нижнего элемента}

7 for u ЗАПИСЬ[tail] do

{ищем всех новых соседей узла tail}

8 if НОВЫЙ[u] then

9 begin

10 ОЧЕРЕДЬ <= u; НОВЫЙ[u]:= ложь

11 end

12 end {while ОЧЕРЕДЬ <>NIL}

13 end;

Как и для поиска в глубину, легко показать, что каждая вершина просматривается ровно один раз и вычислительная сложность равна O(n+m).

Чтобы найти кратчайший путь, нужно немного модифицировать процедуру WD. Во-первых, добавить одномерный массив ПРЕД по числу вершин графа. Пусть во время работы процедуры в вершину u₂ мы попали из u₁: u₁ была предыдущей для u₂, поэтому ПРЕД[u₂]:= u₁. Во-вторых, чтобы массив ПРЕД заполнялся именно так, изменим строку 10 процедуры WD:

9 begin

10 ОЧЕРЕДЬ <= u; НОВЫЙ[u]:= ложь;

ПРЕД[u]:= tail;

Итак, чтобы найти кратчайший путь из s в t, вызовем модифицированную WD(s).

Как только конец пути t попадет в очередь, поиск следует прекратить. Каким образом восстановить путь от s до t из массива ПРЕД?

Рассмотрим последовательность вершин, где u₁ = ПРЕД[u₂]. В t мы попадем из u, в u из v и т.д., пока не встретим s. Эта последовательность - путь из s в t. Первоначальная инициализация массива ПРЕД: ПРЕД[u]:= u.

Вопрос. Как будет заполнен массив ПРЕД при поиске в ширину на рис. 8.9 в момент помещения в очередь вершины 5?

Метод поиска в ширину применим для определения связных компонент графа. Вызвав WD(s), просмотрим все вершины u, для которых существует путь из s в u.

Ответ. ПРЕД[1] = 1; ПРЕД[2] = ПРЕД[3] = 1;

ПРЕД[4] = 3; ПРЕД[5] = 2.

8.4 Каркасы графа

Каждый связный граф имеет каркас. Более того, у одного графа может быть несколько разных каркасов. Дадим теперь определение каркаса.

Для произвольного связного графа G=<V, E> любое дерево D=<V, T>, где T Е будет его каркасом (рис. 8.11).

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

Другими словами, каркас D соединяет все вершины графа G так, чтобы не было циклов.



Рис. 8.11. Каркас графа

Ребра каркаса будут называться ветвями, ребра, не вошедшие в каркас, хордами.

Вопрос. Перечислите хорды графа G относительно каркаса D на рис. 8.11.

Каркасы можно строить как поиском в глубину, так и поиском в ширину (рис. 8.12). В обоих случаях достижение новой вершины u из старой v означает включение в каркас ветви (v-u).

АЛГОРИТМ {Нахождение каркаса связного графа методом поиска в глубину}

Данные: Связный граф G=<V, E>, заданный списками инцидентности ЗАПИСЬ[v], v V.

Результаты: Каркас D=<V, T> графа.

Переменные НОВЫЙ, ЗАПИСЬ, Т - глобальные.

1 procedure GLD(v);

2 begin

3 НОВЫЙ[v]:= ложь;

4 for u ЗАПИСЬ[v] do

5 if НОВЫЙ[u] then {нашли новую ветвь (v-u)}

6 begin

7 T:= T(v-u); {и присоединили ее к каркасу}

9 GLD(u)

10 end

11 end;

1 begin {основная программа}

2 for u V do НОВЫЙ[u]:= истина; {инициализация}

3 T:= 0; {T-множество найденных ветвей}

4 GLD(k) {корень k - произвольная вершина}

5 end.

Докажем корректность этого алгоритма.

Алгоритм строит связный граф, так как каждое новое ребро (v-u) продолжает уже существующий путь от k к v.

Построенный граф не содержит циклов. Каждая новая ветвь (v-u) соединяет уже рассмотренную v с новой u. Чтобы замкнуть цикл, требуется ребро, соединяющее две уже рассмотренные вершины.

Построенный граф содержит все вершины графа G - это свойство поиска в глубину. По этой же причине вычислительная сложность алгоритма О(n+m).

Любой каркас обладает важным свойством - от корня k до произвольной вершины v существует единственный путь, состоящий из ветвей каркаса. Если бы их было два, получился бы цикл, если бы ни одного, каркас не был бы связным.

Кроме того, если каркас D построен поиском в глубину, то для двух вершин u и v, соединенных ребром e E, всегда можно сказать: или v - потомок u, или u - потомок v (относительно каркаса D).

Первое означает, что u лежит на пути из корня k в вершину v, второе - v на пути из k в u. Это легко доказать.

Пусть одна из вершин, например, v, просмотрена раньше u. Построен путь от корня k до v. Процесс поиска в глубину начинается с вершины v. Так как u и v соединены ребром, то рано или поздно будет рассмотрена вершина u и построен путь от v до u. Получился путь k-v-u.

Если v и u соединены ветвью каркаса, то одна из них - сын, другая - отец.

АЛГОРИТМ {Каркас связного графа поиском в ширину}

Данные: связный граф G=<V, E>, представленный списками ЗАПИСЬ[v], v V.

Результаты: каркас D=<V, T> графа G.

1 begin

2 for u V do НОВЫЙ[u]:= истина;{инициализация}

3 T:= 0 {T - множество найденных ветвей}

4 ОЧЕРЕДЬ:= NIL;

5 ОЧЕРЕДЬ <= k; {поместили в очередь корень k}

6 НОВЫЙ[k]:=ложь; {пометили k как просмотренный}

7 while ОЧЕРЕДЬ <> NIL do

8 begin tail <= ОЧЕРЕДЬ;

8 for u ЗАПИСЬ[tail] do

9 if НОВЫЙ[u] then {нашли новую ветвь v-u}

10 begin

11 ОЧЕРЕДЬ <= u; НОВЫЙ[u]:=ложь;

12 T:=T(v-u) {и присоединили ее к каркасу}

13 end

14 end

15 end.

Легко доказать, что этот алгоритм строит каркас произвольного графа за О(n+m) шагов.



Рис. 8.12. Два каркаса графа G

Если каркас D графа G построен поиском в ширину, то путь от корня k до произвольной вершины v будет не только единственным, но и кратчайшим. Это следует из свойств поиска в ширину.

Ответ. {(2-3), (3-4), (5-6), (6-1), (2-5), (1-4)}.

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

Предположим, нам нужно с помощью закона Кирхгофа составить систему линейных уравнений для электрической цепи. Цепь имеет сложную структуру и содержит большое количество циклов. Запишем закон Кирхгофа для каждого цикла и начнем решать полученную систему уравнений. Сразу обнаружится, что часть уравнений являются линейно зависимыми, т.е. получаются из других. Значит, какие-то циклы были не нужны?!

В этой главе будет доказано, что любой цикл графа можно однозначно разложить по фундаментальным циклам этого графа так же, как любой вектор трехмерного пространства однозначно представляется линейной комбинацией базисных векторов i, j, k. Так же будет показано, как построить для данного графа это фундаментальное множество.

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

Вначале для произвольных множеств А и В введем операцию взятия симметрической разности (рис. 8.13, 8.14).



Рис. 8.13. Симметрическая разность двух множеств

Построим симметрическую разность трех множеств. Выберем порядок действий, соответствующий следующей расстановке скобок: (A B) C.

Рис. 8.14. Симметрическая разность трех множеств

В силу симметрии при любой расстановке скобок будет получаться то же множество A B C. Можно установить закономерность: в симметрическую разность входят элементы, содержащиеся одновременно либо в одном, либо в трех множествах, а принадлежащие двум,- удаляются. Обобщим этот результат на произвольное число множеств.

Утверждение 1

Симметрическая разность множеств А₁, А₂, …, А_k содержит в точности те элементы, которые принадлежат нечетному числу множеств.

Доказать это можно индукцией по числу множеств.

Вернемся к фундаментальным циклам. Это множество определяется через каркас графа.

Пусть уже построен каркас D=<V, T> графа G=<V, E>. Если к каркасу добавить произвольную хорду e (E-T), то получившийся граф (D e) будет содержать ровно один цикл. Назовем этот цикл С_е (рис. 8.15). Добавляя к каркасу поочередно все хорды, получим фундаментальное множество циклов Ф относительно каркаса D Ф = {C_е : e (E-T)}.

Вопрос 1. Укажите фундаментальное множество циклов графа G относительно каркаса D на рис. 8.15.

Симметрическая разность любого числа циклов графа G является циклом графа G.

Вопрос 2. В графе G (см. рис. 8.15) найти C₁ C₂, если C₁=(1-2-3), C₂=(2-3-4).

Рис. 8.15. Ф-цикл

Сформулируем без доказательства следующее утверждение.

Утверждение 2

Произвольный цикл C графа G можно однозначно представить как симметрическую разность некоторого числа фундаментальных циклов.

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

Как уже говорилось, знание фундаментальных циклов имеет существенное значение при анализе электрических цепей. Для каждого фундаментального цикла данной цепи можно записать закон Кирхгофа: сумма падений напряжений вдоль цикла равна 0. Все эти уравнения независимы, уравнения для остальных циклов будут следовать из них.

Опишем простой алгоритм построения фундаментальных циклов. Он основан на поиске в глубину из произвольного корня k и является рекурсивным. Каждая встреченная новая вершина v помещается в СТЕК и получает номер GLN[v] (порядок просмотра) и удаляется из него после использования. Поэтому СТЕК всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v до корня k.

Анализируемое алгоритмом ребро (v-u) будет замыкать цикл, если (v-u) - хорда.

Критерий хорды следующий:

(v-u) будет хордой, если u - найденная соседка v - уже встречалась раньше при поиске в глубину. В этом случае она находится в СТЕКе и ее номер GLN(u) меньше соответствующего номера GLN(v). Но это еще не все. Если из u мы попали в вершину v, т. е. u является отцом v, то GLN(u) < GLN(v), но (v-u) не хорда, а ветвь каркаса. Эту ситуацию легко распознать, так как в этом случае вершины u и v стоят в СТЕКе рядом.

Если же GLN(u) < GLN(v) и u не является отцом v, то (v-u) - хорда и цикл состоит из верхней группы элементов стека, начиная с v и кончая u (рис. 8.16).

Рис. 8.16. Стек, содержащий фундаментальный цикл

Мы заранее знаем, что наибольшее число вершин, одновременно находящихся в стеке, не превышает n - длины пути от корня до самой удаленной вершины, поэтому стек можно имитировать массивом переменной длины (длина его будет колебаться от 0 до n). Текущее значение длины будет храниться в переменной d, вталкивание в стек вершины v будет изображаться: СТЕК[d]:= v, выталкивание верхушки СТЕКА: d:= d-1.

АЛГОРИТМ {Нахождение множества Ф-циклов графа}

Данные: Граф G=<V, E>, представленный списками ЗАПИСЬ[v], v V.

Результаты: Множество фундаментальных циклов Ф графа G.

Переменные: d, num, СТЕК, ЗАПИСЬ, GLN - глобальные.

1 procedure CYCLE(v);

{находит фундаментальное множество циклов для компоненты связности графа, содержащей вершину v}

2 begin

3 d:= d+1; СТЕК[d]:= v;

4 num:= num+1; GLN[v]:= num;

5 for u ЗАПИСЬ[v] do

6 if GLN[u]=0 then

7 CYCLE(u) {для новой вершины u}

8 else if (u<>СТЕК[d-1]) AND (GLN[u]<GLN[v]) then

9 печать СТЕК[d],СТЕК[d-1],..,СТЕК[c]=u;

{ребро (v-u) замкнуло новый цикл}

10 d:= d-1; {использованная v удаляется из стека}

11 end;

1 begin {основная программа}

2 for v Є V do GLN[v]:= 0;

3 num:= 0; {инициализация перед началом нумерации}

3 d:= 0; СТЕК[d]:= 0; {d - число элементов в стеке}

4 for v V do

5 if GLN[v]=0 then CYCLE(v)

6 end.

Оценим вычислительную сложность алгоритма.

Если отбросить число шагов, требующих выписывания всех фундаментальных циклов (строки 8-9), сложность имеет порядок О(n+m), как у всех алгоритмов, основанных на поиске в глубину.

Число шагов, потраченное на печать всех фундаментальных циклов, пропорционально суммарной длине всех циклов. Количество фундаментальных циклов = число всех хорд = m - (n - 1) = m - n +1. Длина любого цикла не превосходит n. Таким образом, суммарная длина всех циклов не превосходит n(m - n + 1) mn + n. Если отбросить случай, когда число ребер m=0, то сложность равна О(mn).

Ответ 1. Ф = {C₁=(1-2-3), C₂=(2-3-4)}.

Ответ 2. С₁ С₂=(1-2-3-4).

8.6 Нахождение компонент двусвязности (блоков) графа

Если в связном графе найдутся две вершины u₁ и u₂ такие, что любой путь между ними будет проходить через вершину v, то вершина v будет называться точкой сочленения.

Можно дать эквивалентное определение точки сочленения.

Вершина v графа G=<V, E> называется точкой сочленения, если удаление этой вершины и всех выходящих из нее ребер, ведет к увеличению компонент связности графа.

Если в связном (состоящем из одной компоненты связности) графе нет точек сочленения, он - двусвязный.

Любой максимальный двусвязный подграф графа G называется компонентой двусвязности или блоком этого графа (рис. 8.17).



Рис. 8.17. Блоки графа G

Вопрос 1. Что будет являться пересечением двух различных блоков графа?

Вопрос 2. Что произойдет с блоком, если к нему присоединить ребро графа, имеющего с блоком общую точку и не принадлежащего блоку?

Двусвязность графа - очень полезное свойство для некоторых прикладных задач.

Представим себе, что вершины графа - телеграфные станции; ребра - линии передач. Пусть одна из станций вышла из строя. Если граф двусвязный, то между любыми двумя оставшимися станциями сохранится связь.

Для многих задач важно знать блоки графа. Например, находить все элементарные циклы графа G можно отдельно для каждого блока графа G.

Нахождение точек сочленения и блоков графа - классическая задача. Будем искать точки сочленения, обходя все вершины графа методом поиска в глубину. Будем не только обходить вершины графа, но и строить его каркас.

При построении каркаса поиском в глубину для двух вершин u и v, связанных ребром, всегда точно известно: или u - потомок v, или наоборот. Как распознать точку сочленения s, если уже построен каркас D графа G?

Вот критерий точки сочленения:

- или это корень, имеющий не менее двух сыновей в D;

- или у вершины s есть хотя бы один сын u такой, что ни он, ни его потомки не связаны хордами с предками s.

Рассмотрим рис. 8.18. Номера вершин - номера, которые получают вершины графа во время построения каркаса. Покажем, что вершина s удовлетворяет второму условию критерия.

По построению каркаса s имеет сына 3 и потомка 4. Предок s - вершина k. Сын 3 и его потомок 4 не связаны хордами с k. Итак, s - точка сочленения и граф G имеет первый блок = {s-3, 3-4, s-4}.

Рис. 8.18. Точки сочленения

Вопрос 3. С какой вершиной нужно соединить вершину 4, чтобы граф G стал двусвязным?

Вершина k - точка сочленения, так как она корень, имеющая двух сыновей: s и 5. Поэтому граф G имеет второй блок = {k-s} и третий блок = {k-5}.

Зная критерий точки сочленения, опишем алгоритм нахождения этих точек.

Пусть алгоритм поиска в глубину строит каркас D графа G. Для каждой вершины v будем вычислять два значения: GLN[v] и MIN[v].

GLN[v] - просто номер, который получает вершина при построении каркаса. Например, для корня GLN[k]=1.

Пусть вершина v соединена хордами (вспомните, что такое хорды для каркаса D) c какими-то вершинами X₁, …, X_k. Выберем минимальный из номеров этих вершин:

X[v] = min {GLN[X₁], …, GLN[X_k]}.

Вопрос 4. Какие вершины графа на рис. 8.18 соединены хордами с вершиной s?

Пусть w - любой потомок вершины v. Он также может быть связан хордами с какими-то вершинами Y₁, …, Y_р.

Подсчитаем Y[w] = min {GLN [Y₁], …, GLN [Y_р]}.

И, наконец, подсчитаем Y[w] для каждого w - потомка v и выберем из них минимальный.

Y[v] = min {Y[w], w - любой потомок v}

Минимальный из трех номеров {GLN[v], X[v], Y[v]} назовем MIN[v]:

MIN [v]= min {GLN[v], X[v], Y[v]}.

MIN[v] легко вычислить по индукции.

Пусть для всех сыновей U₁, …, U_k вершины v MIN[U₁], …, MIN[U_k] уже вычислены.

Тогда MIN[v] = min {GLN[v], X[v], MIN[u]},

где MIN[u]= min {MIN[U₁], …, MIN[U_k]}.

Вспомним критерий точки сочленения. Это либо корень с двумя сыновьями, либо предки этой точки и потомки хотя бы одного сына не соединены хордами.

Запишем этот критерий через GLN и MIN.

МIN[u] - минимальный из номеров вершин, с которыми соединен сын u и его потомки. Если среди этих вершин не будет предков v, то критерий выполнится. Номера предков строго меньше GLN[v], поэтому MIN[u] GLN [v] для некоторого сына u вершины v.

Вопрос 5. Вычислите MIN[3] для сына 3 вершины s. Выполнится ли для s критерий?

АЛГОРИТМ {Нахождение компонент двусвязности графа}

анные: Граф G=<V, Е> без изолированных вершин, представленный списками инцидентности ЗАПИСЬ[v], v V.

Результаты: Множество ребер всех компонент двусвязности. Переменные MIN, GLN, CTEK, num - глобальные.

1 procedure BLOC(v,p);

{Поиск в глубину, начиная с v.

В стек записывают ся ребра блоков, p - отец v}

2 begin

3 num:= num+1; GLN[v]:= num; {нумеруем v}

4 MIN[v]:= GLN[v];

5 for u Є ЗАПИСЬ[v] do

6 if GLN[u]=0 then {u - новая, (v-u) - ветвь}

7 begin

8 СТЕК <= (v-u);{Ветвь поместили в стек, поиск продолжается с u}

9 BLOC(u, v) {у u не осталось новых соседей, был подсчитан MIN[u]. Пора пересчитать MIN[v] и проверить критерий}

10 MIN[v]:= min(MIN[v], MIN[u]);

11 if MIN[u]>=GLN[v] then

{v - точка сочленения. Ребра, занесенные в стек последними до (v-u) включительно - блок, связывающий u всех его потомков}

12 begin {печать ребер блока}

13 repeat

14 e <= СТЕК;

15 write(e);

16 until e=(v-u);

17 write(;) {знак конца блока}

18 end

19 end {if GLN[u]=0}

20 else {u - не новая}

21 if (u<>p) and (GLN[u]<GLN[v]) then

22 begin {условие хорды}

23 СТЕК <= (v-u);{v соединена хордой с u,

пересчитаем MIN[v]}

24 MIN[v]:= min(MIN[v], GLN[u])

25 end

26 end;

1 begin {основная программа}

2 for v V do

3 begin

4 GLN[v]:= 0; MIN[v]:= n

5 end;

6 СТЕК:= NIL; num:= 0;

7 BLOC(k,0);

8 end.

Алгоритм составлен. Осталось доказать его корректность.

Покажем, что вызов BLOC(v, 0) для любой вершины v графа приведет к печати всех блоков этого графа.

1. Если граф двусвязный, то он состоит из одного блока и не имеет точек сочленения. В строке 8 в стек будут заноситься все ветви каркаса, в строке 23 - хорды. Точек сочленения нет, поэтому критерий 11 выполнится первый раз для корня. К корню мы вернемся, рассмотрев все вершины и заслав в стек все ребра.

2. Пусть граф содержит i (i>1) блоков, а алгоритм исправно работает для любого графа, содержащего блоков не более i-1.

Начинаем поиск в глубину и на каком-то шаге первый раз встретим ребро (v-u) такое, что MIN[u] GLN[v] (критерий). Вершина v - корень или точка сочленения, u - сын вершины v. Так как проверка критерия выполнилась первый раз, то все потомки u рассмотрены и точек сочленения среди них нет. Следовательно, верхняя часть стека вплоть до ребра (v-u) - первый блок. Удалим этот блок, оставив только вершину v.

Запустим алгоритм для оставшегося графа. Единственным изменением в его работе будет следующее: когда v будет просмотрена первый раз, цикл 5 не будет перебирать вершины из удаленного блока.

В графе осталось i-1 блоков, и по индуктивному предположению они будут найдены, а доказательство - окончено.

Оценим вычислительную сложность алгоритма.

Цикл 2 требует для n вершин О(n) шагов. Вызов BLOC(v, 0) повлечет О(n+m) шагов, где n и m - число вершин и ребер, так как столько требует поиск в глубину. Каждое ребро в цикле 13 удаляется из стека и выводится на печать ровно один раз, т.е. не более О(m) шагов. Сумма всех этих слагаемых не превосходит О(n+m) шагов.

Ответ 1. Точка сочленения или ничего.

Ответ 2. Максимальность блока означает, что, присоединяя к нему любой подграф, мы автоматически присоединяем точку сочленения.

Ответ 3. С вершиной 5.

Ответ 4. Вершина 4.

Ответ 5. MIN[3]=2, так как потомок 3 вершина 4 связана хордой с s, а GLN[s]=2. GLN[s]=MIN[3] и критерий выполнен.

8.7 Эйлеровы пути

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

Если путь заканчивается в начальной вершине, то он называется эйлеровым циклом (рис. 8.19).

Рис. 8.19. Эйлеров цикл, эйлеров путь

адача существования эйлерова пути в заданном графе была решена великим русским математиком Леонардом Эйлером в 1736 году.

редставленное им необходимое и достаточное условие существования такого пути считается первой в истории математики теоремой теории графов.

ТЕОРЕМА

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

аметим, что число вершин нечетной степени в любом графе всегда четно. Это легко доказать.

росуммируем степени всех вершин графа. Эта сумма равна 2m - удвоенному числу ребер, так как каждое ребро соединяет две вершины. Вклад в эту сумму вершин четной степени - четен, поэтому вклад вершин нечетной степени тоже должен быть четен. Для этого их должно быть четное количество (нечетное число ребер четное число вершин = четный результат).

овая формулировка теоремы:

Эйлеров путь в связном графе существует тогда и только тогда, если число вершин нечетной степени равно 0 или 2.

окажем достаточность.

сли эйлеров путь существует, то нечетную степень имеют ровно две вершины - начало и конец. Если это цикл, то таких вершин - 0.

дальнейшем будем рассматривать только эйлеровы циклы u, соответственно, графы без вершин нечетной степени. Если граф имеет 2 нечетных вершины, то добавим еще одну вершину и соединим ее ребрами с нечетными (см. рис. 8.19). Нечетные вершины станут четными, эйлеров путь замкнется в цикл.

оэтому достаточное условие сформулируем только для циклов:

Если в связном графе нет вершин нечетной степени, в нем существует эйлеров цикл.

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

Вопрос. Существует ли эйлеров цикл в данном графе, изображенном на рис. 8.20?

Рис. 8.20. Модельный граф для вопроса

ЛГОРИТМ. {Нахождение эйлерова цикла}

анные: Связный граф G=<V, E> без вершин нечетной степени, представленный списками инцидентности ЗАПИСЬ[v], v V.

езультаты: Эйлеров цикл, хранящийся в стеке EC.

1 begin

2 СТЕК:= NIL; EC:= NIL;

3 k:= произвольная вершина G;

4 СТЕК <= k; {поместим k в СТЕК}

5 while СТЕК<>NIL do

6 begin

7 v:= top(CTEK); {верхний элемент СТЕКА}

8 if ЗАПИСЬ[v]<>0 then {ищем ребро, выходящее из v}

9 begin

10 u:= первая вершина списка ЗАПИСЬ[v];

11 СТЕК <= u; {поместим u в СТЕК}

12 ЗАПИСЬ[v]:= ЗАПИСЬ[v]-[u];

13 ЗАПИСЬ[u]:= ЗАПИСЬ[u]-[v]; {удаляем ребро (v-u) из графа G}

14 end {возврат на 5, u - верхнии элемент}

15 else {из v не выходит ни одно ребро, путь нельзя удлинить}

16 begin

17 v <= СТЕК; ЕС <= v {v выталкивается из СТЕКА и помещается в ЕС}

18 end

19 end {пока СТЕК не пуст}

20 end.

усть k - вершина, выбранная в 3.

икл 5 начинает строить путь с началом в k, вершины этого пути помещаются в стек, ребра удаляются из графа. Это продолжается до тех пор, пока не выполнится ЗАПИСЬ[v]= 0 в 15.

то означает, что путь нельзя удлинить, он кончился на v. На самом деле v = k, так как иначе степень v была бы нечетной - зашли в v, но не вышли. Таким образом, мы вышли из k и вернулись в k т.е. описали цикл. Его вершины находятся в стеке, ребра удалены из графа. Вершина k переносится из стека в ЕС, а очередной вершиной v становится верхний элемент стека.

роцесс повторяется, в стек помещается некоторый цикл, проходящий через v, сама v переноситься в ЕС. По окончании работы стек пуст, ЕС содержит эйлеров цикл.

а рис. 8.21 изображен «модельный» граф, на котором удобно продемонстрировать работу алгоритма. Направления стрелок указывают, в какой последовательности ребра графа G попадают в стек ЕС.



Рис. 8.21. Трассировка алгоритма

начале в стек помещается цикл 1 (V₀-V₁-V₂-V₃-V₄-V₀), он удаляется из графа, V₀ заносится в ЕС.

атем из стека удаляется верхний элемент V₄. Все проходящие через него ребра удалены из графа, V₄ переносится в ЕС.

атем в стек помещается цикл 3, V₃ из СТЕКА переносится в ЕС.

атем из стека в ЕС переносятся все элементы цикла 3, так как проходящие через них ребра удалены. Следующий верхний элемент - V₂ и т.д.

ценим вычислительную сложность алгоритма.

лавный цикл 5 работает, пока стек не пуст. Каждое ребро графа один раз записывается в стек и один раз переносится в ЕС. Число итераций цикла 5 - О(m). Покажем, что число шагов внутри каждой итерации ограничено константой. Одна итерация или записывает ребро в стек, удаляя его из графа, или переносит в ЕС. Списки инцидентности ЗАПИСЬ[v] реализованы так, что для вершин u-v, соединенных ребром, вершина u в списке ЗАПИСЬ[v] содержит указатель на вершину v в списке ЗАПИСЬ[u] и наоборот. Это позволяет удалить ребро (v-u) за время, ограниченное константой. Построенный алгоритм является оптимальным, так как только выписывание эйлерова цикла потребует О(m) шагов.

Ответ. Вначале обходим стороны пятиугольника, образуя цикл, затем «одним росчерком пера» пробегаем звездочку.

9. Классификация задач по степени сложности

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

В этом графе существует гамильтонов цикл		В этом графе гамильтонова цикла нет

Рис. 9.1. Задача Гамильтона

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

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

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

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

сли же мы не располагаем ни явной формулой, ни рекурсивным выражением приемлемой сложности, нам остается только два способа:

построение эффективного алгоритма;

метод перебора всех возможностей.

ложность задачи - сложность наилучшего алгоритма, известного для ее решения.

ложность алгоритма - число шагов, необходимых для решения наихудшего из всех возможных случаев, допускающих применение алгоритма.

то число выражается как функция от размерности входных данных задачи - например, числа вершин графа.

разу возникает вопрос - если сложность задачи зависит от нашего знания «хороших» алгоритмов, до какого предела можно улучшать данный алгоритм?

уществуют ли методы перевода задачи из класса «сложных» в класс «простых»?

РИ КЛАССА ЗАДАЧ

амыми лучшими являются линейные алгоритмы порядка O(n), где n - размерность входных данных, например алгоритм поиска эйлеровых циклов в графе. ругие «хорошие» алгоритмы имеют сложность, представляющую собой многочлен заданной степени, не зависящей от входных данных: О(nm), O(n²), O(n³) и т.д. Задачи, решаемые алгоритмами полиномиальной вычислительной сложности, относятся к классу Р полиномиальных алгоритмов.

сть задачи, которые по своей природе имеют экспоненциальную сложность порядка Aⁿ, где A - константа или полином от n. то задачи, в которых требуется построить все подмножества данного множества, все клики (полные подграфы) данного графа и т.д. Число ответов в этих задачах уже само по себе экспоненциально, поэтому только их перечисление потребует экспоненциальное число шагов. Это класс Е экспоненциальных алгоритмов.

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

от неполный список таких задач. (В приложении содержатся точные математические постановки 32 различных задач.)

ь Решение систем уравнений в целых числах.

ь Определение гамильтонова цикла.

ь Составление расписаний и раскрасок.

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

ь Оптимизация пути коммивояжера через сеть городов.

ь Отбор файлов при запросе в информационный банк данных для получения информации с наименьшей стоимостью.

ь Размещение обслуживающих центров для максимального числа клиентов при минимальном числе центров.

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

ь Диагностика (болезни, поломки).

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

ь упорядочение операций;

ь размещение персонала;

ь оптимизация перевозок;

ь управление производством;

ь проектирование в области электроники.

олее того, для большинства этих задач (так называемых NP-полных задач) была доказана эквивалентность - если для одной из них удастся найти полиномиальный алгоритм, автоматически будут решены все остальные.

азовем его классом NP недетерминированных полиномиальных алгоритмов. сожалению, детальное обсуждение этих задач выходит за рамки данной главы, но при практическом изучении подобных задач нужно помнить следующее:

1. Для небольших n экспоненциальный алгоритм часто более эффективен, чем полиномиальный.

2. Для реальных задач большой размерности следует разработать приближенный полиномиальный алгоритм.

9.1 Алгоритмы с возвратом

ернемся к задаче существования гамильтонова пути - пути, проходящего через каждую вершину графа только один раз. В предыдущей главе было упомянуто, что для такой задачи не построен полиномиальный алгоритм. Попробуем произвести полный перебор всех возможных путей. N вершин графа можно расположить в n! различных цепочек. Чтобы проверить для каждой цепочки, реализована ли она как гамильтонов путь на графе, необходимо еще n шагов, итого сложность полного перебора nn! шагов.

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

БЩАЯ СХЕМА АЛГОРИТМА С ВОЗВРАТОМ

усть решение, которое мы ищем, имеет вид последовательности <X(1), …, X(n)>.

удем строить его, начиная с пустой последовательности длины 0.

усть на каком-то этапе уже построено частичное (неполное) решение длины i: < X(1), …, X(i) >.

опытаемся продолжить это решение еще на один шаг. Для этого нужно отыскать допустимое X(i+1). X(i+1) считается допустимым, если или < X(1), …, X(i+1) > уже является решением, или относительно < X(1), …, X(i+1) > нельзя сразу сказать, что его невозможно расширить до полного решения.

альше существует две возможности:

- если X(i+1) допустимо, то следующее допустимое X ищется для частичного решения <X(1), …, X(i+1)> (заметим, что допустимость X(i+1) вовсе не означает, что <X(1), …, X(i+1)> можно расширить до полного решения);

- если допустимого X(i+1) не существует, то возвращаемся на шаг назад - к частичному решению < X(1), …, X(i-1) > и для него отыскиваем другое X'[i], не совпадающее с предыдущим X(i).

олее точно, пусть для каждого i>0 существует множество A(i), из которого будут выбираться X(i) - претенденты на i-ю координату частичного решения.

чевидно, множества A(i) должны содержать все X(i), занимающие i-ю координату любого решения. Кроме того, A(i) всегда будут содержать какие-то лишние элементы, не содержащие в i-й координате ни одного решения.

еперь общая схема алгоритма с возвратом имеет следующий вид:

1 begin

2 k:= 1;

3 while k>0 do

4 if существует еще новый y A(k), являющийся допустимым then

5 begin

6 X[k]:= y; {y использован}

7 if <X[1],…,X[k]> является решением then write (<X[1],…,X[k]>);

8 k:= k+1

9 end

10 else {возврат на предыдущее частичное решение, все элементы A(k) становятся неиспользоваными}

11 k:= k-1

12 end.

сли предположить, что все решения имеют длину, меньшую n+1, и все множества A(k) состоят из конечного числа элементов, то этот алгоритм находит все решения.

от же самый алгоритм можно очень просто записать с помощью рекурсии.

{рекурсивный вариант алгоритма с возвратом}

1 procedure BC(k);

{генерируем все решения, являющиеся продолжением частичного решения <X[1],…,X[k-1]>, массив Х-

глобальный}

2 begin

3 for y A(k) do

4 if y допустим then

5 begin

6 X[k]:= y;

7 if <X[1],…,X[k]> - решение then

8 write(<X[1],…,X[k]>);

9 BC(k+1);

{генерируем все решения, являющиеся продолжением частичного решения <X[1],…,X[k-1],y>}

10 y неиспользован;{возврат на <X[1],…,X[k-1]>}

11 end {цикл 3 выберет для продолжения

<X[1],…,X[k-1]> следующий y'y}

12 end;

Вопрос 1. Каким образом частичное решение <X(1), …, X(k)> будет продолжено внутри BC(k+1)?

Сгенерировать все решения можно вызовом ВС(1) из главной программы. Описание алгоритма возврата мы начали с несколько более сложного нерекурсивного варианта, так как в рекурсивном варианте «возврат» является частью механизма рекурсии и не появляется в явном виде.

АДАЧА ГАМИЛЬТОНА

рименим теперь алгоритм с возвратом для поиска всех гамильтоновых циклов в графе G=<V,E>. Каждый такой цикл - последовательность различных вершин графа <X(1), …, X(n+1)> и только X(1) = X(n+1) = k, где k - произвольная фиксированная вершина, соседние вершины X(i) и X(i+1) соединены ребром.

огда A(i) = V (множество всех вершин) для любого i n+1;

Условие допустимости y для продолжения <X(1), …, X(i-1)>:

1. y ЗАПИСЬ[X(i-1)] (вершина y соединена ребром с X(i-1));

2. y новая, то есть не принадлежит <X(1), …, X(i-1)>.

ЛГОРИТМ {Нахождение всех гамильтоновых циклов в графе}

анные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], v V.

езультаты: Печать всех гамильтоновых циклов графа G.

еременные ЗАПИСЬ, X, DOP - глобальные.

1 procedure GAMI(i);

{генерация всех гамильтовых циклов, являющихся продолжением частичного решения <X[1],…,X[i-1]>}

2 begin

3 for y Є ЗАПИСЬ[X[i-1]] do

4 if (i=n+1) AND (y=k) then

5 write(X[1],…,X[n],k)

6 else if DOP[y] then

7 begin

8 X[i]:= y; DOP[y]:= ложь;

9 GAMI(i+1);

10 DOP[y]:= истина;

{все решения, продолжающие <X[1],…,X[i-1],y> уже сгенерированы, выбираем другое y', а y становится неиспользованным}

10 end

11 end;{GAMI}

1 begin {основная программа}

2 for v Є V do DOP[V]:= истина;

3 X[1]:= k ; {k - произвольная}

4 DOP[k]:= ложь;

5 GAMI(2);

6 end.

Протрассируем алгоритм для модельного графа и построим его дерево поиска (рис. 9.2):



Рис. 9.2. Трассировка алгоритма

ложность этого алгоритма в наихудшем случае растет по экспоненте с ростом n.

то справедливо и для случая, когда ищется ровно одно решение (если задача не имеет решения, то эта модификация не влияет на ход выполнения алгоритма).

Вопрос 2. Докажите, представив соответствующий «плохой» граф, что число шагов в алгоритме нахождения всех гамильтоновых циклов растет экспоненциально с ростом n.

Ответ 1. Во всех направлениях, до всех тупиков и полных решений.

Ответ 2. Граф типа «погремушка». Такой граф не содержит ни одного гамильтонова цикла, в то же время все вершины, кроме V₀, соединены и представляют собой клику, т.е. граф, у которого все вершины соединены попарно. Всего различных путей будет n!, а для проверки каждой u_j из них потребуется n шагов, итого nn!, что растет быстрее экспоненты (рис. 9.3).



Рис. 9.3. Граф «погремушка»

9.2 Модификации алгоритма с возвратом для решения задач на минимум

АДАЧА КОММИВОЯЖЕРА

УСЛОВИЕ. заданы конечное множество C городов, целые положительные расстояния A[c₁,c₂] для каждой пары городов c₁,c₂.

ВОПРОС. Найти маршрут минимальной длины, проходящий через все города ровно один раз и возвращающийся в исходный пункт.

Это задача на минимум - среди всех допустимых объектов ищется минимальный. Карта представляется графом, ребрам которого приписаны веса. Из всех гамильтоновых циклов (это полный граф, в нем существуют гамильтоновы циклы) в этом графе нужно выбрать цикл минимальной длины. Длина определяется естественным образом - как сумма расстояний между городами, входящими в маршрут. Можно поступить просто - сгенерировать алгоритмом с возвратом все циклы и среди них выбрать минимальный. Однако, немного изменив общую схему алгоритма с возвратом, можно добиться того, что возвраты будут происходить значительно раньше и решение будет найдено быстрее.

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

Условие применимости модифицированной схемы для решения задачи на минимум:

1) Припишем каждому решению (и полному, и частичному) стоимость - ее еще называют целевой функцией. Будем обозначать целевую функцию cost.

2) При продолжении решения его стоимость может только увеличиваться:

3) cost(<X(1), … , X(i-1)>) cost(<X(1), … , X(i-1), X(i)>)

для любого i 2.

Для задачи коммивояжера целевой функцией будет стоимость маршрута

Очевидно, что ее величина при удлинении маршрута может только увеличиваться, так как по условию задачи все расстояния положительны.

Идея алгоритма модифицированной схемы:

1. Находим первое решение и запоминаем его в OptX, а его стоимость в OptCost.

2. Пусть <X(1), … , X(i)> - текущее частичное решение. Найдем допустимое X(i+1). Если cost(<X(1), … , X(i), X(i+1>) OptCost, то любое его продолжение будет заведомо больше текущего минимального решения. Отбрасываем X(i+1) как недопустимое и ищем новое X'(i+1).

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

Вопрос. Как находить первое решение, чтобы еще более убыстрить выполнение алгоритма?

ЛГОРИТМ {Нахождение гамильтоновых цикла min длины}

анные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], матрица весов A[u,v].

езультаты: Печать минимального гамильтонова цикла.

еременные ЗАПИСЬ, X, cost, OptX, OptCost, DOP - глобальные.

1 procedure COMMI(i);

2 begin

3 for y Є ЗАПИСЬ[X[i-1]] do

4 if cost+A[X[i-1],y]<OptCost then

5 if (i=n+1) AND (y=k) then

6 begin OptX:= X; OptCost:= cost+A[X[i-1],y]

7 end

8 else if DOP[y] then

9 begin

10 X[i]:= y; DOP[y]:= ложь;

11 cost:=cost+A[X[i-1],y];

12 COMMI(i+1);

13 DOP[y]:= истина;

14 cost:=cost-A[X[i-1],y];

15 end;

16 end;

1 begin {основная программа}

2 for v Є V do DOP[v]:= истина;

3 X[1]:= k ; {k - произвольная вершина}

4 DOP[k]:= ложь;

5 cost:=0; OptCost:= +;

6 COMMI(2);

7 end.

Ответ. Не внутри программы, а приближенным алгоритмом. Если первое найденное решение будет оптимальным (или близким к оптимальному), то произойдет максимальное количество досрочных возвратов.

9.3 Модификации алгоритма с возвратом для решения задач на максимум

ЗАДАЧА О РЮКЗАКЕ

УСЛОВИЕ. Заданы конечное множество A, положительные целые веса w(a), стоимости s(a) для каждого a Є A и общее ограничение на вес K.

ВОПРОС. Найти из всевозможных выборок A' A такую, чтобы суммарный вес входящих в него элементов не превосходил K, а суммарная стоимость была максимальна.

адача о рюкзаке - задача об определении оптимальной выборки из N объектов, подчиненной некоторому ограничению. оскольку из N объектов возможно сделать 2^N различных выборок, для решения подобной задачи с помощью алгоритма с возвратом необходимо очень сильное ограничение.

Вопрос 1. Изменим стоимости предметов на противоположные. Выборка максимальной стоимости превратилась в выборку минимальной стоимости. Почему нельзя эту задачу решить алгоритмом для решения задач на минимум, изложенным в предыдущем разделе?

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

ПРИНЦИП ВКЛЮЧЕНИЯ-НЕВКЛЮЧЕНИЯ.

аждый i-й объект проверяется на допустимость (согласно нашему ограничению). Затем внутри одной процедуры допустимый объект вначале включается в выборку, и с этим включенным объектом рекурсивно генерируются всевозможные решения и лучшее из них запоминается как оптимальное.