#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: 5577
- Reputace: 106
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