26

Графы

Граф - это пара (V,E), где V - конечное непустое множество объектов произвольной природы, называемых вершинами (vertices, nodes), а E - множество неупорядоченных пар <u,v> вершин из V называемых ребрами (edges). Говорят, что ребро s=<u,v> соединяет вершины u и v. Ребро s и вершина u (а также s и v) называются инцидентными, а вершины u и v - смежными. Ребра, инцидентные одной и той же вершине, также называют смежными. Если ребро s=<u,v> встречается более одного раза, то s - кратное ребро. Ребро вида s=<u,u> называется петлей в вершине u. На рис.1 < 4,2 > - кратные ребра, < 1,1 > петля.

Если порядок элементов, входящих в e_i, имеет значение, то граф называется ориентированным (directed graph), сокращенно - орграф (digraph), иначе - неориентированным (undirected graph). Ребра орграфа называются дугами (arcs). Дуга (u,v) ведет от вершины u к вершине v. При этом вершину v называют преемником вершины u, а u - предшественником вершины v. В дальнейшем будем считать, что термин "граф", применяемый без уточнений "ориентированный" или "неориентированный", обозначает неориентированный граф.

Пример: G=(V,E); V={1,2,3,4}; E=< (1,1), (1,2), (1,3), (2,4), (2,4) >

Степень вершины deg(v) графа - это число ребер, инцидентных данной вершине v, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер.

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

Вершину степени 0 называют изолированной.

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

Граф, не содержащий петель и кратных ребер, называется обыкновенным, или простым графом (simple graph). Во многих публикациях используется другая терминология: под графом понимается простой граф, граф с кратными ребрами называют мультиграфом, с петлями - псевдографом.

Некоторые классы графов получили особые наименования. Граф с любым количеством вершин, не содержащий ребер, называется пустым. Обыкновенный граф с n вершинами, любая пара вершин которого соединена ребром, называется полным и обозначается K_n (очевидно, что в полном графе n(n-1)/2 ребер).

Граф, вершины которого можно разбить на непересекающиеся подмножества V₁ и V₂ так, что никакие две вершины, принадлежащие одному и тому же подмножеству, не смежны, называется двудольным (или бихроматическим, или графом Кенига) и обозначается B_mn (m=|V₁|, n=|V₂|, m+n=|V|). Полный двудольный граф - такой двудольный граф, что каждая вершина множества V₁ связана со всеми вершинами множества V₂, и наоборот; обозначение - K_mn. Замечание: полный двудольный граф B_mn не является полным (за исключением B₁₁=K₂).

B₃₃

Часть графа G = (V,E) - это такой граф G' = (V',E'), что V' принадлежит V и E' принадлежит E. Подграфом графа G называется такая его часть G', которая вместе со всякой парой вершин u, v содержит и ребро <u,v>, если только оно есть в G. Остовным подграфом (суграфом) графа G называется любой его подграф, содержащий то же множество вершин, что и G.

Путь, соединяющий вершины u и v, - это последовательность вершин v(0), v(1),..., v(n) (n>=0) такая, что v(0)=u, u(n)=v и для любого i (0<= i <= n-1) вершины v(i) и v(i+1) соединены ребром. Длина пути v(0), v(1),...,v(n) равна количеству его ребер т.е. n. Путь замкнут, если v(0) = v(n). Путь называется простым, если все его вершины различны. Замкнутый путь, в котором все ребра различны называется циклом. Простой цикл - это замкнутый путь, все вершины которого, кроме v(0) и v(n), попарно различны. Гамильтоновым называется граф, в котором существует простой цикл, содержащий все вершины графа (но не обязательно все его ребра).

Расстояние между двумя вершинами - это длина кратчайшего пути, соединяющего эти вершины. Обод - это граф, вершины которого v(0), v(1),..., v(n) (n >= 2) можно занумеровать так, что для всех i (1<=i<=n-1) вершина v(i) соединена ребрами с v(i-1), v(i+1), вершина v(0) - c v(n), а других ребер нет.

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

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

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

Граф называется полным, если любые две его различные вершины соединены ребром. Два графа G и H изоморфны если существует взаимно однозначное отображение (называемое изоморфизмом) множества вершин графа G на множество вершин графа H, сохраняющее смежность. Автоморфизмом графа G называется изоморфизм графа G на себя.

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

Деревом называется связный граф без циклов.

