Постановка задачи оптимизации пути в графах без контуров

Задан граф без контуров с порядковой функцией и одной из числовых. Найти путь из вершины x_i в вершину x_j с минимальным (максимальным) значением числовой функции. Вершины x_i и x_j единственны в своих уровнях.

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

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

2. Выбор минимального пути после разметки осуществляется одним из двух способов:

а). Начинаем выбор с вершины x_i, помеченной меткой "0". Выбираем далее вершины x_j в соответствии с рисунком:

В нашем случае

б). Начинаем выбор с конечной вершины пути. Выбираем далее вершины x_i в соответствии с рисунком:

В нашем случае:

Обоснованием предложенного алгоритма являются теоремы оптимальности.

Условие применимости - наличие у графа порядковой функции.

В описанном алгоритме рассматривался оптимальный путь между начальным и конечным уровнями с единственной вершиной.

Рассмотрим теперь случай, когда начальный и/или конечный уровни содержат более одной вершины.

Общая постановка задачи:

Задан граф без контуров с порядковой функцией и одной из числовых функций. Найти оптимальный путь между уровнями Е_n и Е_r, причём r>n.

Решение. Ищется предложенным ранее способом с некоторой модификацией. Для этого на графе вводятся дополнительные две вершины - вход E и выход S. Вход Е соединяется дугами со всеми вершинами уровня Е_n. При этом каждой дуге приписывается значение "0". Все вершины уровня Е_r соединяются дугами с выходом S, при этом каждой дуге также приписывается значение "0".

Затем граф размечается и ищется минимальный путь из Е в S.