Odległość (teoria grafów)

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^[1]^[2]. 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ż

Przypisy

↑ Jacek MJ.M. Wojciechowski Jacek MJ.M., KrzysztofK. Pieńkosz KrzysztofK., Grafy i sieci, Warszawa: Wydawnictwo Naukowe PWN, 2013, s. 65, ISBN 978-83-01-17436-1, OCLC 863114458 .
↑ Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 8. ISBN 0-387-95014-1.

[p1-1] Jacek MJ.M. Wojciechowski Jacek MJ.M., KrzysztofK. Pieńkosz KrzysztofK., Grafy i sieci, Warszawa: Wydawnictwo Naukowe PWN, 2013, s. 65, ISBN 978-83-01-17436-1, OCLC 863114458 .

[2] Reinhard Diestel: Graph Theory. Nowy Jork: 2000, s. 8. ISBN 0-387-95014-1.

[1]

[2]