Matematické Fórum

lukaszh

Ahojte,

teória grafov je pre mňa nová téma a prosím o pomoc s dokazovaním týchto (asi triviálnych :-) viet z Diestela

(1) $\rm{rad}(G)\le\rm{diam}(G)\le2\cdot\rm{rad}(G)$
Prvá časť je zrejmá a vyplýva z definície
$\rm{rad}(G)=\min_{u\in V(G)}\max_{v\in V(G)}d_G(u,v)\nl\rm{diam}(G)=\max_{u\in V(G)}\max_{v\in V(G)}d_G(u,v)$
Problém mám skôr s druhou časťou nerovnosti (1).

(2) $g(G)\le2\cdot\rm{diam}(G)+1$
Tento dôkaz je tam rozpísaný, ale vôbec som ho nepochopil. $g(G)$ je dĺžka najkratšieho cyklu.

Vďaka

Kondr · 25. 09. 2009 20:27

Dovolím si vynechávat index G, snad to bude jasné.

1) Máme dva vrcholy u,v, pro které je d(u,v)=diam(G). Pro každý vrchol w grafu musí platit $d(u,w)+d(v,w)\geq d(u,v)=diam(G)$ (trojúhelníková nerovnost: kdyby neplatila, dala by se cesta z u do v zkrátit přes w). Současně $2\max_k d(w,k)\geq d(u,w)+d(v,w)$ , takže $2\max_k d(w,k)\geq diam(G)$ . Protože toto platí pro všechna $w$ , platí to i pro ten $w$ , v němž je $\max_k d(w,k)$ minimální. Proto $2 rad(G)\geq diam(G)$ .

2) EDIT: není to tak snadné, dodám časem

lukaszh · 25. 09. 2009 20:44

↑ Kondr:
Zatiaľ vďaka, pochopil som...

Kondr · 25. 09. 2009 21:14

2)Nejlepší bude to rozdělit na dva případy:
a) délka nejkratšího cyklu je 2k. Pak vezmeme za u a v "protější vrcholy cyklu" -- tedy tak, že mezi u a v existují dvě disjunktní cesty p,q, obě délky k (určené cyklem).
Předpokládejme, že mezi u a v existuje i cesta r kratší než k. Pokud je r disjunktní s p, tvoří r spolu s q kratší cyklus (spor). Pokud r není disjunktní s p, tvoří symetrický rozdíl cest p,q kratší cyklus (opět spor). Proto $k=|p|=|q|=d(u,v)\leq diam(G)$ , $g(G)=2k\leq 2diam G$ .

b)délka cyklu je 2k+1. Na cyklu zvolíme tři vrcholy, u, v,w tak, že z u do v i w vedou po cyklu cesty p,q délky k a v je spojen hranou s w. Ze stejných důvodů jako výšenemůže existovat cesta r z u do w (a symetricky ani do w) délky menší než k, proto opět $k=|p|=|q|=d(u,v)\leq diam(G)$ ,
$g(G)=2k+1\leq 2diam(G)+1$ .

Matematické Fórum

#1 25. 09. 2009 19:35 — Editoval lukaszh (25. 09. 2009 19:56)

Teória grafov

#2 25. 09. 2009 20:27

Re: Teória grafov

#3 25. 09. 2009 20:44

Re: Teória grafov

#4 25. 09. 2009 21:14

Re: Teória grafov

Zápatí