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

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

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

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

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

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

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

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

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

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

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

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

Розбиття вершин графа на підмножини згідно з їх відстанями від певної вершини називається ^[en] графа.

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

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

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

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

Див. також

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

Примітки

1. Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). . Nuclear Physics B. 663 (3): 535—567. doi:10.1016/S0550-3213(03)00355-9. Архів оригіналу за 4 жовтня 2008. Процитовано 23 квітня 2008. Кажучи відстань, тут ми маємо на увазі відстань по графу, а саме довжину найкоротшого шляху між, скажімо, двома заданими гранями
2. . MathWorld--A Wolfram Web Resource. Wolfram Research. Архів оригіналу за 23 квітня 2008. Процитовано 23 квітня 2008. The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v
3. F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
4. , Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104