Формализация описания структуры на основе теории графов

Понятие связности графа

Для неориентированных графов вводится понятие слабой связности, или просто связности, если для всех вершин графа i и j существует цепь из вершины i в вершину j.

Граф G(V) - сильно связан (ориентированный граф), если для всех вершин графа i, j существует путь из вершины i в вершину j.

Порядковая функция на графе. Понятие уровня

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

Полученные непересекающиеся подмножества - уровни.

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

В подмножество нулевого уровня N₀ - все вершины i, у которых G^-1(i) = 0 (нулевой (пустой) столбец)

Проводится последовательная нумерация вершин: 1, 2, …, l. Строка - куда выходят связи, столбец - что входит в вершину.

В подмножество первого уровня N₁ - все вершины i, у которых (те вершины, в которые входят духи только из вершин N₀ уровня).

Проводится последовательная нумерация вершин: l + 1, l + 2, …, l + r.

Второй уровень N₂: .

Нумерация: l + r +1, l + r + 2, …, l + r + p.

Данный процесс повторяется до тех пор, пока не будут пронумерованы все вершины графа. Изложенная процедура нумерации приводит к тому, что в матрице смежности вершин графа a_ij = 0 при i > j.

141

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

141

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

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

Числовая функция на графе

Числовая функция на вершинах графа считается заданной, если каждой i-той вершине a_i графа G(V) , ставится в соответствие некоторое число l_i = l(a_i) из некоторого множества L.

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

Значение функции на пути S через вершины a₁, a₂, …, a_i () при задании числовой функции на вершинах графа определяется

(1)

или

(2)

Аналогично значения функции на пути через вершины при задании числовой функции на дугах (ребрах) графа

(3)

или

(4)

Определение максимального (минимального) путей на графе чаще всего формулируется в виде задачи динамического программирования:

так в соответствии с (2-3)

где - максимальное значение функции на путях S из вершины a₁ в вершину a_j.

- множество левых инциденций для a_j.

q(a_ia_j) - значение функции на дуге (a_ia_j).

При этом предполагается, что все вершины в графе упорядочены.

Пример2. Определение максимального пути на графе

141

Рис. 4

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

Для вершины a₁:

Для вершин a₂, a₃, a₄:

Для вершины a₅:

Для вершины a₆:

Для вершины a₇:

Определение максимального и минимального путей имеет многочисленные приложения при проектировании БСУ: в задачах сетевого и календарного планирования для определения критического пути, в транспортных задачах, в задачах контроля и технической диагностики и др.