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

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

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

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

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

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

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

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

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

Відстань від вершини до точки на ребрі графа

Зауважимо, що сума цих відстаней завжди дорівнює . Звідки випливає, що:

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

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

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

Знаходження головного центру графа — приклад:

Знайти головний центр графа зображеного на рисунку нижче. Зауважимо, що ребра даного графа пронумеровані у наступному порядку: .

Зображення графа для розглядуваної задачі

Отже, скориставшись отриманою в прикладі, який ми розглядали при знаходженні центру графа матрицею відстаней вершина — вершина  (міститься за посиланням «задача розміщення підприємств») і довжинами ребер, наведеними на рисунку, за допомогою рівностей (1) та (2), розрахуємо елементи матриці :

Після цього, для кожного рядка матриці , визначаємо елемент що містить максимальне значення:

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

Блок-схема алгоритму знаходження головного центру графа

Головний центр графа блок-схема

Матеріал був корисним, поділись в соціальних мережах:
Якщо тобі сподобалась дана тема, залиш свій коментар