Застосування елементів теорії графів для рішення задачі розміщення пунктів обслуговування

Задачі розміщення пов'язані з вирішенням проблем оптимального розташування у певних регіонах пунктів обслуговування, таких як: торговельні центри, станції техобслуговування, автозаправні станції, пости пожежної охорони, лікарні, туристичні центри, склади, пошти, готелі і тому подібне. Математична структура таких задач визначається конфігурацією області припустимих точок розміщення і способом оцінки якості розміщення. Внаслідок цього існує багато різноманітних задач розміщення, що стосуються різних сфер знань і у технічній літературі пропонується чимало методів їх розв'язання.

Для того, щоб формулювати і розв'язувати задачі про розміщення, необхідно ввести нові поняття теорії графів:

  1. центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої від неї вершини є мінімальною.
  2. головним центром графа називається будь-яка його вершина, відстань від якої до найвіддаленішої точки на ребрах графа є мінімальною.
  3. абсолютним центром графа називається будь-яка точка на ребрі, відстань від якої до найвіддаленішої вершини графа є мінімальною.
  4. головним абсолютним центром графа називається будь-яка точка, відстань від якої до найвіддаленішої точки є мінімальною.
  5. медіаною графа називається точка, в якій сума відстаней до усіх вершин графа є мінімальною (аналогічно центрам можна ввести поняття головної, абсолютної і головної абсолютної медіани).

При розв'язанні задач на знаходження розміщення центрів обслуговування слід домовитися про область, у якій їх можна розміщувати. Обмежимося тільки тими задачами, для яких областю припустимих точок розміщення центрів обслуговування є деякий граф. Центри, в даному випадку, можуть розташовуватися тільки у вершинах та ребрах графа і ніде більше.

Читати повністю