2.6. Общая теория индексного метода на матрице орграфа

Соберем все полученные результаты воедино и обобщим их на матрице орграфа.

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

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

3. Определение 1. Opt деревом орграфа без контуров называется дерево, индексы всех вершин которого оптимальны. Поэтому всякий путь в opt дереве является оптимальным. Отсюда следует, что для opt дерева справедлив принцип оптимальности.

4. Следствие 1. Лемма 1 позволяет по матрице орграфа перечислить все его деревья, содержащие путь от начальной вершины до конечной (или от конечной до начальной), и выбрать среди них оптимальное, т.е. содержащее искомый оптимальный путь (полный перебор!).

5. Определение 2. Порядковой функцией на орграфе без контуров называется такая функция, которая разбивает множество вершин графа на упорядоченные подмножества Е_i по правилу: а_i  Е_i, если а_i достижима из а₀ не более чем за i шагов (или из а_n не более чем за (n – i) шагов). Порядковая функция строится для задания порядка при просмотре дуг антидерева.

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

6. Лемма 2. Opt дерево для орграфа без контуров может быть построено непосредственно направленным перебором его входящих (исходящих) дуг последовательно по столбцам (или строкам) в соответствии с его порядковой функцией, начиная с корневой вершины, начальной или конечной, т.е. прямым или обратным ходом.

7. Следствие 2. Лемма 2 дает способ построения с минимальным перебором opt дерева, содержащего оптимальный путь от корневой вершины до любой другой в соответствии с принципом оптимальности.