Главная > Математика > Теория графов. Алгоритмический подход
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.1. Задача размещения нескольких пунктов обслуживания

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

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

Если предположить, что пожарные должны размещаться в вершинах соответствующего графа то задача будет состоять в нахождении -центров графа для до тех пор, пока число разделения -центра не станет меньше или равно заданному расстоянию. Полученное (последнее) значение числа будет наименьшим числом пожарных депо, а -центр — их оптимальным размещением, удовлетворяющим предъявляемым требованиям.

Алгоритм нахождения -центров является частным случаем алгоритма решения более общей задачи, состоящей в определении

-центров, располагающихся, вообще говоря, не в вершинах графа. Рассмотрение общего алгоритма поиска -центров мы отложим до разд. 8.5, пока не будет исследована соответствующая более общая задача.

<< Предыдущий параграф Следующий параграф >>
Оглавление