od miko » 20. 1. 2005 00:21
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.
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.