Відстань (теорія графів)

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

Для орієнтованого графа відстань $d(u,v)$ між двома вершинами $u$ та $v$ визначається як довжина найкоротшого орієнтованого шляху з $u$ в $v$ за умови, що принаймні один такий шлях існує. Зауважте, що на відміну від неорієнтованого графа, відстань $d(u,v)$ не обов'язково збігається з $d(v,u)$, і можливі випадки, коли одна відстань визначена, а інша ні.

Пов'язані поняття

Метричний простір визначений на множині вершин за допомогою відстаней на графі називається метрикою графа. Множина вершин (не орієнтованого графа) і ця функція відстаней утворюють метричний простір тоді, і тільки тоді, коли граф є зв'язним.

Ексцентриситет $ϵ(v)$ вершини $v$ — це найбільша геодезична відстань між $v$ і будь-якою іншою вершиною.

Радіус $r$ графа — це мінімальний ексцентриситет будь-якої з вершин графа або, символьно, $r=\underset{v\in V}{\min }ϵ(v)$.

Діаметр $d$ графа — це максимальний ексцентриситет будь-якої з вершин графа. Тобто, $d$ — це найдовша відстань між будь-якою двійкою вершин, $d=\underset{v\in V}{\max }ϵ(v)$. Щоб знайти діаметр графа спочатку знайдіть найкоротші шляхи між кожною двійкою вершин графа. Найбільша довжина серед цих шляхів і є діаметром графа.

Центральна вершина графа — це вершина, ексцентриситет якої дорівнює радіусу графа, тобто $ϵ(v)=r$.

Файл:Pseudo-peripheral.png

Зеленим позначені псевдопериферійні вершини. Діаметр графа 4. $ϵ(9)=ϵ(4)<4,ϵ(8)=ϵ(4)<4$

Периферійна вершина графа діаметру $d$ — це така вершина $v$, що $ϵ(v)=d$.

Псевдопериферійна вершина $v$ має властивість, що для будь-якої вершини $u$, якщо $v$ є якнайдалі від $u$, тоді й $u$ є якнайдалі $v$. Формально, вершина u псевдопериферійна, якщо для кожної вершини v для якої $d(u,v)=ϵ(u)$ виконується $ϵ(u)=ϵ(v)$.

Розбиття вершин графа на підмножини згідно з їх відстанями від певної вершини називається Шаблон:Нп графа.

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

Алгоритм знаходження псевдопериферійних вершин

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

1. Обрати вершину $u$.
2. Серед усіх вершин, що є якнайдалі від $u$, нехай $v$ буде такою, що має мінімальний степінь.
3. Якщо $ϵ(v)>ϵ(u)$ тоді встановити $u=v$ і повторити крок 2, інакше $v$ — це псевдопериферійна вершина.

Див. також

• Матриця відстаней
• Резистивна відстань
• Центр графа