Távolság (gráfelmélet)

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 ${\displaystyle u}$ és ${\displaystyle v}$ közötti ${\displaystyle d(u,v)}$ távolság az ${\displaystyle u}$-ból ${\displaystyle v}$-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 ${\displaystyle d(u,v)}$ értéke nem feltétlenül egyezik meg ${\displaystyle d(v,u)}$ értékével, és még az is előfordulhat, hogy az egyiknek létezik az értéke, a másiknak pedig nem.

Egy gráfmetrika a gráf csúcsainak halmaza fölött definiált metrikus tér, melynek metrikája a gráf csúcsai közötti távolság. Egy irányítatlan gráf csúcshalmaza és a gráf távolságfüggvénye pontosan akkor alkotnak metrikus teret, ha a gráf összefüggő.

Egy ${\displaystyle v}$ csúcs ${\displaystyle \epsilon (v)}$ excentricitása alatt a ${\displaystyle v}$ és a gráf bármely másik csúcsa között mért távolságok közül a maximálisat értjük. Köznyelven, mennyire van távol a tőle legtávolabbi csúcstól a gráfban.

Egy gráf ${\displaystyle r}$ sugarán a csúcsok minimális excentricitását értjük: ${\displaystyle r=\min _{v\in V}\epsilon (v)}$. Nem összefüggő gráfban megegyezés szerint végtelen.

Egy gráf ${\displaystyle d}$ vagy ${\displaystyle diam}$ átmérőjén a csúcsok maximális excentricitását értjük; tehát ${\displaystyle d}$ a csúcspárok között fellépő legnagyobb távolság, avagy ${\displaystyle d=\max _{v\in V}\epsilon (v)}$. Az átmérő megkereséséhez meg kell keresni az összes csúcspár közötti legrövidebb utakat. Ezek között a legnagyobb hosszúságú a gráf átmérője.

Egy gráfban átlagos úthosszon a csúcspárok közötti távolságok (legrövidebb úthosszak) átlaga értendő.

Egy ${\displaystyle r}$ sugarú gráf centrális csúcsa, középponti csúcsa vagy egyszerűen középpontja (central vertex) egy olyan csúcs, aminek az excentricitása éppen ${\displaystyle r}$ – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf sugarát, avagy olyan ${\displaystyle v}$, melyre ${\displaystyle \epsilon (v)=r}$.

Egy ${\displaystyle d}$ átmérőjű gráf periferikus csúcsa (peripheral vertex) egy olyan csúcs, melynek valamely csúcstól való távolsága éppen ${\displaystyle d}$ – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf átmérőjét. Formálisan ${\displaystyle v}$ periferikus, ha ${\displaystyle \epsilon (v)=d}$.

Egy gráf ${\displaystyle v}$ pszeudoperiferikus csúcsa (pseudo-peripheral vertex) olyan tulajdonságú csúcs, hogy a gráf bármely ${\displaystyle u}$ csúcsára igaz, hogy ha ${\displaystyle v}$ a lehető legnagyobb távolságra van ${\displaystyle u}$-tól, akkor ${\displaystyle u}$ is a lehető legtávolabb van ${\displaystyle v}$-től. Formálisan, egy u csúcs akkor pszeudoperiferikus, ha minden v-re, ahol ${\displaystyle d(u,v)=\epsilon (u)}$, igaz, hogy ${\displaystyle \epsilon (u)=\epsilon (v)}$.

Egy gráf csúcsainak olyan felbontását, ahol egy kiindulási vagy gyökércsúcstól való távolság nagysága szerint soroljuk a csúcsokat részhalmazokba, a gráf szintekre bontásának vagy szintfelbontásának nevezzük (level structure).

Geodézikus gráf vagy geodetikus gráf (geodetic graph) az olyan gráf, melyben bármely csúcspárt egyetlen legrövidebb út köt össze. Például minden fa geodézikus.^[4]

A ritka mátrixokat kezelő algoritmusoknak gyakran szükségük van egy magas excentricitású kiindulási csúcsra. Egy periferikus csúcs tökéletes lenne, annak megkeresése azonban magas futásidejű feladat. A legtöbb esetben elegendő egy pszeudoperiferikus kiindulási csúcsot keresni. Ez a következő algoritmussal egyszerűen megtalálható:

1. Válasszunk egy tetszőleges ${\displaystyle u}$ csúcsot.
2. Az ${\displaystyle u}$-tól lehető legmesszebb lévő csúcsok közül válasszuk ${\displaystyle v}$-nek a minimális fokszámút.
3. Ha ${\displaystyle \epsilon (v)>\epsilon (u)}$, akkor legyen ${\displaystyle u=v}$ és folytassuk a második lépéssel, egyébként ${\displaystyle v}$ pszeudoperiferikus és kész vagyunk.

• Távolságmátrix
• Ellenállás-távolság
• Közöttiség-központiság
• Centralitás (központiság)
• Közelségi centralitás
• Fokszám-átmérő probléma irányítatlan és irányított gráfokra

• Ez a szócikk részben vagy egészben a Distance (graph theory) című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.