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

Ez a szócikk az átmérő gráfelméleti jelentéséről szól. Hasonló címmel lásd még: Átmérő (egyértelműsítő lap).

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

${\displaystyle D_{G}=\max _{u,v\in V}\min _{p\in P(u,v)}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 ${\displaystyle 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.

• Graph Diameter, Mathworld

Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!