Zkouska 2.6.

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Fin
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 23. 1. 2007 17:56

Zkouska 2.6.

Příspěvek od Fin »

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(aixi)
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)
-Fin
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“