Átlagos távolság

Az átlagos távolság vagy átlagos úthossz a gráfelméletben a csúcspárok közötti távolságok (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

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

Tekintsük a jobb oldali á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.$