1. Urcite max. pocet hran grafu (V,E) s n vrcholmi, ktory neobsahuje ziadny trojuholnik.
2. Uvedte znenie principu inkluzie a exkluzie. Naznacte dokaz.
3. Formulujte "Lemma o duhovych trojuholnikoch".
4. Dokazte, ze kazdy strom obsahujuci vrchol stupna k ma aspon k listov.
5. Kolko kruznic ( lubovolnej dlzky) je obsiahnutych v Kn?
6. Uvazme uplny graf (V,(V nad 2)), kde V={1,2,...,n}, s vahou w({i,j})= (i,j) na druhu. Najdite vahu minimalnej kostry.
7. Nech R1, R2 su relacie ekvivalencie na tej istej mnozine. Rozhodnite a zdovodnite platnost nasledujucich tvrdeni:
a) R1 U R2 je ekvivalencia
b) R1 prienik R2 je ekvivalencia[/code][/list]
Zadanie z DM od Nesetrila
Zadanie z DM od Nesetrila
Naposledy upravil(a) Jarnik dne 25. 1. 2006 19:00, celkem upraveno 1 x.