Matematické Fórum

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

Stránky: 1

 

#1 10. 10. 2015 15:48 — Editoval dash (10. 10. 2015 16:07)

dash
Zelenáč
Příspěvky: 14
Reputace:   0 
 

Dôkaz: Orientovaný graf je acyklický...

Snažím sa dokázať:
//forum.matweb.cz/upload3/img/2015-10/83160_Screen%2BShot%2B2015-10-10%2Bat%2B15.18.55.png

Začal som takto, neviem ale či idem dobrým smerom:
Máme graf $G$ s maticou susednosti $A$. Predpokladajme, že v graf $G$ je acyklický. Potom existuje práve 0 sledov dĺžky $k$ z vrcholu $v$ do $v$. Predpokladám teda, že platí $\forall k,j: a_{j,j}^{[k]}=0$ kde $a_{i,j}^{[k]}$ je $(i,j)$-tý prvok matice $A^k$. Tu som sa zastavil, pretože neviem ako dokázať tento predpoklad.

Offline

 

#2 11. 10. 2015 14:13

check_drummer
Příspěvky: 4652
Reputace:   101 
 

Re: Dôkaz: Orientovaný graf je acyklický...

↑ dash:
Ahoj, pokud je acyklický, tak lze vrcholy seřadit tak, že pro i>j nevede hrana z j do i. Z toho už pak hned plyne to tvrzení o té matici. Otáza je, zda je zřejmé to mé tvrzení. Ale tady si stačí uvědomit, že musí existovat vrchol, do kterého nevede žádná hrana - ten prohlásíme za první a indukcí pokračujeme dále.

"Máte úhel beta." "No to nemám."

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson