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

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

Первый способ задания графа (невзвешенного) это задать матрицу связности 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 полагаем равным бесконечности (на практике это максимальное число возможное на данном языке программирования). Этот способ задания используется например в алгоритмах поиска пути во взвешенном графе.

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

Процедура находит один из минимальных путей (здесь путей проходящих через минимальное количество вершин) в графе 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 содержащий последовательность номеров вершин определяющих путь.

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

Процедура находит пути минимального веса в графе 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]}, где i<>j; 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 а также все матрицы получаемые в результате преобразований симметричны и следовательно достаточно вычислять только элементы расположенные выше главной диагонали.