Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Нагруженные графы. Расстояния в нагруженном графе




Определение: Граф G = (V, X) (орграф Д = (V, X)) называется нагруженным, если на множестве ребер (дуг) определена некоторая функция l: X → R , которую часто называют весовойфункцией.

Таким образом, в нагруженном графе (нагруженном орграфе) каждому ребру (дуге) x X поставлено в соответствие некоторое действительное число l(x).


Значение l(x) называется длинойребра (дуги) x или весом ребра (дуги) x.

 

Пример:

l( v1, v2)=3

l( v2, v3)=2

l( v1, v3)=7

 

Информацию о длинах дуг (ребер) нагруженного орграфа (графа) можно представить в виде матрицы длин дуг (ребер).

Определение: Матрицей длин дуг (ребер)орграфа Д (графа G) называется квадратная матрица порядка n С= [сij], у которой каждый элемент сij определяется следующим образом:

Определение: Пусть дан нагруженный граф G = (V, X) (орграф Д = (V, X)).

Рассмотрим некоторый маршрут (путь) из вершины vi в вершину vj. Обозначим его П, а сумму длин входящих в него ребер (дуг) обозначим l(П).

l(П) называется длиной маршрута (пути) П в нагруженном графе (орграфе) или весом маршрута (пути).

Пример: Пусть П – маршрут из v1 в v3.

П1 = v1 v2 v3 П2 = v1 v3

l1) = 3 + 2 = 5 l(П2) = 7

Определение: Расстоянием в нагруженном графе (орграфе) (или взвешенным расстоянием) между вершинами vi и vj называется длина минимального маршрута (пути) из vi в vj.

Матрица взвешенных расстояний, взвешенные эксцентриситеты вершин, диаметр, радиус, центр нагруженного графа определяются аналогично определению данных понятий для ненагруженного графа.


Поделиться:

Дата добавления: 2015-01-29; просмотров: 213; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты