Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
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)
Prvá časť je zrejmá a vyplýva z definície
Problém mám skôr s druhou časťou nerovnosti (1).
(2)
Tento dôkaz je tam rozpísaný, ale vôbec som ho nepochopil. je dĺžka najkratšieho cyklu.
Vďaka
Offline
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 (trojúhelníková nerovnost: kdyby neplatila, dala by se cesta z u do v zkrátit přes w). Současně , takže . Protože toto platí pro všechna , platí to i pro ten , v němž je minimální. Proto .
2) EDIT: není to tak snadné, dodám časem
Offline
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 , .
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 ,
.
Offline