Корневое дерево - это связный орграф без циклов, удовлетворяющий следующим условиям:

имеется ровно одна вершина, называемая корнем, к которой не ведет ни одной дуги;

к каждой вершине, отличной от корня, ведется ровно одна дуга;

преемники всякой вершины упорядочены.

Вершины корневого дерева, не имеющие преемников, называются листьями.

Способы задания графов

Матрица смежности представляет собой квадратную матрицу n на n, где n- количество вершин графа.

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

При более подробном рассмотрении можно заметить, что в случае графа без петель матрица имеет ряд особенностей:

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

если наш граф неориентированный - то часть матрицы под главной диагональю и над ней абсолютно идентичны.

На Pascal-е матрица смежности чаще всего задается при помощи двумерного массива:

Matr_Sm: array [1..TopsCount,1..TopsCount] of byte,

либо

Matr_Sm:array [1..TopsCount,1..TopsCount] of boolean;

Матрица инцидентности

представляет собой матрицу m на n, где m - количество ребер или дуг графа (орграфа), а n - количество вершин. На пересечении i - ой строки и j - ого столбца проставляются значения по следующему правилу:

"1" - если i - ое ребро и j - ая вершина инцидентны (для орграфа - если i - ая дуга "входит" в j - ую вершину);

"0" - если i - ая дуга и j - ая вершина не инциндентны;

"-1" - только в случае орграфа: если i - ая дуга "выходит" из j - ой вершины);

«1» применяют для невзвешенного графа, для взвешенного графа применяют вес ребра.

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

Типичный пример задания матрицы инцидентности на языке Pascal - при помощи двумерного массива m на n:

Matr_Ints: array [1..TopsCount, 1..LinksCount] of integer;

Список смежности и список инцидентности

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

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

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

Пусть задан граф на n вершинах и требуется создать некоторую структуру переменных в памяти ЭВМ, отображающую список смежности, составленный для данного графа. Для начала выясним, что будет представлять собой данная структура. Так как строка списка содержит номера вершин, то естественно предположить, что мы должны иметь некоторую цепочку динамических переменных целочисленного типа, связанных между собой. Такая связь обеспечивается использованием указателей, объединенных вместе с целочисленной переменной в запись (Pascal: record). Для того, чтобы обеспечить хранение входных указателей в такие цепочки, используется одномерный массив указателей, имеющий длину, равную количеству вершин графа. Признаком конца цепочки можно использовать какое-либо значение, не допускаемое при нумерации вершин (например - "0"), занесенное в целочисленную переменную последнего блока.

Для созданя такой структуры предварительно необходимо сделать объявления такого рода:

Type

BlockPtr = ^BlockType;

BlockType = record

Number:integer;

Point:BlockPtr;

end;

Var

In_Ptr:array [1..TopsCount] of BlockPtr;

Создание цепочки в памяти осуществляется при вводе списка смежности при помощи процедуры New (BlockPtr_Type_Variable), где BlockPtr_Type_Variable - переменная типа BlockPtr.

Основные задачи на графах

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

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

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

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

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

Опишем процедуру поиска в ширину (BFS - от английского названия этого алгоритма - Breadth First Search) из заданной стартовой вершины б. В этом описании V(x) обозначает множество всех вершин, смежных с вершиной x, Q - очередь открытых вершин. Предполагается, что при посещении вершины она помечается как посещенная и эта пометка означает, что вершина уже не является новой.

Procedure BFS(a)

1. посетить вершину б

26

2.

3. while Q?O do

4.

5. for do

6. исследовать ребро (x,y)

7. if вершина y новая

8. then посетить вершину y

9.

Отметим некоторые свойства процедуры BFS.

Процедура BFS заканчивает работу после конечного числа шагов.

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

В результате выполнения процедуры BFS будут посещены все вершины из компоненты связности, содержащей вершину a, и только они.

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

1. Время работы процедуры BFS есть O(m), где m - число ребер в компоненте связности, содержащей вершину б.

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

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

Алгоритм 1. Поиск в ширину.

пометить все вершины как новые

создать пустую очередь Q

for do if б новая then BFS(б)

