Zkouska (predtermin 12.1.2007) - Pankrac

[Wolda]

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...

[Kubees]

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

[Hardwired]

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 )

[lukas.hermann]

Tak zkoušku z Diskrétky už mám za sebou. Bylo to opravdu jednoduché, nemusel jsem se to tolik učit 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 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.

[mathew]

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
2. dokaz binomickej vety
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
Prajem prijemne chvile stravene nad diskretkou

[onti]

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 ) pangrac je zatial najferovejsi profesor ma matfyze

[dallingerp]

princip inkluze-exkluze + dukaz

jinak podobny jako ostatni
Pangrac jenom rotuje nekolik otazek, aby lidi, co jsou zrovna v mistnosti, nemeli stejnou otazku.

[laforge]

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.