Алгоритм упорядочения графа.

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

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

1. В подмножество нулевого уровня включаются все вершины i, у которых (i)=0 (пустое подмножество) ( (i) определяет все вершины из которых можно непосредственно попасть в вершину i.) (множество левых инциденций). Производится последовательная нумерация вершин: 1,2… e.

(i)=0 (1)=0 (10)=0 =

2. В подмножество первого уровня включаются все вершины i, у которых

(i) (подмножество (i) включено в ).

Производится нумерация вершин e+1; e+2,…, (9)=10 (8)=10 (5)=10 =

3. В подмножество второго уровня включаются все вершины i, у которых

(i) = (7)=(1,8,9) (6)=(8).

 

Рис. 3.3 Неупорядоченный граф.

 

Рис.3.4. Упорядоченный граф.

 

4. В подмножество третьего уровня N3 включаются все вершины i, у которых

(i) (N0 N1 N2). N3={2}. (2)={1,9,7}. Процесс продолжается до тех пор, пока не будут пронумерованы все вершины графа.

 

3.4. Числовая функция на графе. Алгоритм поиска критического пути.

Числовая функция на графе считается заданной, если каждой дуге (ai aj) ставится в соответствие число q=q(ai aj) из некоторого множества Q.

Значение функции на пути S через вершины а1, а2, …, аi, …., (аi S) при задании числовой функции на дугах

q_s= q(ai aj)

(ai aj) S

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

q (a_i a_j)=max[q (a_i a_j)+q (a_i a_j)], ai (a_j), где q (a_i a_j)-максимальное значение целевой функции на путях S из некоторой начальной вершины а1 в вершину

а_j; q (a_i a_ij)-значение функции на дуге (а_i a_j). При использовании данного уравнения считается, что все вершины в графе упорядочены. (a_j) – множество левых инцинденций для вершин (a_j)

Пример. Найти max путь из вершины а₁ в вершину а₇. Принимаем для вершины а₁

q (a₁ a₁)=0. Для вершин а₂, а₃, а₄ : q (a₁ a₂)=2; q (a₁ a₃)=3; q (a₁ a₄)=4.

Для вершины а₅: q (a₁ a₅)=max (2+1; 3+2; 4+1)=5. Для вершины а6: q (a₁ a₆) = =max (3+3’; 4+4)=8. Для вершины а₇: q (a₁ a₇)=max (5+2; 8+1)=9.

Значение функции на max пути равно 9.

 

 

Определение max и min путей имеет многочисленные приложения при проектировании информационно–управляющих систем: в задачах сетевого и календарного планирования для определения критического пути, в транспортных задачах, задачах контроля и технической диагностики.