# Přetermín 6.1.2006

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2006-01-17 16:40:48)}>
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)
<{/ForumPost}>

<{ForumPost(poster="Martin", timestamp=2006-01-17 21:23:02)}>
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)?
<{/ForumPost}>

<{ForumPost(poster="Zdeněk Vilušínský", timestamp=2006-01-18 00:16:13)}>
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.
<{/ForumPost}>

<{ForumPost(poster="Martin", timestamp=2006-01-18 11:36:52)}>
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.  :wink:
<{/ForumPost}>