Определение 3.9.1.Взвешенный граф – это граф дугам, которого поставлены в соответствие веса, так что дуге (xi, xj) сопоставлено некоторое число c (xi, xj) = cij, называемое длиной (или весом, или стоимостью) дуги. Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1.
Определение 3.9.2. Длина пути во взвешенном графе - это сумма длин (весов) тех ребер, из которых состоит путь.
Определение 3.9.3. Расстояние между вершинами – это длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 24, равно 6.
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление