Відстань у графах
Нехай G = (V, X) - зв'язковий неорієнтований граф.
v1,v2 – дві його незбігаючі вершини.
Визначення:Відстаннюміжвершинамиvi таvj називається довжина найкоротшого (vi ,vj) – маршрут. Позначається ρ (vi,vj).
Введена таким чином відстань задовольняє наступним аксіомам метрики:
5) ρ (vi,vj) T = P, тобто матриця P симетрична.
Визначення: Для фіксованої вершиниvвеличина
е(v) = max v,w)wV> називаєтьсяексцентриситетомвершиниv. Таким чином, ексцентриситет вершини дорівнює відстані від цієї вершини до найбільш віддаленої від неї.
Якщо P - матриця відстаней, то ексцентриситет е(vi) дорівнює найбільшому з чисел, що стоять в i-му рядку.
Визначення:Діаметром графа G називається ексцентриситет, максимальний серед усіх ексцентриситетів вершин.
Позначається d(G). d(G) = max v i) /vi V >.
Визначення: Вершинаvназиваєтьсяпериферійною, якщо е(v) = d(G).
Визначення: Мінімальний з ексцентриситетів графа G називається йогорадіусом. Позначається r(G), тобто r(G) = min v i)vi V >.
Визначення: Вершинаvназиваєтьсяцентральною, якщо е(v) = r(G).
Визначення: Безліч всіх центральних вершин графа називається йогоцентром.
Складемо матрицю відстаней P =
e(1) = 2, e(2) = 1, e(3) = 2. e(4) = 2, e(5) = 2, тоді
d(G) = 2. Периферійні вершини: 1, 3, 4, 5.
r(G) = 1, центр . (Центр може складатися з декількох вершин).
Теорема : У повному графі Knd(Kn) = r(Kn) = 1 (бо всі різні вершини графа Kn суміжні).
Завдання перебування центральних вершин виникає у практичній діяльності людей.
Наприклад, граф є мережею доріг, т. е. вершини відповідають населеним пунктам, а ребра – дорогам з-поміж них. Потрібно оптимально розмістити лікарні, пункти обслуговування тощо. У таких ситуаціях оптимізація полягає у мінімізації відстані від місця обслуговування до найбільш віддаленого населеного пункту. Отже, місцями розміщення мають бути центральні вершини графа. Реальні завдання відрізняються від цієї ідеальної тим, що доводиться враховувати й інші обставини – відстані між населеними пунктами, вартість, час проїзду тощо. Для обліку цих параметрів використовуються зважені графи (навантажені).