§ 51. Оптимизация пути в графе без контуров. Теоремы оптимальности

Рассмотрим граф без контуров и его порядковую функцию принимая за начальный уровень подмножество таких вершин что -Зададимся также функцией

Теорема оптимальности Пусть задан максимальный (минимальный) путь через вершины между вершинами принадлежащими соответственно уровням Тогда его подпуть между вершинами принадлежащими соответственно уровням также максимален (минимален).

Доказательство. Пусть путь с максимальным значением (X отсутствует, если дуга). Предположим, что значение подпути не максимально. Тогда существует подпуть со значением, большим указанного. Но это противоречит максимальности заданного пути между Для путей с минимальным значением доказательство проводится таким же образом.

Пример (см. рис. 236, закон композиции — сложение). Легко убедиться, что путь между вершинами максимальный (со значением 44) и что его подпуть (со значением 31) между вершинами также максимальный,

Теорема оптимальности II. Пусть задан максимальный (минимальный) путь через дуги между вершинами принадлежащими соответственно уровням

Рис. 236.

Тогда его подпуть между вершинами принадлежащими соответственно уровням также максимален (минимален).

Доказательство аналогично доказательству теоремы I.

Рис. 237.

Пример (см. рис. 237, закон композиции — сложение). Легко убедиться, что путь между вершинами максимальный (со значением 23) и что его подпуть (со значением 15) также максимален,