АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Нагруженные графы

Нагруженный граф − ориентированный граф D =(V, X), на множестве дуг которого определена некоторая функция , которую называют весовой функцией.

Цифра над дугой (см. рис. 5)− вес дуги (цена дуги).

Рис. 5.

Обозначения: для любого пути П нагруженного ориентированного графа D через l (П) сумму длин дуг, входящих в путь П. (Каждая дуга считается столько раз, сколько она входит в путь П).

Величина l называется длиной пути.

Если выбрать веса равными 1, то придем к ненагруженному графу.

Путь в нагруженном ориентированном графе из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет наименьшую длину.

Аналогично определяется минимальный путь в нагруженном графе.

Введем матрицу длин дуг C (D)=[ c_ij ] порядка n, причем

Свойства минимальных путей в нагруженном ориентированном графе

1) Если для " дуги , то " минимальный путь (маршрут) является простой цепью;

2) если минимальный путь (маршрут) то для " i, j: путь (маршрут) тоже является минимальным;

3) если − минимальный путь (маршрут) среди путей (маршрутов) из v в w, содержащих не более k +1 дуг (ребер), то − минимальный путь (маршрут) из v в u среди путей (маршрутов), содержащих не более k дуг (ребер).

Дата добавления: 2015-09-27 | Просмотры: 660 | Нарушение авторских прав