Přetermín 6.1.2006

[Zdeněk Vilušínský]

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)

[Martin]

No teda to bych si radši dokázal tu Spernerovu vetu, než abych hledal tenhle antiřetězec. Jo a mimochodem, jak jsi dělal tu 3)?

[Zdeněk Vilušínský]

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.

[Martin]

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.