Пример 1. Как видно (см. рис. 2), через две (k = 2) смежные дуги можно попасть: из вершины 1 в вершину 4, из 2 в 1

Как видно (см. рис. 2), через две (k = 2) смежные дуги можно попасть: из вершины 1 в вершину 4, из 2 в 1, из 2 в 3, из 3 в 4, из 4 в 1 и из 4 в 2. ¨

Таким образом, можно алгоритмически определить, существует ли путь из v_i в v_j длиной в k дуг. Очевидно, что если число узлов m, максимальная степень k, в которую нужно возвести А для определения самого длинного пути, равна (m – 1).

Матрица инцидентности – в общем случае прямоугольная матрица В = {b_ij}, , , где m – число вершин, n – число ребер. Для орграфов:

Для неориентированных:

Рис. 3

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

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

Достижимость – это существование пути из узла v_i в узел v_j. Например, на рис. 3.3 путь из узла 1 в узел 4 имеет вид:

узел 1 ® W₁ ® узел 2 ® W₂ ® узел 3 ® W₄ ® узел 4.

Может оказаться, что не все узлы достижимы из остальных узлов. В этом случае может быть выделен подграф Г₁, т.е. совокупность, подмножество узлов, для которого условие сильной связности выполняется. Например, граф Г (см. рис. 3.4) не сильносвязный, т.к. в узел 1 из узлов 2, 3 и 4 нет путей. Сильносвязной компонентой Г₁ для графа Г состоит из узлов 2, 3 и 4 с соответствующими дугами W₂ – W₅.

Физический смысл сильной связности – наличие обратных связей (ОС) между всеми узлами или, другими словами, взаимозависимость (взаимовлияние) всех переменных в графе.

Важность понятия «сильная связность» вытекает из того, что практически все целенаправленные системы строятся на основе принципа обратной связи, когда информация о выходных величинах (координатах) некоторого объекта используется для формирования управляющего сигнала U этим объектом.

Определение эквивалентных передач

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

Для сигнальных графов Мезоном получено следующее соотношение:

, (2)

где Ф_ij – передача от i-го узла к j-му узлу;

Δ – определитель графа:

(3)

W_¥,r (r = 1,2,…) - передаточный коэффициент r-го разомкнутого контура (определяется как произведение передач входящих в контур дуг),

W_¥,r^. W_¥,p (p,r = 1, 2, …, r ¹ p) – произведение «пар» передаточных коэффициентов некасающихся контуров, далее аналогично для «троек», «четверок» и т.д. некасающихся контуров;

P_k – передача k-го прямого пути, определяемая как произведение передаточных коэффициентов дуг, образующих путь;

Δ_k – минор k-го прямого пути (составляется аналогично определителю, но для подграфа, полученного из исходного графа при удалении узлов, принадлежащих k-му прямому пути).

Выделение подсистем в системе

Рассмотрим формальные методы выделения подсистем, базирующиеся на двух основных подходах:

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

- определяется множество всех сильносвязных компонентов;

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

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

Концептуальные методы выделения подсистем базируются на неформальных признаках выделения подсистем. Например, для графа на рис. 5,а можно насчитать пять сильносвязных компонент (кроме самого графа), но концептуально подсистемами можно считать, например, подграфы, изображенные на рис. 5, б и в.

Рис. 5

Проверку силы связности компонент можно осуществлять различными методами, в частности методом Вавилова-Имаева.

Рассмотрим этот метод на примере графа, изображенного на рис. 6. Предположим, что системы S₁ и S₂ не связаны, то есть организованы в систему S ошибочно. Определитель такой несвязной системы будет равен

, (4)

где n – число подсистем (в примере n = 2), Δ_i – определитель i-й подсистемы.

В примере

Δ₁ = 1 + W₁₁^.R₁₁, Δ₂ = 1 + W₂₂^.R₂₂, (5)

Δ_¥ = 1 + W₁₁^.R₁₁ + W₂₂^.R₂₂ + W₁₁^.R₁₁^.W₂₂^.R₂₂. (6)

Рис. 6

Определитель системы с учетом существующих связей:

Δ = 1 + W₁₁^.R₁₁ + W₂₂^.R₂₂ + W₁₁^.R₁₁^.W₂₂^.R₂₂ – W₂₃^.R₁₁^.W₄₁^.R₂₂. (7)

Можно видеть, что разность определителей

δΔ = Δ - Δ_¥ = – W₂₃^.R₁₁^.W₄₁^.R₂₂. (8)

Очевидно, что если

, (9)

«добавкой» δΔ можно пренебречь и подсистемы S₁ и S₂ рассматривать как независимые. Модуль в (4.12) берется потому, что, во-первых, «добавка» δΔ может быть как со знаком «+», так и со знаком «-», во-вторых, значения δΔ, Δ и Δ_¥ - это не обязательно действительные числа. Операторы передач W_ij, K_kp (i, j, k, p – целые числа) могут быть произвольными объектами, в том числе комплексными числами и матрицами. Поэтому модуль может пониматься, по крайней мере, в трех смыслах:

- для действительных чисел – число без знака (со знаком «+»);

- для комплексных чисел p = α + j^.ω, где - мнимая единица:

; (10)

- для матриц – определитель матрицы.

Метод логического ранжирования

Метод используется для задач составления расписаний.

Назначение метода: упорядочивание этапов выполнения некоторых работ.

Предположим, что имеется набор работ (этапов выполнения работ), причем некоторые виды работ не могут быть начаты до того, как будут окончены другие работы. Например, определены причинно-следственные отношения между отдельными работами (см. рис. 7): работа Р₀ является завершающей, ей должны предшествовать работы Р₁, Р₂ и Р₃, работе Р₁ должны предшествовать работы Р₄, Р₅ и Р₉ и т.д. Продолжительность каждой работы примем за единицу.

Для принятия решений нужно выработать критерий, по которому будет происходить оптимизация. В качестве критерия возьмем вес работы. Он тем больше, чем раньше работу необходимо выполнить. Для решения задачи составляется матрица весов (см. табл. 1).

В последней колонке таблицы отмечены веса каждой работы, равные сумме чисел в соответствующей строке. Отсюда можно определить последовательность выполнения работ:

Р₁₁, Р₁₄ ® Р₁₂, Р₁₃ ® Р₇, Р₁₀ ® Р₅, Р₆, Р₈ ® Р₄, Р₉ ® Р₁, Р₂, Р₃.

То есть, сначала выполняются работы Р₁₁ и Р₁₄, после них Р₁₂ и Р₁₃ и т.д. Может быть учтена неравнозначность видов работ, выполняющихся одновременно.

Рис. 7

Таблица 1

Метод анализа иерархий

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

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

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