Nějaké příklady zadání zkoušek pro představu pro ty, které diskrétka teprve čeká.
Jinak zkouška probíhá v klidu a míru – dostanete zadání, bez časového presu si řešíte a když si myslíte, že máte hotovo, Valtr přijde a příklady proberete. Pokud se objeví nějaká nejasnost, dostanete čas si věc znova promyslet a až si budete myslet, že už víte, Valtr přijde znova.
Formální oblečení není vůbec potřeba, i Valtr sám přišel tak, jak chodí na přednášky.
Malá poznámka: zadání se zřejmě opakují, na zkoušce v pondělí 17.1. jsem dostal naprosto stejné zadání jako Martin Ziegler, který (jak soudím dle data zápisu do wiki) dělal zkoušku už v pátek 15.1.
1) Definice:
2) Problém minimální kostry, popsat a předvést 1 algoritmus bez důkazu správnosti.
3) Kolik existuje neizomorfních grafů na 8 vrcholech, které mají skóre jen z 1 a 2.
4) Nakresli všechny vzájemně neizomorfní grafy se skóre (3,3,3,3,3,3) (+ samozřejmě důkaz že jich víc není. )
1) Definice:
a) Definujte permutaci na množině X. Dále X = Z (množina celých čísel), rozhodněte zda jsou (a -->> -a), (a -->> a+1) a (a -->> 5a) permutace.
b) Podejte dvě definice stromu. Dokažte, nebo vyvraťte: každý indukovaný podgraf stromu je strom.
c) Definujte souvislý graf. Dokažte, nebo vyvraťte: doplněk každého nesouvislého grafu je souvislý graf.
2) Charakterizujte skóre, podle kterého lze sestrojit graf.
3) Kolik je permutací množiny {1, ..., n} s právě jedním pevným bodem?
4) Charakterizujte grafy, které neobsahují cestu délky tři jako podgraf.
Pokud se chcete k tomuhle zadání něco zeptat, klidně mi napište: MartinZiegler?.
Tak sem taky nejake zadani pridam:
1) a) Definujte ekvivalenci na mnozine X. Jsou nasledujici relace ekvivalence? X = Z \ {0}: (x|y; xy>=0; x-y je nasobek 7).
{PS, na to co byla ekvivalence, tak se jeste priptal, kolik to ma trid ekvivalence}
b) Definujte permutaci na mnozine X. Pro X = {1,2,3,4,5,6,7} urcete kolik je permutaci suda na suda a zaroven licha cisla na licha.
Kolik je permutaci suda na licha a licha na suda?
c) Definujte indukovany podgraf. Najdete graf na 6 vrcholech jehoz vsechny podgrafy jsou indukovane.
2) Princip inkluze a exkluze. (Asi i dukaz, ja jsem to teda i dokazovala)
3) Qn = (V,E). Vrcholy jsou n-prvkove posloupnosti nul a jednicek. Mezi dvema vrcholy vede hrana, prave tehdy, lisi-li se prave v jedne
souradnici. Rozhodnete pro ktera n se da nakreslit 1 tahem bez opakovani hran. (U tohoto prikladu jsem rikala i nastin dukazu, kdy je graf Eulerovsky)
4) (2,3,3,3,3,3..) {n-1 trojek} Rozhodnete pro ktera n je to skore grafu.
Pokud chcete neco vedet k tomuhle zadani, tak mi klidne napiste: KateřinaBöhmová.
1. a) Definujte skóre grafu. Jakou nejvyšší sumu skóre lze získat? Vyjádřete pomocí n.
b) Definujte zobrazení. Jsou následující relace zobrazením (množiny X a Y jsou s přirozenými čísly)?
i) xRy právě tehdy když x dělí y
ii) xRy právě tehdy když x^4 – y^2 = 0
iii) xRy právě tehdy když x+1-y^2 = 0
c) Definujte eulerovský graf. Jaké existují bipartitní eulerovské grafy Km,n ?
2. Zformulujte a dokažte (a zdůvodněte) princip inkluze a exkluze (původně Spernerova věta – nebude vyžadovat – nebrali jsme).
3. Spočtěte SUMA (k přes 0 do n) ( 2n nad 2k )
4. Najděte rovinný graf, který má nejvíce stěn + zdůvodnění a vyjádření pomocí n.
Všechno jsem měl správně, ale pak se mě zeptal ještě, co vím o počtu hran v grafu bez C4 (nanejvýš 1/2*(n2/3 + n) ). K tomuhle ke mě dostal už jen, že se to dokazuje pomocí Cauchy-Schwarzovy nerovnosti, tak mě nechal předvést ještě (celý) důkaz Cayleyho formule.
Na stejném termínu byl ještě jeden člověk (nebudu jmenovat) se stejným zadáním, kterého se neptal vůbec na nic >:-o. Pokud se chcete k tomuhle zadání na něco zeptat, rozhodně mi nepište: Adam