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
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Teorie grafu: stromy (TOTO TÉMA JE VYŘEŠENÉ)
#1 07. 01. 2008 10:04
- vincent_vega_
- Zelenáč
- Příspěvky: 13
- Reputace: 0
Teorie grafu: stromy
Teorie grafů
Dokažte následující větu. Jestliže má strom T úplné párování, pak pro každý vrchol v∈V(T) platí, že graf T-v má jedinou lichou komponentu. Lichou komponentou rozumíme komponentu, která má lichý počet vrcholů.
Vím že se to tu už řešilo, ale topic už nefunguje. Predem dekuji
Offline
#2 07. 01. 2008 10:43
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Teorie grafu: stromy
Hrany tvořící párování obarvěme červeně, ostatní modře. Když odstraníme libovolný vrchol, rozpadne se graf na několik komponent. Ty, které byly připojeny modrou hranou si úplné párování zachovají, mají proto sudý počet vrcholů. Komponentě, která byla připojena červeně, chybí právě odstraněný vrchol k tomu, aby měla úplné párování. Tato jediná komponenta je lichá.
Už se to na fóru jednou řešilo, ale buď to nejde vyhledat, nebo to nějaký plantážník smazal.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#3 07. 01. 2008 11:04
- vincent_vega_
- Zelenáč
- Příspěvky: 13
- Reputace: 0
Re: Teorie grafu: stromy
Jj je mi to jasny díky moc.
Offline
Stránky: 1
- Hlavní strana
- » Vysoká škola: úvod do studia
- » Teorie grafu: stromy (TOTO TÉMA JE VYŘEŠENÉ)