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. Látható, hogy két csúcs között több legrövidebb út is létezhet. 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 $u$ és $v$ közötti $d(u,v)$ távolság az $u$-ból $v$-be irányított éleken vezető legrövidebb út éleinek száma, feltéve hogy ilyen út létezik. Látható, hogy az irányítatlan gráfokkal ellentétben a $d(u,v)$ értéke nem feltétlenül egyezik meg $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.

Kapcsolódó fogalmak

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 $v$ csúcs $ϵ(v)$ excentricitása alatt a $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 $r$ sugarán a csúcsok minimális excentricitását értjük: $r=\underset{v\in V}{\min }ϵ(v)$. Nem összefüggő gráfban megegyezés szerint végtelen.

Egy gráf $d$ vagy $diam$ átmérőjén a csúcsok maximális excentricitását értjük; tehát $d$ a csúcspárok között fellépő legnagyobb távolság, avagy $d=\underset{v\in V}{\max }ϵ(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 $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 $r$ – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf sugarát, avagy olyan $v$, melyre $ϵ(v)=r$.

Egy $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 $d$ – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf átmérőjét. Formálisan $v$ periferikus, ha $ϵ(v)=d$.

Egy gráf $v$ pszeudoperiferikus csúcsa (pseudo-peripheral vertex) olyan tulajdonságú csúcs, hogy a gráf bármely $u$ csúcsára igaz, hogy ha $v$ a lehető legnagyobb távolságra van $u$-tól, akkor $u$ is a lehető legtávolabb van $v$-től. Formálisan, egy u csúcs akkor pszeudoperiferikus, ha minden v-re, ahol $d(u,v)=ϵ(u)$, igaz, hogy $ϵ(u)=ϵ(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.

Pszeudoperiferikus csúcsok keresési algoritmusa

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 $u$ csúcsot.
2. Az $u$-tól lehető legmesszebb lévő csúcsok közül válasszuk $v$-nek a minimális fokszámút.
3. Ha $ϵ(v)>ϵ(u)$, akkor legyen $u=v$ és folytassuk a második lépéssel, egyébként $v$ pszeudoperiferikus és kész vagyunk.

Kapcsolódó szócikkek

• 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

Fordítás

• Sablon:Fordítás