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

Основополагающим представлением при разработке критериев устойчивости графов является представление о характеристических значениях взвешенного орграфа. Для более четкой формулировки этого представления определим матрицу взанмосвязи $A$ для графа $G$ следующим образом:
\[
a_{i j}=f\left(u_{i}, u_{i}\right), \quad i, j=1,2 \ldots, n,
\]

где $u_{1}, u_{2}, \ldots, u_{n}$-вершины графа $G, f(\cdot, \cdot)$-весовая функция. Тогда характеристические значения $G$ определяются как собственные значения $A$.

Связь между значением $v_{j}(t)$ в каждой вершине в момент времени $t$, изменением значения $p_{i}(t)$ и матрицей взаимосвязи графа $G$ дается следующей теоремой.

Теорема о распространении возмущения
Для простого процесса распространения возмущения, начинающегося в вершине и, имеем

и
\[
\begin{array}{c}
p_{j}(t)=\left[A^{t}\right]_{i j} \\
v_{i}(t)=v_{i}(0)+\left[I+A+A^{2}+\ldots+A^{t}\right]_{i j},
\end{array}
\]

где $A$-матрица взаимосвязи для данного орграфа, $[\cdot]_{i j}$ означает элемент соответствующей матрицы, стоящий на пересечении і-й строки и $j$-го столбца.

В качестве иллюстрации этой теоремы рассмотрим простой орграф

В данном случае матрица взаимосвязи такова:
\[
\boldsymbol{A}=\left[\begin{array}{rrrr}
0 & 1 & -1 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 0 & -1 \\
1 & 0 & 0 & 0
\end{array}\right]
\]

Предположим, что простой процесс распространения возмущения начинается в вершине $u_{1}$ в момент времени $t=0$, причем $v_{i}(0)=0, i=1,2,3,4$. Простое вычисление показывает, что
\[
\begin{aligned}
A^{2} & =\left[\begin{array}{rrrr}
0 & 0 & 0 & 2 \\
1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & -1 & 0
\end{array}\right] \\
I+A+A^{2} & =\left[\begin{array}{rrrr}
1 & 1 & -1 & 2 \\
1 & 1 & 0 & 1 \\
1 & 0 & 1 & -1 \\
1 & 1 & -1 & 1
\end{array}\right]
\end{aligned}
\]

Поскольку процесс распространения возмущения начинается в вершине $u_{1}$, получим, что $p_{3}(2)$ определяется элементом, стоящим на пересечении первой строки и третьего столбца матрицы $A^{2}$, т. е. $p_{3}(2)=0$.

Аналогичным образом получим $v_{1}(2)=v_{1}(0)+[I+A+$ $\left.+A^{2}\right]_{1,1}=0+1=1$. Очевидно, что эти результаты согласуются с теоремой о распространении возмущения.

Теперь постараемся связать представления об устойчивости по возмущению и об устойчивости по начальному значению с матрицей взаимосвязи $A$. По-видимому, в настоящее время неизвестны какие-либо общие необходимые и достаточные условия, однако если предположить, что орграф $G$ обладает различными характеристическими значениями (это условие является достаточно общим), то можно сформулировать теорему об устойчивости по возмущению.

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

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

Устойчивость по начальному значению определяется на основе указанной выше теоремы об устойчивости по возмущению. Строгий критерий устойчивости дается следующей теоремой.

Теорема об устойчивости по начальному значению
Взвешенный орграф $G$ устойчив по начальному значению для любого простого процесса распространения возмущения в том и только в том случае, если орграф $G$ устойчив по возмущению для любого простого процесса распространения возмущения и единица не является характеристическим значением $G$.

Таким образом, как устойчивость по начальному значению, так и устойчивость по возмущению определяются путем исследования характеристических значений графа $G$, т. е. корней характеристического уравнения матрицы взаимосвязи $A$.

Пример. Борьба с насекомыми-вредителями
Рассмотрим задачу борьбы с насекомыми-вредителями культурных растений путем распыления инсектицидов. Введем следующие обозначения:
$P_{1}$ – культивируемое растение, прирост которого ограничен влиянием густоты посадки;
$H_{1}$ – растительноядное насекомое-вредитель, питающееся растением $P_{1}$;
$W$ – насекомое-хищник, убивающее только насекомое $H_{1}$;
$G$ – насекомое-хищник, поедающее как насекомое $H_{1}$, так и насекомое $\mathrm{H}_{2}$;
$H_{2}$ – насекомое-вредитель, которое поедает растение $P_{2}$; $I$ – инсектицид.
Знаковый орграф, описывающий эту ситуацию ${ }^{1}$ ), показан на рис. 5.11. Отметим, что знак, приписанный дуге ( $\left.x_{i}, x_{i}\right)$,

Рис. 5.11. Знаковый орграф для задачи борьбы с насекомыми-вредителями.
указывает влияние изменения $x_{i}$ на скорость изменения $x_{i}$. Матрица взаимосвязи для рассматриваемого орграфа имеет вид

Корни характеристического уравнения матрицы $A$ таковы:
\[
\{-0,119 \pm 1,85 i ;-0,335 \pm 1,03 i ;-0,762 ;-0,328 ; 0\},
\]

и, следовательно, максимальный по модулю корень имеет модуль больше единицы. Тогда, согласно теореме об устойчивости по возмущению, граф, представленный на рис. 5.11, не является устойчивым ни по возмущению, ни по значению.
1) Приведенный на рис. 5.11 зюаковый орграф не совсем точно отражает суть дела. Действительно, инсектицид должен истреблять также и насекомое $\mathrm{H}_{2}$ (следует провести дугу со знаком минус от $I$ к $H_{2}$ ), растения $P_{1}$ и $P_{2}$ должны влиять друг на друга (это приведет к дальнейшему усложнению орграфа).- Прим. ред.

Аналогичный результат можно было предсказать и на основании анализа графа (рис. 5.11), поскольку он содержит много циклов усиления возмущения, например $G \rightarrow H_{2} \rightarrow P_{2} \rightarrow$ $\rightarrow \mathrm{H}_{2} \rightarrow G$.

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