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

gráfelméleti mennyiség
(Excentricitás (gráfelmélet) szócikkből átirányítva)

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ó fogalmakSzerkeszté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 algoritmusaSzerkeszté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ócikkekSzerkesztés

FordításSzerkesztés

  • 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 jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

JegyzetekSzerkeszté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