Távolság (gráfelmélet)
gráfelméleti mennyiség / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén két csúcs távolsága alatt rendszerint az őket összekötő legrövidebb útban (geodézikus vonalon) található élek száma értendő. Ezt geodetikus vagy geodézikus távolságnak is nevezik.[1] Látható, hogy két csúcs között több legrövidebb út is létezhet.[2] Ha a két csúcs között nincs út, például mert a gráf két különböző összefüggő komponensébe tartoznak, akkor megegyezés szerint a csúcsok távolságát végtelennek tekintjük.
Irányított gráfoknál az és
közötti
távolság az
-ból
-be irányított éleken vezető legrövidebb út éleinek száma, feltéve hogy ilyen út létezik.[3] Látható, hogy az irányítatlan gráfokkal ellentétben a
értéke nem feltétlenül egyezik meg
értékével, és még az is előfordulhat, hogy az egyiknek létezik az értéke, a másiknak pedig nem.