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

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

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

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

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

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

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

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