|
A [[matematika]], azon belül a [[gráfelmélet]] területén két [[csúcs (gráfelmélet)|csúcs]] '''távolsága''' alatt rendszerint az őket összekötő [[legrövidebb út probléma|legrövidebb útban]] (geodézikus vonalon) található [[él (gráfelmélet)|élek]] száma értendő. Ezt '''geodetikus''' vagy '''geodézikus távolságnak''' is nevezik.<ref>{{cite journal |last=Bouttier |first=Jérémie |author2=Di Francesco,P. |author3=Guitter, E. |date=July 2003 |title=Geodesic distance in planar graphs |journal= Nuclear Physics B|volume=663 |issue=3 |pages=535–567 |url=http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TVC-48KW72R-1&_user=3742306&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000061256&_version=1&_urlVersion=0&_userid=3742306&md5=86dd4de63373a7e72d23d16840947661
|accessdate= 2008-04-23 |quote=By distance we mean here geodesic distance along the graph, namely the length of any shortest path between say two given faces |doi=10.1016/S0550-3213(03)00355-9}}</ref> Látható, hogy két csúcs között több legrövidebb út is létezhet.<ref>{{cite web |url=http://mathworld.wolfram.com/GraphGeodesic.html |title=Graph Geodesic |accessdate= 2008-04-23
|last=Weisstein |first=Eric W. |authorlink=Eric W. Weisstein |work=MathWorld--A Wolfram Web Resource |publisher= Wolfram Research |quote=The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v}}</ref> 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 (gráfelmélet)|összefüggő komponensébe]] tartoznak, akkor megegyezés szerint a csúcsok távolságát végtelennek tekintjük.[[Irányított gráf|Irány]]
[[Irányított gráf]]oknál az <math>u</math> és <math>v</math> közötti <math>d(u,v)</math> távolság az <math>u</math>-ból <math>v</math>-be irányított éleken vezető legrövidebb út éleinek száma, feltéve hogy ilyen út létezik.<ref>F. Harary, Graph Theory, Addison-Wesley, 1969, p.199.</ref> Látható, hogy az irányítatlan gráfokkal ellentétben a <math>d(u,v)</math> értéke nem feltétlenül egyezik meg <math>d(v,u)</math> é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őség (gráfelmélet)|összefüggő]].
Egy <math>v</math> csúcs <math>\epsilon(v)</math> '''excentricitása''' alatt a <math>v</math> é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 <math>r</math> '''sugarán''' a csúcsok minimális excentricitását értjük: <math>r = \min_{v \in V} \epsilon(v)</math>. Nem összefüggő gráfban megegyezés szerint végtelen.
Egy gráf <math>d</math> vagy <math>diam</math> '''[[átmérő (gráfelmélet)|átmérőjén]]''' a csúcsok maximális excentricitását értjük; tehát <math>d</math> a csúcspárok között fellépő legnagyobb távolság, avagy <math>d = \max_{v \in V}\epsilon(v)</math>. Az átmérő megkereséséhez meg kell keresni az összes csúcspár közötti [[legrövidebb út probléma|legrövidebb utakat]]. Ezek között a legnagyobb hosszúságú a gráf átmérője.
Egy gráfban '''[[átlagos úthossz]]on''' a csúcspárok közötti távolságok (legrövidebb úthosszak) [[átlag]]a értendő.
Egy <math>r</math> sugarú gráf '''centrális csúcsa''', '''középponti csúcsa''' vagy egy'''ontja''' ''(central vertex)'' egy olyan csúcs, aminek az excentricitása éppen <math>r</math> – tehát ez egy olyan csúcs, ami éppen megvalósítja a gráf sugarát, avagteEz a ző algoritmussal egyszerűen megtalálható:
# Az <math>u</math>-tól lehető legmesszebb lévő csúcsok közül válasszuképéssel, egudoperifaynk.
==Kaóik[[Közöttiség-központiság|özöttiég-központiság]]==
* [[Centralitás]] ([[központiság|köz]]
[[Kategória:Gráfelmélet]]
| 