Центры и медианы графа

Примеры задач размещения

Задачи размещения. Поиск центров и медиан в графе

1. В небольшом городе с несколькими районами нужно разместить станцию скорой помощи. В каком районе нужно выбрать место для строительства, чтобы минимизировать время нахождения в пути машин скорой помощи до самого дальнего от станции района города?

2. Несколько небольших городов соединены сетью дорог. В каком городе нужно разместить станцию технической помощи, чтобы расстояние от нее до любого места возможной аварии на дороге было как можно меньше?

3. Где нужно построить телефонную станцию, чтобы минимизировать суммарную длину проложенного кабеля?

4. Где в городском районе нужно построить бомбоубежище, чтобы время на дорогу из любого дома района до бомбоубежища было как можно меньше?

Все эти задачи можно свести к поиску некоторой точки в ориентированном графе с заданными длинами дуг, для которой оптимизируется «наихудший вариант» – минимизируется длина наибольшего пути или сумма длин путей. Такие задачи называются минимаксными и минисуммными задачами размещения соответственно.

В дальнейшем будем рассматривать сильно связный ориентированный граф G(V, E) с p вершинами и q дугами, каждой дуге (i, j) которого поставлено в соответствие положительное число l(i, j) – длина дуги. Ребро означает две разнонаправленные дуги одинаковой длины. Будем считать, что если поделить дугу (ребро) некоторой точкой, то сумма длин получившихся отрезков равна длине ребра.

Определение. Расстоянием вершина – вершина (обозначение d_ij) называется длина кратчайшего пути от вершины i до вершины j. По определению положим, что d_ii = 0, i= 1 ,…, p. Числа d_ij заносятся в матрицу D, размерности , которая называется матрицей расстоянийвершина – вершина.

Построим матрицу D для графа на рис. 1. Матрица задана в табл. 1.

Определение. Внешним центром графа называется такая его вершина i, для которой минимально максимальное расстояние .

Итак, чтобы найти внешний центр, нужно отыскать

Рассмотрим граф на рис. 1 с матрицей D (табл.1)

; ;

Таблица 1

j i						∑
	13	11		7	16
			7
				7
∑			16

D =

; ;

; ;

Внешний центр графа – это вершина 5. В табл. 1 числа выделены жирным шрифтом.

Определение. Внутренним центром графа называется такая его вершина i, для которой минимально максимальное расстояние .

Итак, чтобы найти внутренний центр, нужно отыскать .

Для графа на рис. 1 имеем

; ;

; ;

; ;

В графе два внутренних центра – вершины 3 и 4. В табл.1 числа выделены курсивом с подчеркиванием.

Подчеркнем, что при поиске внешнего центра минимизируются максимальные пути из вершин, а при поиске внутреннего центра минимизируются максимальные пути до вершины.

Дата добавления: 2015-07-02