Главная Прочее
Проблемы автоматизированной обработки информации
|
|
|||||
Формализация описания структуры на основе теории графовПонятие связности графаДля неориентированных графов вводится понятие слабой связности, или просто связности, если для всех вершин графа i и j существует цепь из вершины i в вершину j. Граф G(V) - сильно связан (ориентированный граф), если для всех вершин графа i, j существует путь из вершины i в вершину j. Порядковая функция на графе. Понятие уровня- разбиение множества вершин графа на пересекающиеся подмножества, упорядоченные так, что если вершина входит в подмножество с номером i, то следующая за ней вершина - в подмножество с номером, большим i. Полученные непересекающиеся подмножества - уровни. Алгоритм упорядочения В подмножество нулевого уровня N0 - все вершины i, у которых G-1(i) = 0 (нулевой (пустой) столбец) Проводится последовательная нумерация вершин: 1, 2, …, l. Строка - куда выходят связи, столбец - что входит в вершину. В подмножество первого уровня N1 - все вершины i, у которых (те вершины, в которые входят духи только из вершин N0 уровня). Проводится последовательная нумерация вершин: l + 1, l + 2, …, l + r. Второй уровень N2: . Нумерация: l + r +1, l + r + 2, …, l + r + p. Данный процесс повторяется до тех пор, пока не будут пронумерованы все вершины графа. Изложенная процедура нумерации приводит к тому, что в матрице смежности вершин графа aij = 0 при i > j. 141 Рис. 2 Неупорядоченный граф 141 ![]() Рис. 3 Упорядоченный граф Для графа при наличии контуров в соответствии с этим алгоритмом выделяются сначала сильно связанные подграфы, образующие классы, а далее, так как граф классов не имеет контуров, на нем можно произвести упорядочение и ввести понятие уровней. Числовая функция на графеЧисловая функция на вершинах графа считается заданной, если каждой i-той вершине ai графа G(V) , ставится в соответствие некоторое число li = l(ai) из некоторого множества L. Числовая функция на дугах (ребрах) считается заданной, если каждой дуге (aiaj) ставится в соответствие число qi = q(aiaj) из некоторого множества Q. Значение функции на пути S через вершины a1, a2, …, ai () при задании числовой функции на вершинах графа определяется (1) ![]() ![]() или (2) Аналогично значения функции на пути через вершины при задании числовой функции на дугах (ребрах) графа (3) или (4) ![]() ![]() ![]() ![]() ![]() ![]() Определение максимального (минимального) путей на графе чаще всего формулируется в виде задачи динамического программирования: так в соответствии с (2-3) ![]() ![]() ![]() ![]() где - максимальное значение функции на путях S из вершины a1 в вершину aj. ![]() ![]() - множество левых инциденций для aj. q(aiaj) - значение функции на дуге (aiaj). При этом предполагается, что все вершины в графе упорядочены. Пример2. Определение максимального пути на графе 141 Рис. 4 ![]() ![]() ![]() Множество определяет все вершины, из которых можно непосредственно попасть в вершину i, называется обратным соответствием (столбец) - множество левых инциденций. Для вершины a1: Для вершин a2, a3, a4: Для вершины a5: Для вершины a6: Для вершины a7: Определение максимального и минимального путей имеет многочисленные приложения при проектировании БСУ: в задачах сетевого и календарного планирования для определения критического пути, в транспортных задачах, в задачах контроля и технической диагностики и др. |
<< | СОДЕРЖАНИЕ | >> |
---|