Ugrás a tartalomhoz

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

Ellenőrzött
A Wikipédiából, a szabad enciklopédiából

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]