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

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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.

Kapcsolódó fogalmak[szerkesztés]

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 csúcs excentricitása alatt a é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 sugarán a csúcsok minimális excentricitását értjük: . Nem összefüggő gráfban megegyezés szerint végtelen.

Egy gráf vagy átmérőjén a csúcsok maximális excentricitását értjük; tehát a csúcspárok között fellépő legnagyobb távolság, avagy . 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 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 – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf sugarát, avagy olyan , melyre .

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

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

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]

Pszeudoperiferikus csúcsok keresési algoritmusa[szerkesztés]

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

Kapcsolódó szócikkek[szerkesztés]

Fordítás[szerkesztés]

Jegyzetek[szerkesztés]

  1. Bouttier, Jérémie (2003. július 1.). „Geodesic distance in planar graphs”. Nuclear Physics B 663 (3), 535–567. o. DOI:10.1016/S0550-3213(03)00355-9. (Hozzáférés ideje: 2008. április 23.) „By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces” 
  2. Weisstein, Eric W.: Graph Geodesic. MathWorld--A Wolfram Web Resource. Wolfram Research. (Hozzáférés: 2008. április 23.) „The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v”
  3. F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.
  4. Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104