# Zkouska (predtermin 12.1.2007) - Pankrac

<{ForumPost(poster="Wolda", timestamp=2007-01-12 20:09:12)}>
Takze, nejprve upozorneni! My co jsme tam byli na 15:30, i pres vsechna predchozi prohlaseni o ustnim zkouseni, jsme byli zkouseni de-facto pisemne. Mozna ze proto, ze uz se mu tam nechtelo v patek ve ctyri byt dele, nez bylo nutne (mozna, ze na zacatku o tom neco rekl, ja kazdopadne diky bouracce tramvaje prisel pozde). Probihalo to vicemene tak, ze vzdy k nekomu z nas prisel a neco nam zadal, jen posledni priklad byl vylozene na nejakem papirku... Takze tezko soudit, co z toho muzete potkat Vy...  
  
Kazdopadne, ja mel celkem 3 otazky:  
  
1) Definujte castecne usporadani ... Overte, zda relace R: N->N xRy <=> (|x|>=|y| & x <> -y) je castecne usporadani a pokud ano, nakreslete Hasseho diagram.  
  
def. najdete napr. v Kapitolach. Ta relace castecne usporadani je, ale pozor, pouze tehdy, kdyz se do te podminky pripise jeste 0 R 0 (nula v relaci s nulou), jinak by to nebylo reflexivni. To mi nedoslo, je to takovy maly chytacek. Ale jinak to z tech axiomu c.u. overite a H.D. nakreslite.  
  
  
2) zformulujte a dokazte vetu o maximalnim poctu hran rovinneho grafu.  
  
viz. Kapitoly ci Vase zapisky s prednasek :-)  
  
  
3) V zavislosti na n mejme mnozinu X = {1,2,3......,n} a usporadane dvojice (A, B) takove, ze A "inkluze" B "inkluze" X. Kolik takovych usporadanych dvojic v zavislosti na n je? + Dodatek: ma vyjit hezka formule, zkuste pouzit napr. binomickou vetu.  
  
Ja se drzel hintu, kdyz si rozepisete, jak muzete volit A a v zavislosti na tom pak B, dojdete k sume \[k od 0 do n] (n nad k)*2^n-k coz je po par upravach presne dle binomicke vety 3^n. Kdyz jsem to vyresil, tak jen Pankrac povidal, ze to jde jednoduseji nahlednout tak, ze si budeme barvit prvky v mnozine X 0, resp. 1, resp. 2 pokud nejsou ani v A ani v B, resp. jsou jen v B, resp. jsou v A i B. Tzn. zobrazeni z \[n] -> {0,1,2} a tech je 3^n.  
  
  
Jinak Pangrac byl u zkousky vazne spravny, pokud se na to alespon trosku pripravite, tak to musite dat! U dukazu vet neni potreba nejake silene formalni rozebirani, staci vedet, o co jde.  
  
Hodne stesti...
<{/ForumPost}>

<{ForumPost(poster="Kubees", timestamp=2007-01-12 22:36:19)}>
Souhlasim že Pangrác byl dost férovej :) (Já šel na prvním předtermínu) Tak ještě přihodim na co se ptal mě:   
1. a) Co je to Barevnost grafu  
    b) Jaká je barevnost grafu K5  
    c) Jaká je barevnost grafu K3,3  
2. Kolik je přirozených čísel od 1 do 100 které nejsou dělitelné druhou mocninou žádného přirozeného čísla (1 se nepočítá)  
3. Dokázat binomickou větu
<{/ForumPost}>

<{ForumPost(poster="Hardwired", timestamp=2007-01-13 11:06:58)}>
Já sem měl:  
1) definujte ekvivalenci a spočtěte počet různých ekvivalencí na množině {1,2,3,4}  (tam sem využil toho, že třídy ekvivalence tvořej rozklad množiny, na který ta ekvivalence je)  
  
2) ušaté lemma (taková ta konstrukce 2-souvislého grafu z kružnice přidáváním uší + důkaz 2-souvislosti vytvořeného grafu a toho, že tímhle postupem vytvořím jakýkoliv 2-souvislý graf)  
  
3) počet navzájem neizomorfních grafů na 8mi vrcholech, jejichž vrcholy mají stupně 0, 2 nebo 7  
  
