2.9. Последовательные графы в им

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

Пусть на орграфе без контуров задана порядковая функция, т.е. все вершины графа распределены по уровням Е₀, Е₁,…, Е_n.

Определение. Последовательным графом называется такой орграф без контуров, в котором множество дуг, исходящих из вершин уровня Е_i, совпадает с множеством дуг, входящих в вершины уровня Е_{i + 1}.

По определению последовательный граф всегда обладает порядковой функцией. Достоинства последовательного графа:

1. можно оптимизировать по частям;

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

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

Пример (продолжение предыдущего) (рис. 2.5).

Рис. 2.5

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