Skúška 19.1

Zdravstvujte!

Tak dnes som uspesne absolvoval skusku z DM a sice to uz mate asi vsetci za sebou predsa mozno aspon niekomu pomoze ked bude vediet co sa tam asi tak objavuje. Moje zadanie znelo:

1. Určete max. počet hran gran (V,E) s n vrcholy, ktorý neobsahuje žádný trojúhelník.

2. Uvedte znení principu inkuse a exkluse. Naznačte důkaz. (ja som ho radsej spravil celý)

3. Formulujte "Lemma o duhových trojúholníkoch".

4. Dokažte, že každý strom obsahuj)ci vrchol stupna k má alespon k listů.

5. Kolik kružnic (libovolné délky) je obsaženo v Kn?

6. Uvažme úplný graf, kde V={1..n} s vahou w({i,j}) = (i-j)^2. Naleznete váhu minimálnej kostry.

7. Nechř R1, R2 sú relace ekvivalence na téže množine. Rozhodnete a zduvodnete platnost následujících tvrzení:
   a) R1 sjednoceno R2 je ekvivalence
   b) R1 prienik R2 je ekvivalence

a to je všetko.