Учитывая, что цикл for в строке 3 повторяется n раз, где n - число вершин графа, получаем общую оценку трудоемкости O(m+n). Необходимо отметить, что эта оценка справедлива в предположении, что время, требуемое для просмотра окрестности вершины, пропорционально степени этой вершины. Это имеет место, например, если граф задан списками смежности. Если же граф задан матрицей смежности, то для просмотра окрестности любой вершины будет затрачиваться время, пропорциональное n. В этом случае общее время работы алгоритма будет оцениваться какO(n²). Наибольшее значение величины m при данном n равно , т.е. имеет порядок n². Таким образом, трудоемкость алгоритма поиска в ширину при задании графа списками смежности не выше, чем при задании матрицей смежности. В целом же первый способ задания предпочтительнее, так как дает выигрыш для графов с небольшим числом ребер.

В качестве простейшего примера применения поиска в ширину для графа рассмотрим задачу выявления компонент связности. Допустим, мы хотим получить ответ в виде таблицы, в которой для каждой вершины x указан номер comp(x) компоненты, которой принадлежит эта вершина. Компоненты будут получать номера в процессе обхода. Для решения этой задачи достаточно ввести переменную с со значением, равным текущему номеру компоненты, и каждый раз при посещении новой вершины x полагать comp(x)=c. Значение с первоначально устанавливается равным 0 и модифицируется при каждом вызове процедуры BFS.

BFS-дерево и вычисление расстояний

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

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

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

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

Каркас, который будет построен описанным образом в результате поиска в ширину в связном графе, называется BFS-деревом. Его можно рассматривать как корневое дерево с корнем в стартовой вершине б. BFS-дерево с заданным корнем б, вообще говоря, не единственное - зависит от того, в каком порядке просматриваются окрестности вершин. Однако всякое BFS-дерево обладает свойством, на котором и основаны наиболее важные применения поиска в ширину. Каркас T связного графа G с корнем б назовем геодезическим деревом, если для любой вершины x путь из x в б в дереве T является кратчайшим путем между x и б в графе G.

Итак, мы можем применить поиск в ширину для вычисления расстояний от стартовой вершины б до всех остальных вершин графа - нужно только в процессе обхода для каждой посещаемой вершины y определять расстояние от y до б в BFS-дереве. Это сделать легко:d(б,y)=d(б,x)+1, где x- активная вершина. Вначале устанавливаем d(б, б)=0.

Если граф несвязен, некоторые расстояния будут бесконечными. Чтобы учесть эту возможность, положим вначале d(б,x) = ? для всех x?0. Пока вершина x остается новой, для нее сохраняется значение d(б,x)=?, когда же она посещается, d(б,x) становится равным расстоянию между б и x и больше не меняется. Таким образом, бесконечность расстояния можно использовать как признак того, что вершина новая. Если по окончании работы d(б,x)=? для некоторой вершины x, это означает, что x не достижима из б, то есть принадлежит другой компоненте связности.

Для того чтобы не только определять расстояния, но и находить кратчайшие пути от б до остальных вершин, достаточно для каждой вершины y знать ее отца F(y) в BFS-дереве. Очевидно, что F(y)=x, где x- вершина, активная в момент посещения вершины y. Заполнение таблицы F фактически означает построение BFS-дерева.

Модифицируя процедуру BFS с учетом сделанных замечаний, получаем следующий алгоритм:

Алгоритм 2.Построение BFS-дерева и вычисление расстояний от вершины б до всех остальных вершин:

1. for do d(б,x):= ?

2. d(б, б):= 0

3.

4. while Q?O do

5.

6. for do

7. if d(б,y) = ?

8. then d(б,y):= d(б,x) + 1

9. F(y):= x

10.

Поиск в глубину

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

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

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

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

Обозначим стек для открытых вершин через S, остальные обозначения сохраняют тот же смысл, что и в предыдущем разделе. Через top(S) обозначается верхний элемент стека (т.е. последний элемент, добавленный к стеку). Тогда процедура обхода одной компоненты связности методом поиска в глубину со стартовой вершиной б может быть записана следующим образом (DFS - Depth First Search).

Procedure DFS(a)

1. посетить вершину б

2.

3. while S?O do

4. x:= top(S)

5. if имеется неисследованное ребро (x, y)

6. then исследовать ребро (x, y)

7. if вершина y новая

8. then посетить вершину y

9.

10. else удалить x из S

