Книги-online

Теория графов.

И в библиотеке бывают рекламные паузы.

Теория графов.

Введение.

На этой странице рассматриваются алгоритмы работы с графами. Граф - пара G=(V,E), где V - множество вершин (вершинами могут быть объекты произвольной природы) и E - множество ребер, ребра - элементы вида e=(vi,vj), где vi,vj принадлежат множеству вершин, т.е. ребро это элемент из декартова произведения множества V на себя. Достаточно подробно терминология теории графов разобрана на странице А.Чернобаева, поэтому за более полной информацией можно обратиться туда, там же можно найти алгоритмы для работы с графами, как те которые представлены здесь, так и многие другие. Нам же для дальнейшей работы понадобится рассмотреть способы задания и структуры для хранения информации о графе.

Первый способ задания графа (невзвешенного) это задать матрицу связности S размера n*n, где n количество вершин графа, т.е. мощность множества V, при этом элемент si j=1, если существует ребро из i-ой в j-ую вершины и si j=0, если такого ребра нет. Нетрудно видеть, что матрица S- симметрична, если граф неориентированный, и может быть не симметричный в противном случае. При этом полагаем, что si i=0, т.е. в графе нет петель. Такой способ задания графа используется например в волновом алгоритме.

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

Путь с минимальным количеством промежуточных вершин.(волновой алгоритм)

Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе G=(V,E) заданном матрицей связности S. Путь ищется из вершины номер u1 к вершине номер u2. Процедура использует волновой алгоритм.

Волновой алгоритм заключается в следующем:

каждой веpшине i пpиписывается два целых числа T[i] - вpеменная метка и P[i] - метка предыдущей вершины пути (начальное значение T[i]=0, P[i]=0 для всех i);

заводятся два списка "фpонта волны" NF и OF, а также пеpеменная T (текyщее вpемя);

OF:={u1}; NF:={}; T:=1;

для каждой из веpшин i, входящих в OF, пpосматpиваются соседние веpшины j, и если T[j] = 0, то T[j]=T, NF=NF + {j}; в переменную P[j] заносится номер i.

если NF = {}, то пyть не сyществyет, переход к шагу 8;

если одна из веpшин совпадает с u2, то найден кpатчайший пyть длины T, переход к шагу 8;

OF:=NF; NF:={}; T:=T+1; возврат к шагу 4.

Восстанавливаем путь проходя массив P.

В качестве OF, NF я использую массивы размера n (количество вершин в графе), некоторые языки (например Pascal) позволяют работать с объектами типа множества, тогда правильнее использовать именно такую структуру для определения OF, NF, но для того чтобы не нарушать общности я все же остановился именно на массивах, которые присутствуют практически во всех языках программирования.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2) и массив Path содержащий последовательность номеров вершин определяющих путь. Наверх

Путь минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Дейкстры)

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

Алгоритм по которому происходит поиск заключается в следующем:

всем веpшинам пpиписывается вес - вещественное число, d(i)=GM для всех вершин кроме вершины с номером u1, а d(u1)=0;

всем веpшинам пpиписывается метка m(i)=0;

вершина u1 объявляется текущей - t=u1

для всех вершин у которых m(i)=0, пересчитываем вес по формуле: d(i):=min{d(i), d(t)+W[t,i]}

среди вершин для которых выполнено m(i)=0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует; ВЫХОД;

иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t)=1)

если t=u2, то найден путь веса d(t),ВЫХОД;

переходим на шаг 4.

На выходе имеем переменную length, которая определяет длину пути (length=-1 если пути не существует, length=0, если u1=u2), переменную Weight -вес пути и массив Path содержащий последовательность номеров вершин определяющих путь. В алгоритме не упомянуто, как же определить сам путь, но это легко выяснить, если посмотреть блок-схему. Наверх

Путь минимальной суммарной длины во взвешенном графе с произвольными весами для всех пар вершин.(алгоритм Флойда)

Процедура находит пути минимального веса в графе G=(V,E) заданном весовой матрицей w у которой элемент wi j равен весу ребра соединяющего i-ую и j-ую вершины. При этом полагаем, что W[i,i]=0 для всех i. Путь ищется для всех пар вершин графа. Для бесконечности используется число GM его можно задавать в зависимости от конкретной задачи.

Следует заметить, что если в графе существует контур отрицательной сумарной длины, то вес любого пути, проходящего через вершину из этого контура, можно сделать сколь угодно малой, "прокрутившись" в контуре необходимое количество раз. Поэтому поставленная задача разрешима не всегда. В случае описанном выше, алгоритм Флойда прекращает свою работу. Останавливаясь подробнее надо заметить, что если граф неориентированный (W[i,j]- симметрична), то ребро с отрицательным весом является как раз таким контуром (туда-сюда можно бегать пока не сделаем вес достаточно малым)

Алгоритм Флойда предполагает последовательное преобразование матрицы весов W. В конечном итоге получаем матрицу, элементы d[i,j] которой представляют из себя вес минимального пути соединяющего i и j вершины. Рассмотрим преобразования матрицы весов:

	D0=W
	dm+1[i,j]=min{dm[i,j], dm[i,(m+1)] + dm[(m+1),j]}, где ij; dm+1[i,i]=0.

