Ugrás a tartalomhoz

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

A Wikipédiából, a szabad enciklopédiából
A lap aktuális változatát látod, az utolsó szerkesztést TurkászBot (vitalap | szerkesztései) végezte 2020. november 15., 12:59-kor. Ezen a webcímen mindig ezt a változatot fogod látni. (Hibás DEFAULTSORT eltávolítása (WP:BÜ), apróbb javítások)
(eltér) ← Régebbi változat | Aktuális változat (eltér) | Újabb változat→ (eltér)

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]