Взвешенные графы
Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.
Замечание: Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 11.7, равно 6.
Рис. 11.7. Взвешенный граф
N-периферия вершины v - это множество вершин, расстояние до каждой из которых (от вершины v) не меньше, чем N.
| Таможни | Государства | Площадь территории | Наличие наземной границы | Стоимость получения визы |
| Переезды | Города | Стоимость ночевки в гостинице | Дороги | Длина дороги |
| Супер-чайнворд | Слова | - | Совпадение конца и начала слов(возможность "сцепить" слова) | Длина пересекающихся частей |
| Карта | Государства | Цвет на карте | Наличие общей границы | - |
| Сеть | Компьютеры | - | Сетевой кабель | Стоимость кабеля |
