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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Для орієнтованого графа відстань між двома вершинами та визначається як довжина найкоротшого орієнтованого шляху з в за умови, що принаймні один такий шлях існує.[3] Зауважте, що на відміну від неорієнтованого графа, відстань не обов'язково збігається з , і можливі випадки, коли одна відстань визначена, а інша ні.

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

[ред. | ред. код]

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

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

Радіус графа — це мінімальний ексцентриситет будь-якої з вершин графа або, символьно, .

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

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

Зеленим позначені псевдопериферійні вершини. Діаметр графа 4.

Периферійна вершина графа діаметру  — це така вершина , що .

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

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

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

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

[ред. | ред. код]

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

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

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]
  1. Bouttier, Jérémie; Di Francesco,P.; Guitter, E. (July 2003). Geodesic distance in planar graphs. Nuclear Physics B. 663 (3): 535—567. doi:10.1016/S0550-3213(03)00355-9. Архів оригіналу за 4 жовтня 2008. Процитовано 23 квітня 2008. Кажучи відстань, тут ми маємо на увазі відстань по графу, а саме довжину найкоротшого шляху між, скажімо, двома заданими гранями
  2. Weisstein, Eric W. Graph Geodesic. 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. Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104