преобразование проделывается для m=1..n, где n - мощность множества вершин графа. Если на некотором шаге получим отрицательное dm[i,m]+dm[m,i] для какого-нибудь i, то в графе существует контур отрицательного веса, проходящий через вершину i и задача не разрешима.

На выходе получаем матрицу D минимальных весов и матрицу P при помощи которой можно востановить путь минимального веса следующим образом: значение p[i,j] будет равно номеру предпоследней вершины в пути между i и j (либо p[i,j]=i, если путь не существует). Переменная s на выходе равна 1, если алгоритм отработал полностью, и нулю, если в ходе работы алгоритма найден контур отрицательного веса.

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

Нахождение K путей минимальной суммарной длины во взвешенном графе с неотрицательными весами.(Алгоритм Йена)

Алгоритм предназначен для нахождения К путей минимальной длины во взвешеном графе соединяющих вершины u1,u2. Ищутся пути, которые не содержат петель. Алгоритм прислал Pavel Mikheyev

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

Работа алгоритма начинается с нахождения кратчайшего пути, для этого будем использовать уже описанный алгоритм Дейкстры. Второй путь ищем перебирая кратчайшие отклонения от первого, третий кратчайшие отклонения от второго и т.д. Более точное пошаговое описание: 1. Найти минимальный путь P1=(v11,...,v1L[1]) .Положить k = 2. Включить P1 в результирующий список. 2. Положить MinW равным бесконечности. Найти отклонение минимального веса, от (k–1)-го кратчайшего пути Pk-1 для всех i=1,2,...,L[k-1], выполняя для каждого i шаги с 3-го по 6-й. 3. Проверить, совпадает ли подпуть, образованный первыми i вершинами пути Pk-1, с подпутем, образованным первыми i вершинами любого из путей j=1,2,...,k–1). Если да, положить W[vk-1i,vji+1] равным бесконечности в противном случае ничего не изменять (чтобы в дальнейшем исключить получение в результат одних и тех же путей). 4. Используя алгоритм нахождения кратчайшего пути, найти пути от vk-1i к u2, исключая из рассмотрения корни (vk-11,...,vk-1i) (чтобы исключить петли), для этого достаточно положить равными бесконечности элементы столбцов и строк матрицы W, соответствующие вершинам входящим в корень. 5. Построить путь, объединяя корень и найденное кратчайшее ответвление, если его вес меньше MinW, то запомнить его. 6. Восстановить исходную матрицу весов W и возвратиться к шагу 3. 7. Поместить путь минимального веса (MinW), найденый в результате выполнения шагов с 3 по 6, в результирующий список.Если k = K, то алгоритм заканчивает работу, иначе увеличить k на единицу и вернуться к шагу 2.

Алгоритм использует массив p для результирующего списка путей, и массив length для хранения соответствующих длин, при этом если начиная с некоторого i элементы length[i] равны -1, значит существует только i-1 кратчайшех путей без петель. Наверх

Построения минимального остовного дерева (Алгоритм Краскала)

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

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

Итак алгоритм Краскала:
1. Сортируем ребра графа по возрастанию весов.
2. Полагаем что каждая вершина относится к своей компоненте связности.
3. Проходим ребра в "отсортированном" порядке. Для каждого ребра выполняем:

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

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

Предположим, что как и ранее граф задается матрицой весов W (см. введение), ясно, что в данном случае работать непосредственно с матрицей весов не удобно, это выявляется уже на этапе упорядочивания ребер по весу, поэтому вначале выделим массив ребер с соответствующими весами. В нашем случае достаточно если ребро будет иметь три свойства: начальная вершина, конечная вершина и вес (вообще работа с графами хорошо реализуется методами ООП, но поскольку мы не используем расширения языков, то будем работать с простыми массивами). Для задания набора ребер используем два массива E: array [1..m,1..2] of integer - здесь m - количество ребер (m<n2-n+1, где n - количество вершин), и массив EW: array [1..m] of real, тогда ребро ei, соединяющее вершины u,v с весом wi будет соответствовать элементам E[i,1]=u,E[i,2]=v,EW[i]=w. Таким образом до начала непосредственно поиска минимального остовного дерева нам необходимо пройти матрицу весов W и заполнить массивы E и EW.

Преобразовав представление графа от весовой матрицы к набору ребер (часто граф изначально задается при помощи списка ребер, и тогда предыдущая часть алгоритма становиться не нужна), мы уже можем легко упорядочить ребра по неубыванию весов, я для этого использую в блок-схеме алгоритм пузырька, чтобы не "замазывать" основной алгоритм, но можно легко перейти и к другим способам упорядочивания. Далее в алгоритме вводиться массив V:array [1..n] of integer элементы, которого характеризуют номер компоненты связности соответствующих вершин (две вершины u1,u2 лежат в одной компоненте связности, если и только если V[u1]=V[u2]). Теперь все структуры используемые в алгоритме описаны, и его работу легко будет понять из блок-схемы.

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

Найденое дерево будет определено с помощью массива WO - матрицы весов. Наверх