# Zkouska 2.6.

<{ForumPost(poster="Fin", timestamp=2008-06-03 09:38:19)}>
Zadání co si pamatuju zhruba takovehle:  
1)Pocet koster K3,3 - pres determinanty nebo rekurzivne, melo vyjit 81.  
2)Vyjadrime sqrt(1-3x) jako radu Sum(a<sub>i</sub>x<sup>i</sup>)  
a)První kladný koeficient je a0, jaký je další(neexistuje, stačí si podle OBV napsat tu sumu a koukat jak vypada pro licha a suda i)  
b)prvni cely koeficient je a0, jaky je dalsi(na to jsem neprisel)  
3)Najit maximalni parovani v bipartitnim grafu, neni regularni ani nema stupne v jedne partite vetsi nez v druhe, jestli se vam to chce kreslit tak G=(AuB,E),A={1,2,3,4,5,6},B={7,8,9,10,11,12},E={1-8,1-9,1-11,2-7,2-10,3-7,3-10,4-7,4-10,5-9,5-11,5-12,6-10,6-11,6-12}. Bud pres toky nebo rychleji najit parovani o 1 mensi nez perfektni(ktere je videt na prvni max na druhy pohled) a ukazat ze perfektni parovani neexistuje tak ze pujdeme po vrcholech ktere maji stupen jedna, hrana ktera z nich vede musi byt v perf. parovani, pak smazat hrany vedouci z druheho vrcholu teto hrany a repeat, dokud se to nekde nezasekne.  
4)Nakreslete KPR radu 3(neni Fannova rovina, ta je radu 2). Ja to delal postupem ze skript(Matousek), mozna rychlejsi by v tomhle pripade bylo nakreslit dva ortogonalni LC radu 3 a nakreslit to podle nich, podle toho jak rychle je clovek dokaze najit.  
Nalseduji dokazovaci prřiklady, opet staci 2 ze 3  
5)Mame n ruznych mnozin velikosti n-2, dokazte ze tento system ma SRR  
6)Dokazte, ze v 2-souvislem grafu na n vrcholech existuje aspon n koster.  
7)Naky barveni cisel, zadani si presne nepamatuju, bylo to na Ramseyovu vetu a pry je to ve skriptech od Vally(existuje stejnobarevna trojice x,y,z ze x+y=z, je to jakesi lemma)  
  
5) se dalo dokazat pres Hallovu podminku, pro J velikosti do n-2 jasne plati, n-1 taky protoze ty mnoziny jsou ruzne(tj kazde dve se lisi alespon v jednom prvku) a pro n plati protoze sjednoceni n mnozin velikosti n-2 nemuze byt n-1, pocet podmnozin velikosti n-2 z n-1 prvku je (n-1)nad(n-2) coz je n-1 (aspon myslim ze to tak bylo, kazdopadne nejaky podobny argument).  
6)indukce podle usateho lemmatu(kruznicova verse), pridanim ucha vzniknou nove kostry tak ze vynecham nekterou z jeho hran  
7)tu pry neresil nikdo:o)  
  
Moje rada zni nepodcenujte uceni dukazu, i kdyz napisete pisemku na 3, porad to na ustnim muzete vyhnat na 1 .o)
<{/ForumPost}>