Оптимизация пути в графах без контуров

Числовые функции графа

Рассмотрим 2 вида числовой функции:

· числовая функция на вершинах графа.

· числовая функция на рёбрах графа.

Если введена числовая функция на вершинах графа, то каждой вершине ставится в соответствие какое-то число.

Если введена числовая функция на рёбрах графа, то каждому ребру ставится в соответствие какое-то число.

Числовая функция на вершинах графа обозначается l, на дугах - m.

Максимальным (минимальным) путём через вершины графа называется путь, с максимальным (минимальным) значением числовой функции на его вершинах.

Максимальным (минимальным) путём через дуги графа называется путь, с максимальным (минимальным) значением числовой функции на его дугах.

Подпутём называется отрезок данного пути.

Теорема оптимальности 1. Если на графе G=(X,s), с порядковой функцией k=O(x_i) и числовой функцией l_i=j(x_i) задан максимальный (минимальный) путь через вершины между вершинами xm_i и xs_l, принадлежащими соответственно уровням m и s, то его подпуть между вершинами xn_j и xr_k, принадлежащими соответственно уровням n и r при условии s³r>n³m также максимален (минимален).

Дата добавления: 2015-01-03