Еще раз обратим внимание на основное отличие этой процедуры от аналогичной процедуры поиска в ширину. При поиске в ширину вершина, став активной, остается ею, пока не будет полностью исследована ее окрестность, после чего она становится закрытой. При поиске в глубину, если в окрестности активной вершины x обнаруживается новая вершина y, то y помещается в стек и при следующем повторении цикла while станет активной. При этом x остается в стеке и через какое-то время снова станет активной. Иначе говоря, ребра, инцидентные вершине x, будут исследованы не подряд, а с перерывами.

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

Свойства 1 и 2 поиска в ширину, отмеченные в предыдущем разделе, сохраняются и для поиска в глубину. Остается верной и оценка трудоемкостиO(m+n), но ее доказательство требует несколько иных рассуждений, так как каждая вершина теперь может становиться активной несколько раз. Однако каждое ребро рассматривается только два раза (один раз для каждой инцидентной ему вершины), поэтому в операторе if в строке 5 ветвь then (строки 6-9) повторяется O(m) раз. В этом же операторе ветвь else (строка 10) повторяется O(n) раз, так как каждая вершина может быть удалена из стека только один раз.

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

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

Этот алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной стартовой вершины б, строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке S. Через некоторое количество шагов неизбежно наступит тупик - все ребра, инцидентные активной (последней посещенной) вершине x, уже пройдены. Так как степени всех вершин графа четны, в этот момент x=a и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека S в другой стек C, пока не встретим вершину x, которой инцидентно непройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по непройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что S пуст. В этот момент в стеке C находится последовательность вершин эйлерова цикла.

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

1. выбрать произвольно вершину б

2.

3. while S?O do

4. x:= top(S)

5. if имеется непройденное ребро (x, y)

6. then пометить ребро (x, y) как пройденное

7.

8. else переместить вершину x из S в C

26

Для обоснования алгоритма заметим сначала, что первой в стек S помещается вершина б, и она будет последней перемещена из S в C. Следовательно, она будет последней вершиной в стеке C. Далее, как было отмечено выше, первый раз, когда обнаружится, что все инцидентные активной вершине ребра пройдены (т.е. будет выполняться ветвь else в строке 8), активной будет стартовая вершина б. Значит, эта вершина будет первой перемещена из S в C. Итак, по окончании работы алгоритма в начале и в конце последовательности вершин, содержащейся в стеке C, находится вершина б. Иначе говоря, если эта последовательность представляет маршрут (а далее будет показано, что так оно и есть), то этот маршрут замкнут.

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

Будем говорить, что ребро (x, y) представлено в стеке (S или C), если в какой-то момент работы алгоритма в стеке рядом находятся вершины x и y. Ясно, что каждое ребро графа будет представлено в стеке S и что каждые две вершины, расположенные рядом в этом стеке, образуют ребро. Допустим, в какой-то момент из стека S в стек C перемещается вершина x, а непосредственно под ней в стеке S находится вершина y. Возможно, что вершина y будет перемещена из S в C при следующем повторении цикла while, тогда ребро (x, y) будет представлено в стеке C. Другая возможность - между перемещением вершины x и следующим перемещением, т.е. следующим выполнением ветви else, будет несколько раз выполнена ветвь then (строки 6,\,7). Это означает, что будет пройдена некоторая последовательность ребер, начинающаяся в вершине y. Ввиду четности степеней эта последовательность может закончиться только в вершине y. Значит, и в этом случае следующей за вершиной x будет перемещена из S в C вершина y. В любом случае ребро (x, y) будет представлено в стеке C. Из этого рассуждения видно, что последовательность вершин в стеке C является маршрутом и что каждое ребро графа в конечном итоге будет содержаться в этом маршруте, причем один раз.

При каждом повторении цикла while в рассмотренном алгоритме либо проходится одно ребро, либо одна вершина перемещается из S в C. Последнее можно трактовать как прохождение уже пройденного однажды ребра в обратном направлении. Каждое ребро в каждом направлении будет пройдено один раз, поэтому общая трудоемкость этого алгоритма оценивается как O(m). Необходимо только оговориться, что этот вывод, как и аналогичные заключения об алгоритмах обхода в первых разделах этой главы, справедлив лишь при определенных предположениях о том, как задан граф. Способ задания должен обеспечить возможность быстрого просмотра множества ребер, инцидентных данной вершине. Подходящим является, например, задание графа списками инцидентности, в которых для каждой вершины перечисляются инцидентные ей ребра. Необходимо также иметь возможность быстро пометить ребро как пройденное или проверить, пройдено ли данное ребро. Для этого подходящей структурой может служить характеристический массив на множестве ребер.

