Fiala 9.6.2017

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.
Speedding
Matfyz(ák|ačka) level I
Příspěvky: 35
Registrován: 10. 1. 2017 19:32
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Fiala 9.6.2017

Příspěvek od Speedding »

1)
a) Definujte vytvořující funkci pro posloupnost.
Dána posloupnost {0,1,0,2,0,3,...}, určete její vytvořující funkci (Je to \frac{x}{(1-x^2)^2})

b) Definujte pojem kostra grafu.
Nalezněte dva neizomofrní grafy, které mají právě 6 koster a které mají stejný počet hran i vrcholů. (Stačí vzít cyklus délky 6 a nějak šikovně k tomu přidat "listy")

c) Definujte kombinatorickou kouli
Určete objem kombinatorické koule, je-li abeceda množina {1,...,7} a B(x,t)=((1,2,3)^T, 2) (Stačí si uvědomit, že velikost abecedy je 7, t je 2 a velikost kódu je 3. Dosadíme do vzorce \sum_{i=0}^t {n \choose i} (q-1)^i a výsledek je tuším 127.)


2) Zformulujte a dokažte větu o hranové barevnosti bipartitních grafů.

3) Sepište vše, co víte o KPR a latinských čtvercích.



Pan docent Fiala se před zkouškou zdál býti v dobré náladě, ale buď ho během první půl hodiny zkoušky něco naštvalo, nebo je při samotném zkoušení celkem tvrdý.
Měl jsem prakticky všechno, jen drobnou chybku v důkazu a u čtverců jsem toho moc nevěděl u ortogonality (měli jsme napsat vše co víme - to, že o ortogonalitě nevím nic, je vedlejší :D ). Definice bez chyby.
Řekl mi, že to mám mezi jedničkou a dvojkou a jestli chci jedničku, tak mu budu muset zodpovědět pár šťouravých dotazů - radši jsem vzal dvojku a "utekl", jinak by ještě přišel na to, že to moc neumím a vyhodil by mě :D Ve výsledku jsem ale spokojený.

Rada: Napište na ten papír opravdu všechno, co víte. Jinak se Fiala bude ptát a to fakt nechcete :D
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“