Á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