§ 50. Числовая функция на графе

Числовая функция на вершинах графа. Пусть задан граф Говорят, что на вершинах графа реализуется числовая функция, если каждой вершине ставится в соответствие число из некоторого множества

Например, для графа на рис. 226 имеем

Значение пути через вершины. Пусть на задан внутренний бинарный ассоциативный закон.

Значением пути через вершины называют число где и записывают

Рис. 226.

Рис. 227.

Например, для графа на рис. 226 и множества если принять за закон композиции сложение, имеем

При рассмотрении значения контура всегда фиксируется начало (во избежание многозначности).

Максимальный (минимальный) путь через вершины. Обозначим через подмножество путей графа с некоторым свойством Максимальным (минимальным) путем через вершины, принадлежащим назовем путь с максимальным (минимальным) значением А. Очевидно, что таких путей может быть несколько.

Например, пусть для графа на рис. 227 функция такова:

закон композиции — сложение, а свойство — «быть элементарным путем длины 3 с началом в В». В силу (43.3)

Пути максимальные, а путь минимальный.

Числовая функция на дугах графа. Пусть задан граф Говорят, что на дугах графа реализуется числовая функция, если каждой дуге ставится в соответствие число из некоторого множества

Рис. 228.

Рис. 229

Например, для графа на рис. 228 имеем

Значение пути через дуги. Пусть на задан внутренний бинарный ассоциативный закон . Значением пути через дуги называют число где и записывают

Например, для графа на рис. 228 и множества если принять за закон композиции умножение, имеем

Максимальный (минимальный) путь через дуги. Обозначим через множество путей графа с некоторым свойством Максимальным (минимальным) путем через дуги, принадлежащим назовем путь с максимальным (минимальным) значением

Например, пусть для графа на рис. 229 (функция указана там же) свойство — «быть гамильтоновым путем», а закон композиции — сложение.

(кликните для просмотра скана)

Из рис. 207 имеем

Гамильтонов путь максимальный, а путь минимальный.

Рис. 235.

Замечания. 1) В задачах оптимизации рассматриваются также числовые функции, определенные на других упорядоченных множествах.

2) В графе без контуров от значений на дугах можно перейти к значениям на вершинах и обратно. Например, на рис. 231 показано, как от графа на рис. 230 со значениями, приписанными ребрам, перейти к графу на рис. 232 со значениями, приписанными вершинам, а на рис. 234 показано, как от графа на рис. 233 со значениями, приписанными вершинам, перейти к графу на рис. 235 со значениями, приписанными дугам.

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

Подпуть. Подпутем называют отрезок данного пути. Например, для графа на рис. подпуть пути —подпуть пути подпуть пути .

УПРАЖНЕНИЯ

(см. скан)

(см. скан)