§ 53. Последовательные графы
Граф 
называют последовательным, если для него выполняются следующие условия:
1) G обладает порядковой функцией 
со значениями 
где
Следовательно, последовательный граф - это такой граф без контуров, в котором множество дуг, исходящих из вершин уровня Ей, совпадает со множеством дуг, входящих в вершины уровня 
если нулевой уровень определяется условием 
Пример такого графа приведен на рис. 248.
Очевидно, что к последовательным графам применимы способы отыскания оптимальных путей, изложенные выше, как, например, для графа на рис. 249, где максимальный путь выделен (на рис. 250, та же задача решена для того же графа, но с другой порядковой функцией).
Для последовательного графа процесс оптимизации упрощается.
Пусть
где 
переменная, определенная на вершинах уровня 
Тогда задача сводится к оптимизации функции
Под сложением здесь можно понимать произвольную бинарную ассоциативную операцию 
Мегод динамического программирования, основанный на принципе оптимальности, позволяет записать
(кликните для просмотра скана)
(кликните для просмотра скана)
В случае, когда 
или 
содержат более одной вершины.
Последовательный граф можно разложить на последовательные подграфы, как показано на рис. 251, и производить оптимизацию по частям.
С другой стороны, вводя новые вершины, любой граф без контуров можно дополнить до последовательного. На рис. 252 показано, как это осуществляется; при этом новым дугам приписывается значение 0 (или нейтральный элемент относительно закона 
Задачи, приводящие к оптимизации на последовательных графах. Некоторые комбинаторные задачи можно свести к задаче оптимизации на последовательном графе.
Пусть 
заданы таблицей
Требуется определить минимум
при условии
Строится граф, дугам которого приписываются возможные значения функции из таблицы (53.6), как показано на рис. 253 (вершины расположены в том же порядке, что и числа в 
Порядок, в котором рассматриваются переменные 
произволен, т. е. существуют 
таких последовательных графов.
Полагая
где
функцию (53.7) можно записать так:
т. е. в форме (53.3).
Рис. 253
УПРАЖНЕНИЯ
(см. скан)
