glava2 (1033925), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

Наиболее важные свойства параллельной формы:

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

• все дуги, входящие в вершины 1-го яруса, не имеют начальных вершин или отсутствуют;

• все дуги, выходящие из вершины последнего яруса, не имеют концевых вершин или отсутствуют;

• произведение высоты любой параллельной формы на ее ширину не меньше общего числа вершин графа;

• высота формы на 1 больше длины критического графа.

Параллельно-ярусную форму графа легко интерпретировать в виде матрицы Н размерности h  n, где h - число ярусов, а элементы h_ij матрицы Н равны 1, если j-ая вершина принадлежит i-ому ярусу и 0 в противном случае (рис.2.4).

Дерево - это ациклический граф специального типа. (Ориентированное) дерево Т – это (ориентированный) граф G = (A, R) со специальной вершиной r  A, называемой корнем, у которого :

• степень по входу вершины r равна 0;

• степень по входу всех остальных вершин дерева Т равна 1;

• каждая вершина а  A достижима из r.

Дерево Т обладает следующими свойствами :

• Т - ациклический граф;

• для каждой вершины дерева Т существует единственный путь, ведущий из корня в эту вершину (рис. 2.5).

(Применительно к ориентированному графу G (рефлексивным и) транзитивным замыканием называется граф G^*, который содержит то же множество вершин, что и G, но в котором из вершины a в b идёт одна дуга тогда и только тогда, когда в G существует путь (длины 1 или больше) из a в b).

Граф (то есть отношение) может интерпретироваться (представляться) и как квадратная булева матрица М (составленная из 0 и 1) размера пхп, называемой матрицей смежности. В матрице смежности 1 на пересечении i-ой строки и j-го столбца стоит только тогда, когда элемент (вершина), соответствующий i-ой строке, находится в отношении R с элементом (вершиной), соответствующим j-му столбцу; в противном случае имеем 0.

Используя матрицу смежности легко интерпретировать не только сам граф, но и его транзитивное замыкание R⁺. Для этой цели вводится матрица смежности транзитивного замыкания M⁺.

При вычислении матрицы смежности используют булевы операции умножения и сложения. Помимо матрицы смежности существует и матрица инцидентности, показывающая принадлежность вершины и исходящих из нее дуг. Матрица инцидентности I является прямоугольной размера nd, где d – число дуг, и на пересечении i-ой строки и j-ого столбца стоит 1, если из i-ой вершины выходит j-ая дуга; в противном случае имеем 0. На рис.2.3 приведён граф и его матрицы смежности i–ой степени отношения и матрицы инцидентности.

2.1.3. Наиболее распространенные алгоритмы на графах.

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

Топологическая сортировка.

Вложение частичного порядка в линейный называется топологической сортировкой.

Формально, частичный порядок R на множестве A вложен в линейный порядок R, если R – линейный порядок и R  R, то есть aRb влечет aRb для всех a, b  A.

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

Приведем один из алгоритмов топологической сортировки [1].

Вход: Частичный порядок R на конечном множестве A.

Выход: Линейный порядок R на A, для которого R  R.

Решение: Так как A – конечное множество, линейный порядок R на A можно представить в виде списка a₁, a₂, ..., a_n, для которого a_iRa_j, если i < j, и A = {a₁, a₂, ..., a_n}. Этот список строится с помощью следующих шагов:

1. Положить i = 1, A_i = A и R_i = R ;

2. Если A_i пусто, остановиться и выдать a₁, a₂, ..., a_i-1 в качестве искомого линейного порядка. В противном случае выбрать в A_i такой элемент a_i, что aR_ia_i ложно для всех a  A_i ;

3. Положить A_i+1 = A_i – {a_i} и R_i+1 = R_i  (A_i+1  A_i+1). Затем увеличить i на единицу и повторить шаг 2 ;

Более кратко. Так как частичный порядок представляется в виде ациклического графа, то на каждом шаге алгоритма (A_i, R_i) является ациклическим графом и a_i – его базовая вершина. Ациклический граф (A_i+1, R_i+1) образуется из (A_i, R_i) вычеркиванием вершины a_i и всех выходящих из нее дуг.

Н
а рис.2.6 приведен ациклический граф и соответствующий линейный порядок.

Однако, в общем случае, топологической сортировкой называется разметка вершин графа в соответствии со следующим утверждением. Если задан ориентированный ациклический граф, имеющий п вершин, то существует целое число s  п , для которого все вершины графа можно так пометить одним из индексов 1,2,…,s, что при наличии дуги (a_i,a_j) имеем i<j

Нахождение кратчайших путей.

Пусть задан граф G = (A, R) с разметкой дуг, то есть каждой дуге, ведущей из вершины i в вершину j приписан вес (стоимость) c_ij (если из i в j не ведет ни одна дуга, вес c_ij считается бесконечным); причем считается, что c_ij  0. Стоимость пути определяется как сумма стоимостей дуг, образующих его. Тогда кратчайший путь обладает наименьшей стоимостью среди всех путей, ведущих из a в b.

Существуют алгоритмы нахождения кратчайших путей в различных модификациях [1],[2]. Приведем один из алгоритмов [1].

Вход: Граф G с n вершинами, занумерованными 1, 2, ..., n и с весами c_ij  0 для всех 1  i, j  n.

Выход: Матрица M = [m_ij], в которой m_ij – минимальный из путей, ведущих из вершины i в вершину j.

Решение:

1. Положить m_ij = c_ij для всех i и j;

2. Положить k = 1;

3. Для всех i и j, если m_ij > m_ik + m_kj , положить m_ij = m_ik + m_kj;

4. Е
   сли k < n, увеличить k на единицу и перейти к шагу 3. Если k = n , то выполнить и остановиться.

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

k = 1

k = 2

k = 3

Результаты работы алгоритма сведены в таблицы:

В тех случаях, когда желательно вычислить транзитивное замыкание отношения R, полагают c_ij = 0, если a_iRa_j, и c_ij =  в противном случае. Тогда матрица M⁺ транзитивного замыкания будет состоять только из значений равных 0 или ; причем 0 будет соответствовать наличию пути между вершинами, а  – его отсутствию.

Наряду со значением стоимости кратчайшего пути в большинстве случаев следует и определить этот путь, т.е. найти набор дуг, составляющих этот кратчайший путь. Здесь также существуют соответствующие алгоритмы, например, алгоритм Дейкстры, который находит кратчайший путь и его дуги из одного источника (из базовой вершины) в любую другую. Если, в общем случае, в графе нет базовой вершины, то ее создают, вводя новую вершину и дугу с нулевым весом. Так на рис.2.7б показано введение для графа (а) базовой вершины a₀ (б).

Характеристики

Список файлов книги