4) spočítat délku antiřetězce v uspořádání inkluzí na množině {1 ... 10} takového, že neobsahuje {9} ani {10}  (je potřeba využít Sternerovy věty na množinu {1...8}...tohle sem nedal, takže nakonec za 2 :) )
<{/ForumPost}>

<{ForumPost(poster="lukas.hermann", timestamp=2007-01-13 17:47:14)}>
Tak zkoušku z Diskrétky už mám za sebou. Bylo to opravdu jednoduché, nemusel jsem se to tolik učit :P Pankrác byl naprosto skvělý. Když mi na konci nešly některé části příkladu, tak mi nechal dost času na přemýšlení a nakonec mi i poradil. Stres ze mě spadnul hned, jak jsem si sedl do lavice :)  
  
Dostal jsem:  
  
1) definice stromu + napsat těch 6 ekvivalencí z přednášky  
  
2) formulace a důkaz binomické věty  
  
3) cvičení s jednoho papírku:  
  
"Mohou mít dva grafy G1 a G2 stejné skóre, jestliže  
  
a) G1 je souvislý, G2 není souvislý,  
b) G1 je 2-souvislý, G2 není souvislý,  
c) G1 je 2-souvislý, žádná komponenta G2 není 2-souvislá,  
d) G1 je strom, G2 není souvislý,  
e) G1 je strom, G2 je 2-souvislý,  
f) G1 neni rovinný, G2 je kružnice,  
g) G1 neni rovinný, G2 je strom?"  
  
Zadání tohohle příkladu jsem našel mj. tady na fóru, i když až potom, co jsem ho u zkoušky dostal 8) Není to nic těžkého, jen to poslední mi trvalo dost dlouho.  
  
To je vše. Rozhodně se toho nebojte. Je to asi nejjednodušší zkouška z těch, které o tomto zkouškovém máme. Stačí se na to pořádně podívat a pochopit to.
<{/ForumPost}>

<{ForumPost(poster="mathew", timestamp=2007-01-13 17:47:50)}>
Tak ja som bol na predtermine uz o jednej a prebiehalo to tak ako to tu uz bolo napisane. Ja som vychytal nasledovne :   
1. co je to strom a napis co plati o stromoch (tych 5 ci 6 ekvivalencii) bez dokazu  8)   
2. dokaz binomickej vety  :D   
3. priklad: mas graf na 15 vrcholoch   
   V={1,2,3...,15}  
   E={{i,j}; i - j sude a |i-j|>=4}  
   dokazte ze tento graf nie je rovinny  
  
a to bola pohoda je tam totiz K33 napr jedna partita vrcholy 1,3,5 a druha 11,13,15 .   
Vychytal som asi to najlahsie co sa dalo takze za jedna  8)    
Prajem prijemne chvile stravene nad diskretkou  :P
<{/ForumPost}>

<{ForumPost(poster="onti", timestamp=2007-01-16 00:28:00)}>
Tiez som bol na predtermine 12.1 o 12:30, mal som viacmenej kombinaciu predosleho, konkretne:  
  
1. Definuj ciastocne usporiadanie na mnozine  
    + priklad ci je relacia na Z  |x|>=|y| a x<>-y  ciastocne usporiadanie + hassov diagram  
2. Sformuluj a dokaz usate lemma  
3. priklady som mal pre zmenu 2  
   Kolko je kruznic dlzky k v uplnom grafe s n vrholmi. (sranda priklad)  
   Pocet neizomorfnych grafov na 8 vrcholoch stupna 0,2,7..  
  
Mam za 2, ale sam by som si ju nedal :o) pangrac je zatial najferovejsi profesor ma matfyze
<{/ForumPost}>

<{ForumPost(poster="dallingerp", timestamp=2007-01-16 11:07:53)}>
princip inkluze-exkluze + dukaz  
  
jinak podobny jako ostatni  
Pangrac jenom rotuje nekolik otazek, aby lidi, co jsou zrovna v mistnosti, nemeli stejnou otazku.
<{/ForumPost}>

<{ForumPost(poster="laforge", timestamp=2007-01-21 12:15:12)}>
Tak na zaciatok som mal definovat suvisly graf (+2-suvisly, vrcholovo, hranovo, kriticky 2-suv a tak...). Potom dokazat horny odhad na farebnost grafu (5), a na koniec par relacii (urcit vlastnosti, 4ks).  
  
Vela stastia na skuske.
<{/ForumPost}>