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
#2 01. 06. 2013 19:04 — Editoval OiBobik (01. 06. 2013 19:06)
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: Teorie grafů - párování
↑ Mythic:
Čau,
(perfektní) párování je graf, jehož všechny vrcholy mají stupeň právě 1 (tj. každý vrchol je právě v jedné hraně).
Strom je graf, kde mezi každými dvěma vrcholy vede právě jedna cesta (tj. souvislý graf bez kružnic).
Takže zadání je:
Když dostaneš strom, kolika způsoby v něm lze vybrat nějakou podmnožinu jeho hran tak, aby každý vrchol byl koncovým vrcholem právě jedné z těch vybraných hran.
Hint:
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline
#3 01. 06. 2013 20:05
- check_drummer
- Příspěvky: 4900
- Reputace: 105
Re: Teorie grafů - párování
↑ Mythic:
Ahoj, začni od vrcholu se stupněm 1.
"Máte úhel beta." "No to nemám."
Offline