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