Matematické Fórum

Sandrastrelcova · 26. 12. 2013 00:33

Ahoj prosím o pomoc s důkazem... dokaž že orientovaný graf je slabě souvislý právě tehdy když je silně souvislý... kreslím obrázky a tam to vidím, ale jak na důkaz? prosím pomoc!

petrkovar · 29. 12. 2013 21:18

↑ Sandrastrelcova:Myslím, že tvrzení neplatí. Stačí vzít dva vrcholy a mezi nimi jednu orientovanou hranu. Takový graf je slabě souvislý a není silně souvislý. Jaké máte definice slabé a silné souvislosti?

mholec · 04. 01. 2014 13:00

Slabě souvislý orientovaný graf je silně souvislý, právě když každá jeho hrana je obsažena v nějakém cyklu.

Pokud je graf silně souvislý, je i slabě souvislý. Je to vidět když se provede symetrizace silně souvislého grafu.

Důkazy neumím formulovat ale logicky, je-li v silně souvislém grafu cesta mezi každými dvěma vrcholy, pak musí být i ve slabě souvislém, protože jakoukoliv cestu grafu silně souvislého lze nalézt i v grafu slabě souvislém.

Sandrastrelcova · 04. 01. 2014 16:44

už jsem to vyřešila sama, ale děkuji i tak!

Matematické Fórum

#1 26. 12. 2013 00:33

orientovaný graf - důkaz

#2 29. 12. 2013 21:18

Re: orientovaný graf - důkaz

#3 04. 01. 2014 13:00

Re: orientovaný graf - důkaz

#4 04. 01. 2014 16:44

Re: orientovaný graf - důkaz

Zápatí