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 é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.F. Harary, Graph Theory, Addison-Wesley, 1969, p.199. 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 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.Øystein Ore, Theory of graphs [3rd ed., 1967], Colloquium Publications, American Mathematical Society, p. 104
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ó:
Válasszunk egy tetszőleges csúcsot. Az -tól lehető legmesszebb lévő csúcsok közül válasszuk -nek a minimális fokszámút. Ha , akkor legyen és folytassuk a második lépéssel, egyébként 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
Jegyzetek
Kategória:Gráfelmélet