Matematické Fórum

geovektor1

Ahoj, narazil som na dalsiu zaujimavu ulohu z oblasti teorie grafov - Dokazte, ze pre kazdy graf plati nerovnost $r(G)\le d(G)\le 2r(G)$ kde $r$ je polomer a $d$ je priemer.

Brano · 07. 03. 2015 13:01

to je dost jednoduche - staci ked si pod seba napises definicie polomeru a priemeru a mal by si to vidiet
ak nie tak ich napis sem a posunieme sa.

geovektor1

No my sme si uvadzali takuto definiciu na prednaske: Polomerom (priemerom) grafu $G$ ozn. $r(G)$ $(resp. d(G)$ , nazyvame najmensiu (resp. najvacsiu) z excentrit vrcholov v G tj. $r(g):= min e(x)$ kde $x \in V_{G}$ $d(g):= max e(x)$ kde $x \in V_{G}$ Ale mne to nepride take jasne hned priamo z tej definicie tak neviem no.

jarrro · 07. 03. 2015 16:19

tak minimálne nerovnosť $r(G)\le d(G)$
je triviálna
a nerovnosť $d(G)\le 2r(G)$ platí, lebo keby bolo
$r<\frac{d}{2}$ , znamenalo by to, že nejaký vrchol v je vzdialený menej ako polovicu maximálnej vzdialenosti v grafe od všetkých vrcholov
lenže potom pre každé dva vrcholy u,w by bolo
$\rho{$u, w$}\leq \rho{$u, v$}+\rho{$v, w$}<\frac{d}{2}+\frac{d}{2}=d$
teda
$\rho{$u, w$}<d$
teda aj maximálna vzdialenosť (bavíme sa o konečných grafoch) by bola menšia ako d to dáva spor