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