Předtermín byl ústní s písemnou přípravou a každý měl své vlastní zadání. To moje bylo:
1) Zformuluj a dokaž binomickou větu
2) Co je to kostra a najdi graf s právě 6ti kostrami
3) Dokaž, že pro každý souvislý graf G existují 2 vrcholy u, v, že G-u, G-v, i (G-u)-v jsou souvislé
a protože jsem nechtěl dokazovat Spernerovu větu , tak jsem dostal příklad navíc
4) Urči největší systém nezávislých podmnožin (1..10) M (tedy platí M1 podmnožinou M2 => M1=M2;) s tím, že jsou v něm již obsaženy jednoprvkové množiny (9), (10)
Přetermín 6.1.2006
- Zdeněk Vilušínský
- Matfyz(ák|ačka) level III
- Příspěvky: 110
- Registrován: 16. 1. 2006 22:04
- Typ studia: Informatika Bc.
- Login do SIS: viluz5am
- Bydliště: Železný Brod/Troja A1923
- Kontaktovat uživatele:
- Zdeněk Vilušínský
- Matfyz(ák|ačka) level III
- Příspěvky: 110
- Registrován: 16. 1. 2006 22:04
- Typ studia: Informatika Bc.
- Login do SIS: viluz5am
- Bydliště: Železný Brod/Troja A1923
- Kontaktovat uživatele:
Já si to radši spočítal, protože když se nad tím zamyslýš, je to trivka. Protože už v něm mám jednoprvkové 9 a 10, tak se 9 a 10 už nemůže vyskytnout v žádné množině v nezávislém systému. A tak jen dosadíš do vzorečku a vyjde 72.
Co 3ky týče, ta byla težší, ale měl jsem nápad. Pro strom to totiž platí - má minimálně dva listy, které můžeš sebrat bez porušení souvislosti.
No a pro jiný graf si najdeš kostru. Ta je strom a tak má aspoň 2 listy. No a pak mi jen trvalo, než jsem si uvědomil, že je můžu utrhnout bez obav, a zbytek grafu dostanu zpětným dodáním hran - čímž určitě neporuším souvislost.
Co 3ky týče, ta byla težší, ale měl jsem nápad. Pro strom to totiž platí - má minimálně dva listy, které můžeš sebrat bez porušení souvislosti.
No a pro jiný graf si najdeš kostru. Ta je strom a tak má aspoň 2 listy. No a pak mi jen trvalo, než jsem si uvědomil, že je můžu utrhnout bez obav, a zbytek grafu dostanu zpětným dodáním hran - čímž určitě neporuším souvislost.
Věda je jako sex. Jistěže má nějaké praktické výsledky, ale proto ji přece neděláme. - R.P.Feynman
I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
I krátký algoritmus může mít chování tak komplikované, že mu nerozumí ani jeho autor.
- Martin
- Supermatfyz(ák|ačka)
- Příspěvky: 330
- Registrován: 19. 2. 2005 20:23
- Typ studia: Matematika Ph.D.
No jo, ale já jsem to zadání pochopil tak, že máš ten antiřetězec určit a ne jen spočítat počet prvků. Tohle jsem samozřejmě taky věděl, ale přecejen vypisovat 8C4 + 2 množin by se mi asi moc nechtělo.
Ta trojka - hmm docela lehký, když se člověk zamyslí... Asi bych se měl občas trochu zamyslet.
Ta trojka - hmm docela lehký, když se člověk zamyslí... Asi bych se měl občas trochu zamyslet.
"Endure. In enduring grow strong."