Упражнения

5.1. Определить минимальные пути из вершины v₁ в вершину v₇, из вершины v₂ в вершину v₅ в орграфе, заданном матрицей смежности. Построить граф.

а) б)

А = А =

Определить количество минимальных путей.

5.2. Найти все кратчайшие пути из вершины v₁ во все остальные в орграфе:

А =

§ 6. Расстояние в графах

Пусть G = (V, X) – связный неориентированный граф.

v₁, v₂ – две его несовпадающие вершины.

Определение: Расстоянием между вершинами v_i и v_j называется длина кратчайшего (v_i , v_j) – маршрута. Обозначается ρ (v_i , v_j).

Введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

ρ (v_i , v_j) ≥ 0;
ρ (v_i , v_j) = 0 <=> v_i = v_j (если i = j);
ρ (v_i , v_j) = ρ (v_i , v_j) – симметричность;
ρ (v_i , v_j) ≤ ρ (v_i ,w) + ρ (w , v_j) – неравенство треугольника;
ρ (v_i , v_j) < ∞

Определение: Пусть G = (V, X). Если V = { v₁, v₂, …, v_n}, то матрицей расстояний называется матрица P = [ p _ij] порядка n, у которой:

p _ij = ρ(v_i,v_j) (i = 1,…, n; j = 1,…, n)

Замечание: P^T = P, т. е. матрица P симметрична.

Определение: Для фиксированной вершины v величина

е(v) = max {ρ(v,w) | wV} называется эксцентриситетом вершины v. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.

Если P – матрица расстояний, то эксцентриситет е(v_i) равен наибольшему из чисел, стоящих в i-й строке.

Определение: Диаметром графа G называется эксцентриситет, максимальный среди всех эксцентриситетов вершин.

Обозначается d(G). d(G) = max {е(v_i) / v_i V }.

Определение: Вершина v называется периферийной, если е(v) = d(G).

Определение: Минимальный из эксцентриситетов графа G называется его радиусом. Обозначается r(G), т. е. r(G) = min {е(v_i) | v_i V }.

Определение: Вершина v называется центральной, если е(v) = r(G).

Определение: Множество всех центральных вершин графа называeтся его центром.

Пример:

Составим матрицу расстояний P =

e(1) = 2, e(2) = 1, e(3) = 2. e(4) = 2, e(5) = 2, тогда

d(G) = 2. Периферийные вершины: 1, 3, 4, 5.

r(G) = 1, центр {2}. (центр может состоять из нескольких вершин).

Теорема: В полном графе K_n d(K_n) = r(K_n) = 1 (т. к. все различные вершины графа K_n смежны).

Задача нахождения центральных вершин возникает в практической деятельности людей.

Например, граф представляет собой сеть дорог, т. е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы (нагруженные).