Átmérő (gráfelmélet)

Egy gráf $d$ vagy $diam$ átmérőjén a csúcsok maximális excentricitását értjük; tehát $d$ a csúcspárok között fellépő legnagyobb távolság, avagy $d=\underset{v\in V}{\max }ϵ(v)$. 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.

Nem összefüggő gráfban, ha értelmezzük az átmérő fogalmát, akkor értéke megegyezés szerint végtelen.

$D_G=\underset{u,v\in V}{\max }\underset{p\in P(u,v)}{\min }l(p)$.

Nem összekeverendő az átlagos távolsággal, ami a pontpárok közötti legrövidebb utak hosszainak átlaga.

A d maximális fokszámú és k átmérőjű gráf csúcsainak száma legfeljebb $1+d\sum _{i=0}^{k-1}(d-1{)}^i$ lehet; azokat a gráfokat, amiknek a csúcsszáma éppen ennyi, Moore-gráfoknak nevezik.

További információk

• Graph Diameter, Mathworld