Нагруженные графы
Нагруженный граф − ориентированный граф D =(V, X), на множестве дуг которого определена некоторая функция , которую называют весовой функцией.
Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).
Рис. 5.
Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).
Величина l называется длиной пути.
Если выбрать веса равными 1, то придем к ненагруженному графу.
Путь в нагруженном ориентированном графе из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет наименьшую длину.
Аналогично определяется минимальный путь в нагруженном графе.
Введем матрицу длин дуг C (D)=[ cij ] порядка n, причем
Свойства минимальных путей в нагруженном ориентированном графе
1) Если для " дуги , то " минимальный путь (маршрут) является простой цепью;
2) если минимальный путь (маршрут) то для " i, j: путь (маршрут) тоже является минимальным;
3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).
Дата добавления: 2015-09-27 | Просмотры: 644 | Нарушение авторских прав
|