6.1. Задача размещения нескольких пунктов обслуживания
В разд. 3.1 была рассмотрена задача размещения одной больницы (или одного полицейского участка, или одного пожарного депо) в графе, представляющем реальную сеть дорог. Однако очень часто имеет место такая ситуация, когда одного пункта обслуживания недостаточно, поскольку он не в состоянии обслужить все поступающие вызовы, и тогда возникает задача о наилучшем размещении нескольких таких пунктов обслуживания. Эту задачу можно сформулировать так.
Найти наименьшее число пожарных депо (например) и такое их размещение, чтобы расстояние от каждого жилого района до ближайшего к нему пожарного депо не превышало наперед заданной величины. Если же число пожарных депо известно, то требуется разместить их так, чтобы было минимально возможным расстояние от любого района до ближайшего к нему депо.
Если предположить, что пожарные должны размещаться в вершинах соответствующего графа 
то задача будет состоять в нахождении 
-центров графа для 
до тех пор, пока число разделения 
-центра не станет меньше или равно заданному расстоянию. Полученное (последнее) значение числа 
будет наименьшим числом пожарных депо, а 
-центр — их оптимальным размещением, удовлетворяющим предъявляемым требованиям.
Алгоритм нахождения 
-центров является частным случаем алгоритма решения более общей задачи, состоящей в определении
-центров, располагающихся, вообще говоря, не в вершинах графа. Рассмотрение общего алгоритма поиска 
-центров мы отложим до разд. 8.5, пока не будет исследована соответствующая более общая задача.
