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

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

 

Описание потоков информации в системах управления.

Рассмотрим АСУП. Источник информации – документ. Взаимодействие

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

1) исходные поступающие в систему;

2) внешние - результаты переработки исходных;

3) промежуточные – результаты переработки исходных, которые используются для вычисления внешних документов, но сами из системы не выдаются.

Совокупность исходных и внешних документов составляет информационный

базис системы. Между документами, входящими в поток, существуют отношения вхождения и порядка.

Отношение вхождения означает х_j=x_j1 x_j2 … x_jn, т.е. документ х_j образуется непосредственно из документов x_j1, x_j2, …x_jn, а отношение порядка: x_j следует за х_i – означает, что документ хj может быть образован только после документа х_i.

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

Введение порядковой функции на этом графе позволит выявить его многоуровневую структуру и классифицировать документы по уровням формирования, т.е. упорядочить информационные процессы в АСУП.

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться:

Популярное:

1. АДАПТАЦИЯ И ОПИСАНИЕ ИСПОЛЬЗУЕМЫХ АЛГОРИТМОВ
2. Алгоритм выполнения чертежей с использованием
3. Алгоритм вычисления ошибки косвенных измерений
4. Алгоритм интегрирования рациональной дроби
5. Алгоритм К внутригрупповых средних.
6. Алгоритм кратчайшей раскраски графа
7. Алгоритм метода проекции градиента
8. Алгоритм обработки и анализа данных
9. Алгоритм обработки результатов ПФЭ
10. Алгоритм обучение перцептрона
11. Алгоритм оказания неотложной помощи
12. Алгоритм подбора состава тяжелого бетона.