Знаходження головного центру графа

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

Розглянемо далі один із способів рішення задач на знаходження головного центру. Але, для початку, введемо деякі визначення, необхідні для опису точок на ребрах та деяких відстаней в графі.

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

Головний центр графа

Розміщення точки на ребрі графа

Таким чином, чверть-точкою ребра  є точка, віддалена від вершини  на довжини ребра . Нуль-точкою ребра  являється вершина , а одиничною - вершина . Отже, вершини графа також можуть розглядатися як точки його ребер. Точки ребер, які не є вершинами, називаються внутрішніми. Будь-яка точка ребра повинна бути або внутрішньою, або вершиною. Нехай через позначається множина всіх точок графа . Таким чином, різниця являється множиною всіх його внутрішніх точок.

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

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

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

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

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

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

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