Zadanie z DM od Nesetrila

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]

Je hezké, že na ostatní tak myslíš, že jim píšeš zadání, ale mít přezdívku Jarník... hmm to už chce pořádnou sebejistotu. :D :D

Treba to tu rozhybat :idea:

Vsak to je to iste zadanie co som mal ja minuly rok. Len mi nevravte, ze oni to nechavaju uplne rovnake? Lebo ak hej, tak to je potom dobra fraska...

Nesetril opakuje zadania, aj rovnake chyby ma v nich :D

Diskretka nie je az taka lahka, dostal som zevraj najlahsi test, lebo tam bol len jeden dokaz, aj tak som ho nespravil, lebo ja som vedel len dokazy, priklady som pocitat nevedel. Nie je umenia nespravit tazku skusku. :D