Átlagos távolság

A Wikipédiából, a szabad enciklopédiából

Az átlagos távolság vagy átlagos úthossz a gráfelméletben a pontpárok közötti legrövidebb úthosszak átlaga. A fokszámeloszlás és a klaszterezettség mellett az egyik legfontosabb mérőszám a hálózati topológiában. Az átlagos úthossz mutatja, hogy mennyire hatékony egy hálózat, például hány csomóponton kell áthaladnia egy üzenetnek, vagy mennyi veszteséggel képes áramot közvetíteni egy elektromos hálózat.

Nem összekeverendő az átmérővel, ami a pontpárok közötti legrövidebb úthosszak maximuma.

Számos, a gyakorlatban előforduló hálózatnál, mint például az internet, vagy az ismeretségi hálózatok, az átlagos úthossz viszonylag kicsi, a csúcsok számának logaritmusával arányos. Ez a kis átlagos úthossz a kis-világ tulajdonság egyik feltétele.

Példa[szerkesztés | forrásszöveg szerkesztése]

A példához tartozó G gráf

Tekintsük a jobboldali ábrán szereplő G nem irányított, összefüggő gráfot!

A két csúcs közötti legrövidebb út hossza a G gráfban
második csúcs
1 2 3 4 5 6
első
csúcs
1 0 1 2 2 1 3
2 1 0 1 2 1 3
3 2 1 0 1 2 2
4 2 2 1 0 1 1
5 1 1 2 1 0 2
6 3 3 2 1 2 0

Megjegyzések:

  • A táblázat a főátlóra szimmetrikus, mert egy A csúcsból egy B csúcsba legrövidebb úton ugyanolyan hosszú eljutni, mint visszafelé B-ből A-ba a legrövidebb úton.
  • A főátlóban csupa 0 szerepel, mert egy A csúcsból önmagába 0 lépéssel juthatunk legrövidebben.
  • Ha a gráf nem összefüggő, akkor előfordulhat, hogy nem lehet eljutni valamelyik pontból a másikba. Ilyenkor a legrövidebb távolság definíció szerint végtelen.

Az átlagos távolság a táblázatban szereplő nem nulla számok átlaga:

l_G = \frac{1 + 2 + 2 + 1 + 3 + \ldots + 3 + 3 + 2 + 1 + 2}{30}=\frac{50}{30} \approx 1,667.