6. Балансные неравенства в случае ациклического графа.

Решения балансных уравнений (5.3) или балансных неравенств (5.1) играют важную роль в исследовании дифференциальных уравнений на графах. Особый интерес при этом представляют неотрицательные решения. В общем случае, конечно, таких решений может и не быть. Однако есть важный класс графов, для которых балансные неравенства имеют полную систему неотрицательных решений.

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

Определения (ср. [38]). 1. Ориентированная последовательность ребер в которой конечная вершина предыдущего ребра является начальной для следующего, называется путем на графе (ориентированным путем).

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

Может случиться, что путь не имеет ни начала, ни конца, т. е. все вершины в нем являются внутренними.

3. Путь называется циклом (ориентированным циклом), если в нем все вершины внутренние.

4. Граф называется ациклическим, если в нем нет циклов.

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

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

Пусть схема

определяет ациклический граф. Рассмотрим соответствующую систему балансных неравенств

Теорема. Существует линейно-независимых неотрицательных решений системы неравенств (6.2).

Доказательство. Схема (6.1) предполагает некоторую нумерацию Л- и -вершин графа. Можно так перенумеровать вершины ациклического графа, что вдоль любого пути возрастают номера как так и -вершин. Действительно, пусть множество начальных вершин графа. Это множество определяется ациклической структурой графа и не связано с заданием условий вида (1.1). На первом шаге перенумеруем вершины На втором шаге нумеруем те из -вершин, у которых все непосредственно предшествующие -вершины уже получили номера, а затем продолжим нумерацию -вершин и перенумеруем те из -вершин, не имеющие номера, у которых все непосредственно предшествующие -вершины получили номера. На третьем шаге продолжается нумерация В- и -вершин по правилам второго шага и т. д. Очевидно, через конечное число шагов этот процесс нумерации закончится. При этом занумерованными окажутся все вершины графа, так как в противном случае вместе с вершиной без номера существует предшествующая ей вершина без номера и, в силу ацикличности графа, существует начальная вершина без номера, что противоречит построению.

Пусть (6.1) и (6.2) записаны относительно такой нумерации. Совершенно очевидно, что вдоль любого пути номера как так и -вершин возрастают. В частности, если при некотором то

Будем строить набор решений

системы (6.2) следующим образом. Положим

и построим последовательно по убыванию номера Пусть уже построены для всех Построим Перепишем (6.2) в виде

и рассмотрим все те для которых т. е. вершины которым непосредственно предшествует вершина Согласно нумерации для таких возможно лишь при и соответствующие величины по предположению индукции уже определены, т. е. при всех правые части (6.4) известны и можно положить

где максимум берется по всем таким, что Этим построение вектора (6.3) завершается. По построению все компоненты (6.3) неот рицательны и при каждом удовлетворяют всем неравенствам (6.4) и, следовательно, (6.2). Матрица

строками которой являются векторы (6.3), является нижней треугольной матрицей, причем Отсюда следует линейная независимость векторов (6.3). Теорема доказана.

Следствие. Существуют положительные числа такие, что

Доказательство. Каждое уравнение может иметь не более чем линейно-независимых решений. Это значит, что при каждом найдется хотя бы одно значение I (один из векторов (6.3)), такое, что Полагая

где произвольные положительные числа, легко убеждаемся, что числа (6.7) удовлетворяют строгим неравенствам (6.6).