#1 15. 04. 2015 12:34
- geovektor1
- Příspěvky: 119
- Reputace: 0
Dokaz, teoria grafov
Ahojte, mam dokazat jednu vetu ale vobec neviem ako na to, znenie: Ak graf aspon s tromi vrcholmi obsahuje most, tak obsahuje aj artikulaciu.
Offline
#2 15. 04. 2015 15:50
Re: Dokaz, teoria grafov
↑ geovektor1:
Ahoj,
stačí vyjít z definic:
Most je hrana, po jejímž odnětí vzroste poček komponent grafu.
Artikulace je uzel, po jehož odnětí vzroste počet komponent grafu.
Když odejmeš uzel, pochopitelně odejmeš i hrany, které do něj vedou. Tedy když odejmenš uzel, do kterého vede most, odňal jsi i most a z definice mostu ti vzrostl počet komponent. Tedy uzel, který si odejmul, se chová jako artikulace.
Доктор сказал «в морг» — значит в морг!
Offline