2. Метрические характеристики неориентированного графа

Пусть G(V,X) – псевдограф и пусть вершины v и w (vw) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vV; d(v, w) = , если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний C_n² .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа: d(G) = maxd(v, w).

v, wV

Эксцентриситет (максимальное удаление) вершины: r(v) = maxd(v, w);

vV

Радиус графа : r(G) = min r(v);

vV

Центр графа: любая вершина vV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин , радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С₅² = 5!/3!2! = 10: d(v₁, v₂) =1, d(v₁, v₃) = 2, d(v₁, v₄) = 2, d(v₁, v₅) = 3, d(v₂, v₃) = 1, d(v₂, v₄) = 1, d(v₂, v₅) = 2, d(v₃, v₄) = 1, d(v₃, v₅) = 2, d(v₄, v₅) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v₁) = 3, r(v₂) = 2, r(v₃) = 2, r(v₄) = 2, r(v₅) = 3.

Радиус графа r(G) = 2.

Центры графа v₂, v₃, v₄ .

3. Минимальные маршруты в нагруженных графах

Граф G(V, X) называется нагруженным, если на множестве ребер графа задана функция, называемая весовой, которая ставит в соответствие каждому ребру х Х графа некоторое число l(x). Значение l(x) называется длиной дуги.

Величине l(x) можно придать разный смысл: затраты на транспортировку, время проезда, расстояние между пунктами, расход бензина и т.д.

Сумма длин ребер, входящих в маршрут, называется длиной маршрута.

Заметим, что если для всех х  Х l(x) = 1, то граф можно рассматривать как ненагруженный.

Маршрут в графе G(V, X) из вершины v в вершину w (vw), называется минимальным, если он имеет минимальную длину среди всех маршрутов в графе G(V, X) из вершины v в вершину w.

Ограничимся графами, для которых l(x)>0.

При поиске минимального маршрута в нагруженном графе с l(x)>0

воспользуемся таким же утверждением, что и для ненагруженного графа, а именно:

любой минимальный маршрут является простой цепью.

Рассмотрим теперь задачу поиска минимального маршрута в нагруженном графе.

Пусть граф G(V,X) нагруженный, число вершин n  2, необходимо построить минимальный маршрут из v₁ в v_n.

Приведем алгоритм.

Шаг 1. Каждой вершине присвоить индекс (v_i): (v₁) = 0, (v_i) = , i  1. окрасить вершину v₁ и положить v = v₁.

Шаг 2. Для каждой неокрашенной вершины v_j изменить индекс по правилу:

(v_j) = min {(v_j), (v) + l(v, v_j)}.

Окрасить ту из вершин, для которой (v_j) окажется наименьшим.. окрасить также ребро, ведущее в выбранную на данном шаге вершину v_j . Положить v = v_j.

Шаг 3. Если v = v_j , закончить процедуру, так как кратчайший маршрут из v₁ в v_n . если v  v_n , то перейти к шагу 2.

Замечание. Шаг 2 невозможен, если все (v_j)= . В этом случае вершина v_n недостижима.

Применим изложенный алгоритм к заданному диаграммой графу. Найдем в нем кратчайший маршрут из v₁ в v₆.

Шаг 1. Окрасим вершину v₁ . Присвоим вершинам индексы: (v₁) =0, (v₂) = (v₃)=…= (v_n)=. Полагаем v₁ = v.

Шаг 2.

(v₂) = min {, 0+4} = 4,

(v₃) = min {, 0+7} = 7,

(v₄) = min {, 0+3} = 3,

(v₅) = min {, 0+} = ,

(v₆) = min {, 0+} = .

Окрашиваем вершину v₄ и ребро {v₁, v₄}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₄.

Шаг 2.

(v₂) = min {4, 3+} = 4,

(v₃) = min {7, 3+} = 7,

(v₅) = min {, 3+3} = 6,

(v₆) = min {, 3+} = .

Окрашиваем вершину v₂ и ребро {v₁, v₂}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₂.

Шаг 2.

(v₃) = min {7, 4+3} = 7,

(v₅) = min {6, 4+2} = 6,

(v₆) = min {, 4+} = .

Окрашиваем вершину v₅ и ребро {v₄, v₅}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₅.

Шаг 2.

(v₃) = min {7, 6+} = 7,

(v₆) = min {, 6+2} = 8.

Окрашиваем вершину v₃ и ребро {v₁, v₃}.

Шаг 3. Так как вершина v₆ не окрашена, выполняем шаг 2, полагая v = v₃.

Шаг 2.

(v₆) = min {8, 7+2} = 8.

Окрашиваем вершину v₆ и ребро {v₅, v₆}.

Так как вершина v₆ окрашена, то работу прекращаем. Получили минимальный маршрут v₁ v₄ v₅ v₆ , длина которого равна 8 .

Заметим, что это в данном случае не единственный для вершин v₁ и v₆ минимальный маршрут, т.к. в алгоритме имелась возможность окрасить вместо ребра {v₄, v₅} ребро {v₂, v₅}, тогда бы получили другой маршрут той же длины.