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

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

Для орієнтованого графа відстань ${\displaystyle d(u,v)}$ між двома вершинами ${\displaystyle u}$ та ${\displaystyle v}$ визначається як довжина найкоротшого орієнтованого шляху з ${\displaystyle u}$ в ${\displaystyle v}$ за умови, що принаймні один такий шлях існує.^[3] Зауважте, що на відміну від неорієнтованого графа, відстань ${\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}$.

Периферійна вершина графа діаметру ${\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] графа.

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

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

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

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

Див. також[ред. | ред. код]

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

Примітки[ред. | ред. код]