Odległość między dwoma wierzchołkami definiuje się w teorii grafów jako liczbę krawędzi w najkrótszej ścieżce, łączącej rozpatrywane wierzchołki. W przypadku, gdy nie istnieje taka ścieżka, tj. gdy wierzchołki z danej pary należą do odrębnych spójnych składowych jednego grafu niespójnego, odległość z definicji równa się nieskończoności. W ten sposób zdefiniowana odległość może zostać znaleziona poprzez zastosowanie algorytmu przeszukiwania wszerz (BFS) bądź algorytmu Dijkstry.
Graf z tak określoną funkcją odległości jest przestrzenią metryczną.
W szczególnym przypadku grafu pełnego odległość między dowolną parą wierzchołków jest równa 1.
Zobacz też Średnica grafu Promień grafu Acentryczność
Przypisy
Kategoria:Teoria grafów