Гамильтоновы пути и циклы

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

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

Гамильтонов цикл представляет собой, с комбинаторной точки зрения, просто перестановку вершин графа. При этом в качестве начальной вершины цикла можно выбрать любую вершину, так что можно рассматривать перестановки с фиксированным первым элементом. Самый бесхитростный план поиска гамильтонова цикла состоит в последовательном рассмотрении всех этих перестановок и проверке для каждой из них, представляет ли она цикл в данном графе. Такой способ действий уже при не очень большом числе вершин становится практически неосуществимым ввиду быстрого роста числа перестановок - имеется (n-1)! перестановок из n элементов с фиксированным первым элементом.

Более рациональный подход состоит в рассмотрении всевозможных простых путей, начинающихся в произвольно выбранной стартовой вершине б, до тех пор, пока не будет обнаружен гамильтонов цикл или все возможные пути не будут исследованы. По сути дела, речь тоже идет о переборе перестановок, но значительно сокращенном - если, например, вершина b не смежна с вершиной б, то все (n-2)! перестановок, у которых на первом месте стоит б, а на втором b, не рассматриваются.

Рассмотрим этот алгоритм подробнее. Будем считать, что граф задан окрестностями вершин: для каждой вершины x задано множество вершин, смежных с x. На каждом шаге алгоритма имеется уже построенный отрезок пути, он хранится в стеке PATH. Для каждой вершины x, входящей в PATH, хранится множество N(x) всех вершин, смежных с x, которые еще не рассматривались в качестве возможных продолжений пути из вершины x. Когда вершина x добавляется к пути, множество N(x) полагается равным V(x). В дальнейшем рассмотренные вершины удаляются из этого множества. Очередной шаг состоит в исследовании окрестности последней вершины x пути PATH. Если N(x) ?O и в N(x) имеются вершины, не принадлежащие пути, то одна из таких вершин добавляется к пути. В противном случае вершина x исключается из стека. Когда после добавления к пути очередной вершины оказывается, что путь содержит все вершины графа, остается проверить, смежны ли первая и последняя вершины пути, и при утвердительном ответе выдать очередной гамильтонов цикл.

Алгоритм 1. Поиск гамильтоновых циклов

1. выбрать произвольно вершину б

2.

3. N(б):= V(б)

4. while PATH ?O do

5. x:= top(PATH)

6. if N(x) ?O

7. then взять

8. N(x):= N(x) - y

9. if вершина y не находится в PATH

10. then

11. N(y):= V(y)

12. if PATH содержит все вершины

13. then if y смежна с б

14. then выдать цикл

15. else удалить вершину x из PATH

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

Кратчайшее остовное дерево

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

При допущении, что разветвления возможны только в этих же n объектах, задача сводится к нахождению кратчайшего остовного дерева (SST - shortest spanning tree, или MST - minimal spanning tree) во взвешенном графе, вершины которого соответствуют заданным объектам, а веса ребер равны "расстояниям" между ними. Если каждая пара вершин соединена ребром, то граф является полным и решение существует всегда, в противном случае решение существует тогда и только тогда, когда граф связен (отсутствие ребра между двумя вершинами означает невозможность прямой связи между соответствующими объектами).

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

В отличие от задачи Штейнера, задача поиска кратчайшего остовного дерева допускает эффективное решение. Ниже будут рассмотрены два алгоритма решения этой задачи.

Алгоритм Краскала

Вход: связный взвешенный граф G=(V,E), n=|V|, m=|E|.

Выход: SST - кратчайшее остовное дерево G.

1. SST'=<пустой граф с n вершинами>;

2. k=0;

