Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Взвешенные графы. Нахождение кратчайших маршрутов

Определение J^.26. Граф G называется взвешенным;, если каждому его ребру поставлено в соответствие число, называемое весом ребра.

Определение J±.21. Матрицей весов (п,т)-графа С называется квадратная матрица W = (wtJ) порядка п (г, j= 1,2,..., п), в которой Wij - вес ребра (щ, Vj) и wtJ = 0 или wtJ = ос, если пара (гщ Vj) не является ребром графа,

Заметим, что если пара (vi,Vj) не является ребром графа и гф], то, как правило, шр принимают равным ос, а диагональные элементы матрицы весов полагают равными 0, в случае отсутствия в графе соответствующих петель.

П р и м е р 4.12. Записать матрицу весов для графа, представленного на рис. 30.

Рис. 30

Легко видеть, что матрица весов для графа, изображенного па рис. 30, имеет вид

Во взвешенном графе для каждого маршрута можно определить его вес, т. е. сумму весов ребер, входящих в маршрут.

Определение 4-28. Расстоянием между двумя несовпадающими вершинами щ и Vj связного графа С называется длина, а для взвешенного графа - вес кратчайшего (гщг^-маршрута.

Заметим, что любой граф можно рассматривать как взвешенный, если каждому ребру приписать вес, равный 1. Ясно, что тогда расстояние между вершинами щ и Vj (иг ^ Vj) любого графа - это вес кратчайшего (щ, -маршрута.

Обозначим расстояние между вершинами щ, vj через р(щ, Vj). Положим, что p(vi,Vi) = 0. Введенное таким образом понятие расстояния удовлетворяет следующим свойствам:

  • 1) pvi,Vj)>0;
  • 2) p(vi,Vj) = 0 тогда и только тогда, когда i=j;
  • 3) p{Vi,Vj) = p{Vj,Vi)
  • 4) p(vi,Vj) <p{vi,Vk) + p(vk,vj) (неравенство треугольника). Определение J^.29. Матрицей расстояний называется матрица

P=(Pij) порядка п (i,j = 1,2,..., гг), в которой pij = p{vi,Vj).

Определение 4-30. Величина е{г) = max p(vi, Vj) называет-

ся эксцентриситетом вершины щ. Максимальный из всех эксцентриситетов называется диаметром графа G и обозначается d(G) = maxe(vi). Минимальный из всех эксцентриситетов называет-

Vi^zV

ся радиусом; графа G и обозначается r(G) = min е(щ).

Vi€V

Определение 4-31. Вершина v называется периферийной, если d(G) = e(v) и центральной, если r(G) = e(v). Совокупность центральных вершин называют центром графа.

П р и м е р 4.13. Составить матрицу расстояний, найти диаметр и радиус графа из примера 4.12 (рис. 30).

Вычислим расстояния между вершинами и запишем матрицу расстояний.

Найдем эксцентриситеты вершин: е(гц) = 2, е{гь) = 2, е(гц) = 3, е(гц) = 3. Значит, диаметр d(G) = 3, а радиус r(G) = 2. Вершины гц и гь являются центральными, а г>з и гц - периферийными.

Нахождение кратчайших маршрутов лежит в основе многих прикладных задач. Опишем алгоритм Дейкстры - один из алгоритмов нахождения кратчайших (щ, гл^-маршрутов во взвешенном графе G = (Vl Е) с матрицей весов W.

  • 1. Зададим строку Dl = {d,..., dln}- где =0, d.)=wih
  • 2. П о л ожи м Vi = Vi{vi}.
  • 3. Пусть на шаге к строка Dk и множество Vj- уже определены. Выберем вершину Vj G Vk, так, что dh = min dk.

J vi&Vk

4. Определим Vk+1 = Vk {vj }, Dk+l = {d,+1,..., dkn+1}, где

5. На шаге k = n — 1 строка Dn~l состоит из расстояний между вершиной Vi и остальными вершинами графа.

П р и мер 4.14. С помощью алгоритма Дейкстры определить эксцентриситет вершины v взвешенного графа с матрицей весов

Определим кратчайшие маршруты, соединяющие вершину v с остальными вершинами графа (рис. 31).

1. Vi = Vi{vi} = {v2,V3,V4,v5,Ve},/Г = {0,4, 00,00, 00,1}.

Рис. 31

2. Так как d) = min d = d = 1 соответствует вершине гу, то V> =

J Vi€Vi

= V {гу} = {гу, гу, гд, г^5}. Определяем D2. Так как гд, гу V2, то df = = fi]; =0, = rfg = 1.

Таким образом, ?) — {0,3, 00, ос, 6,1}.

3. Далее, ей = min df — dl — З соответствует вершине гу, то Уз =

J vieV2

= V3 {с-2} = {гу, гд5 гу}? Определяем /93. Так как гд, гу, гу^ТД то 3 =

= cff = 0, d% = do = 3; d,Q = dl = l.

Получим, D3 = {0,3,5, оо, 4,1}.

4. Теперь, сЙ = min df = d = 4, V% = Кз {^5} = {^з, гд}, Т>4 = {0,3,5,

J vteV.3

  • 6.4,1}.
  • 5. U 1-,Ы {г,}. Д5 = {0,3,5,6,4,1}.

Значения в строке D5 равны расстояниям от вершины гд до остальных вершин графа. Например, р(гддд) = 6. Кратчайшим (гд, гд)-маршрутом будет маршрут (гд, гу, гу, гу, гу, гд) • Эксцентриситет е(гд) = max р(г д, гд-) = 6.

Vj?V

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>