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
#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