3. если |E(SST')|=n-1, то SST=SST'; КОНЕЦ;

4. k=k+1;

5. e=<k-ое по возрастанию весов ребро графа G>;

6. если добавление e в SST' не приводит к появлению цикла, то добавить его в SST';

7. перейти на шаг 3.

Доказательство корректности алгоритма Краскала

A. Алгоритм Краскала (АК) завершает работу за конечное число шагов и строит остовное дерево графа, т.к. он является частным случаем следующего алгоритма построения остовного дерева графа (без весов).

Алгоритм построения остовного дерева графа (алгоритм ST)

Вход: связный граф G=(V,E), n=|V|, m=|E|.

Выход: ST - остовное дерево графа G.

Занумеровать произвольным образом ребра графа G;

ST'=<пустой граф с n вершинами>;

k=0;

если |E(ST')|=n-1, то ST=ST'; КОНЕЦ;

k=k+1;

e=<k-ое ребро графа G>;

если добавление e в ST' не приводит к появлению цикла, то добавить его в ST';

перейти на шаг 4.

Кратчайший путь

Пусть G - связанный ориентированный граф, в котором каждому ориентированному ребру сопоставлено положительное вещественное число, называемое длиной ребра. Такой граф называется взвешенным, т.к. каждое ребро как бы имеет свой вес или длину. Длина ребра, например, из вершины i в вершину j обозначается w(i,j). Если в графе отсутствует ребро, например из вершины i в вершину j, то w(i,j)=MAX. Длина ориентированного пути в графе G - это сумма длин ребер, составляющих путь.

Ориентированный s-t - путь, имеющий минимальную длину, называется кратчайшим путем из s в t. Длина кратчайшего ориентированного s-t - пути называется расстоянием из s в t и обозначается через d(s,t). Ясно, что d(i,i)=0 для любого i.

Поиск минимального пути по алгоритму Форда

Алгоритм Форда позволяет от какой-либо исходной вершины Xi определить минимальный путь до произвольной вершины Xj графа G.

Алгоритм Форда состоит из следующих шагов:

Каждой вершине Xi графа G ставятся в соответствие максимально возможные для данной задачи числа Hi;

На втором шаге вычисляются разности Hj-Hi для каждой вершины Xi, где Hj - вес вершины, в которую ведет дуга (Xi,Xj). Здесь возможны три случая: Hj - Hi < Lij, Hj-Hi=Lij, Hj-Hi>Lij, где Lij - вес дуги, ведущей из вершины Xi в вершину Xj.Случай, когда Hj-Hi>Lij позволяет нам уменьшить расстояние между вершинами Xi и Xj благодаря следующим преобразованиям: Hj-Hi>Lij, Hj > Lij + Hi, отсюда принимаем: Hj=Hi+Lij.

Второй шаг выполняется до тех пор, пока еще существуют пары (i,j), для которых выполняется неравенство Hj-Hi>Lij.

По окончанию второго этапа метки вершин позволяют нам определить значение минимального пути из исходной в конечную вершину;

На третьем этапе происходит определение минимального пути при помощи обратного хода от конечной вершины к начальной, причем для вершины Xj предшествующей будет вершина Xi, если для этой пары выполняется Hj-Hi=Lij. Если существует несколько таких пар, то выбирается любая из них.

Алгоритм Белмана - Калаба

Использование алгоритма Беллмана-Калаба позволяет нам ускорить поиск минимального пути между произвольной заданной парой вершин.

На первом этапе заданному графу ставится в соответствие взвешенная матрица смежности M. Матрица формируется по следующим правилам:

M(i,j)=Lij, если существует дуга, ведущая из Xi в Xj, где Lij - вес этой дуги;

M(i,j)=max, где max - максимально возможное число для данной задачи, если не существует дуги, ведущей из вершины Xi в Xj;

M(i,j)=0, если i=j.

На втором этапе строится вектор V0 по следующим правилам:

V0(i)=Lin, если существует дуга, ведущая из вершины Xi в вершину Xn, где Xn - конечная заданная вершина, для которой ищется минимальный путь, Lin - вес этой дуги;

V0(i)=max, где max - максимально возможное число для данной задачи, если не существует дуги, ведущей из вершины Xi в Xn;

V0(i)=0, если i=j.

На k-той итерации строится вектор Vk по следующим правилам:

Vk(i)=min{Vk-1(j)+Lij}, где i=1..(n-1),j=1..n; i<>j

Vk(n) = 0.

Итерации прекращаются, когда мы получаем вектор, равный предыдущему, т.е.Vk=Vk-1.

После прекращения процесса элемент вектора Vk, имеющий наименьшее значение, не равное нулю, дает нам длину минимального пути между заданной парой вершин.

Список литературы

Зеленин А.Н. - Графы. Работа с графами - Х.: Телтех, 2010. изд. второе, исправ. и доп. - 250 с.: ил.