# Zk. 1.6.2009 - Kratochvil

<{ForumPost(poster="Marex", timestamp=2009-06-01 22:00:39)}>
Bylo 6 prikladu:  
  
1) Urcete pocet koster tohoto grafu:  
[http://artax.karlin.mff.cuni.cz/~vasum7am/graf1.png](http://artax.karlin.mff.cuni.cz/~vasum7am/graf1.png)  
2) Urcete vytvorujici funkci pro posloupnost (2, 1, 3, 2, 4, 3, 5, 4, ...)  
3) Rozhodnete, pro ktera prirozena cisla m, n obsahuje uplny bipartitni graf K<sub>m,n</sub> Hamiltonovskou kruznici  
4) Najdete nejvetsi parovani v nasledujicim grafu a zduvodnete, proc je nalezene parovani nejvetsi:  
[http://artax.karlin.mff.cuni.cz/~vasum7am/graf2.png](http://artax.karlin.mff.cuni.cz/~vasum7am/graf2.png)  
5) Dokazte, ze kazdy vrcholove 2-souvisly graf o n vrcholech ma alespon n koster. Popiste vsechny vrcholove 2-souvisle grafy o n vrcholech, ktere maji prave n koster.  
6) Necht n >= 3 je prirozene cislo. Necht A<sub>1</sub>, A<sub>2</sub>, ..., A<sub>n</sub> je system n ruznych mnozin velikosti n-2. Dokazte, ze tento system ma system ruznych reprezentantu.  
  
Bodovani:  
Priklady 1-4 za 6 bodu.  
Priklady 5-6 za 8 bodu.  
Celkovy mozny zisk je 40 bodu.  
  
Hodnoceni:  
40-34: 1  
31-28: 2  
26-19: 3  
15-14: ustni  
(mezery v bodovani znamenaji, ze takovy pocet bodu nikdo nemel)  
  
(Je to prepis z fotky, kreslit neumim, melo by to byt spravne, patches are welcome)
<{/ForumPost}>

<{ForumPost(poster="Sranda", timestamp=2009-06-12 00:02:56)}>
Nekdo ma reseni 6. prikladu.   
  
Hallova podminka rika, ze  
pro kazde  L z {1...n}, |L| <= |U Ai|  
  
ale  
* |U Ai| = n-2  
* kdyz bereme L = {1,2,3,..n} => |L| = n                        =>  n>n-2 => A1,A2,...,An nema SRR.  
  
Je to spravne nebo jsem mimo.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2009-06-12 00:59:25)}>
Myslim si ze |Ai|=n-2 a sjednoceni Ai muze byt vice nez n.  
indukci podle L plati az do n-1  
  
pro |L|=n   
SPOREM: |U Ai|<=n-1 , z toho plyne, ze system ma maximalne n-1 ruznych prvku. Kazdy mnozina obsahuje n-2 prvku.  
odtud vime ze (n-2) z (n-1) = n-1. (pocet ruzne mnoziny)  SPOR. Ale system ma n ruzne mnoziny.
<{/ForumPost}>