Программирование на языке Pascal

       

Взвешенные графы


Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 11.7, равно 6.


Рис. 11.7.  Взвешенный граф

N-периферия вершины v - это множество вершин, расстояние до каждой из которых (от вершины v) не меньше, чем N.

Таблица 11.3. Примеры взвешенных графов

ГрафВершиныВес вершиныРебра (дуги)Вес ребра (дуги)
ТаможниГосударстваПлощадь территорииНаличие наземной границыСтоимость получения визы
ПереездыГородаСтоимость ночевки в гостиницеДорогиДлина дороги
Супер-чайнвордСлова-Совпадение конца и начала слов(возможность "сцепить" слова)Длина пересекающихся частей
КартаГосударстваЦвет на картеНаличие общей границы-
СетьКомпьютеры-Сетевой кабельСтоимость кабеля



Содержание раздела