Треугольная матрица следования. Утверждение об условиях получения треугольных матриц следования

Рассмотрим условие получения матриц следования в треуголь­ном виде. По условию граф-схемы не должны содержать циклов (контуров). Это означает, что главная диагональ всегда должна со­держать нулевые элементы.

Найдем условие построения треугольной матрицы следования для граф-схемы без цикла. Введем в граф-схемы понятие яруса. Возьмем произвольную вершину в графе G, Найдем все дли­ны путей, ведущих в . Среди этих длин найдем максимальную: пусть это будет число . Аналогичные вычисления выполним для некоторой вершины и получим .

Если, то вершины и принадлежат одному ярусу - ярусу h.

Для обеспечения получения треугольной матрицы следования для графа G необходимо при нумерации вершин придерживаться следующего правила: вершины, принадлежащие (d + 1)-му ярусу, должны иметь номера большие, чем номера вершин d-ro яруса. Внутри одного яруса вершины могут нумероваться произвольно. Такую нумерацию назовем нумерацией по ярусам.

Матрица следования получится треугольной, если в граф-схеме G произведена нумерация по ярусам.

Предположим, что в некоторой строке δ матрицы следования существует ненулевой элемент правее главной диагонали. Это значит, что существует связь δ+v→δ. Т.к. номер δ+v>δ, то d_δ ≤ d_δ+v по условию построения матрицы S. Однако, любой путь в вершину δ+v может быть продолжен в вершину δ, поэтому d_δ > d_δ+v, что противоречит предыдущему неравенству. Элемент v был выбран произвольно, следовательно, утверждение теоремы справедливо для любого элемента, лежащего левее главной диагонали