Átmérő (gráfelmélet)
matematikai fogalom a gráfelméletben
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.
Nem összefüggő gráfban, ha értelmezzük az átmérő fogalmát, akkor értéke megegyezés szerint végtelen.
- .
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 lehet; azokat a gráfokat, amiknek a csúcsszáma éppen ennyi, Moore-gráfoknak nevezik.
További információk
szerkesztés- Graph Diameter, Mathworld