Predtermin 6.1.

Zdar,

tak som sa (hadam viac ako menej :D uspesne) zucastnil dnesneho predterminu.. pisalo sa to v S3 na Malej strane, 12:15, 90 min. casu, 4 ulohy. Zajtra rano vysledky a pripadne ustne doskusanie (ak niekto nebude suhlasit so znamkou :))

Takze priklady (pokial si pamatam)

1, (a) napiste definici kostry souvisleho grafu.
kolik koster ma C_n (kruznice na n vrcholech)? Zduvodnete
kolik koster ma K_n? [bez dokazu...aspon dufam :D]
(b) definujte permutaci na obecne mnozine X
kolik existuje permutaci na mnozine X={1,2,3,4,5,6,7}, ktere sudym cislem prirazuji sude a lichym liche? kolik jich existuje takovych, ktere sudym prirazuji liche a lichym sude? zduvodnete.
(c) definujte indukovany podgraf
uvedte priklad grafu na 6 vrcholech, ktereho kazdy podgraf je zaroven indukovany podgraf.

2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

3, Definujme graf Q_n tak, ze V={0,1}^n (vsechny usporadane n-tice jednicek a nul) a vrcholy (x_1,x_2...x_n), (y_1,y_2...y_n) jsou spojeny hranou prave tehdy pokud se lisi pouze v jedne souradnici.
Urcete, pro ktere n existuje v grafu Q_n uzavreny tah, ktery prochazi vsemi hranami. Zduvodnete.

4, Urcte, pro ktere n existuje graf se skore (2,3,3,3...3) (jedna dvojka, n-1 trojek). Zduvodnete.

Kua, je to dobry pocit mat to za sebou... :lol:

Isidor wrote:Zdar,

tak som sa (hadam viac ako menej :D uspesne) zucastnil dnesneho predterminu.. pisalo sa to v S3 na Malej strane, 12:15, 90 min. casu, 4 ulohy. Zajtra rano vysledky a pripadne ustne doskusanie (ak niekto nebude suhlasit so znamkou :))

Takze priklady (pokial si pamatam)

1, (a) napiste definici kostry souvisleho grafu.
kolik koster ma C_n (kruznice na n vrcholech)? Zduvodnete
kolik koster ma K_n? [bez dokazu...aspon dufam :D]
(b) definujte permutaci na obecne mnozine X
kolik existuje permutaci na mnozine X={1,2,3,4,5,6,7}, ktere sudym cislem prirazuji sude a lichym liche? kolik jich existuje takovych, ktere sudym prirazuji liche a lichym sude? zduvodnete.
(c) definujte indukovany podgraf
uvedte priklad grafu na 6 vrcholech, ktereho kazdy podgraf je zaroven indukovany podgraf.

2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

3, Definujme graf Q_n tak, ze V={0,1}^n (vsechny usporadane n-tice jednicek a nul) a vrcholy (x_1,x_2...x_n), (y_1,y_2...y_n) jsou spojeny hranou prave tehdy pokud se lisi pouze v jedne souradnici.
Urcete, pro ktere n existuje v grafu Q_n uzavreny tah, ktery prochazi vsemi hranami. Zduvodnete.

4, Urcte, pro ktere n existuje graf se skore (2,3,3,3...3) (jedna dvojka, n-1 trojek). Zduvodnete.

Kua, je to dobry pocit mat to za sebou... :lol:

Jak jsi dopadl ? A jak dopadli ti co s to psali s tebou a vis jejich vysledky ?

Saff wrote:Jak jsi dopadl ? A jak dopadli ti co s to psali s tebou a vis jejich vysledky ?

O ostatnych neviem nic, pisali sme to asi 40ti, potom rano na 9:00 prislo tak 10-15 ludi (ostatni 10:00 a 11:00), viem akurat ze aspon styria sme mali za 1 a potom som uz zdrhol "domov"...

Isidor wrote: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.

Isidor wrote: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.

Ferro_the_King wrote: Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.

No myslím, že počet nezávislých podmnožin je roven počtu prvků množiny, asi takhle to vypadá {1} {1,2} {1,2,3} {1,2,3,4} ... {1,2...,2005}. tzn 2005, pak myslím, že stačí vytáhnout každou pátou podmnožinu tzn 2005/5 a výsledek asi bude 401. Doufám, že jsem to dobře pochopil a že to tak je, abych tu nemát. Tak to prosím berte s jistou rezervou, a jestli má někdo jiný názor, nechť ho sem prosím napíše!

Ferro_the_King wrote:

Isidor wrote: 2, necht mnozina X={1,2,3...2005}. Jaka je velikost maximalniho systemu nezavislych podmnozin P(X), ve kterem kazda mnozina ma pocet prvku delitelny 5? Zduvodnete (staci, kdyz vhodne upravite dukaz Spernerovy vety na dalsi strane).

Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.

My jsme tohle řešili na cviku. Maximální počet nezávislých podmnožin je kombinační číslo: 2005 nad (celá část(2005/2)). Ale mohutnost těch podmnožin není dělitelná 5, proto si vybereš množiny, který jsou dělitelný 5.
Jejich počet je kombinační číslo: (2005 nad 1000) nebo (2005 nad 1005)

P.S. Neuměl jsem napsat ty vzorce, tak jsem je musel takhle popsat "slovy" :)

to kokso, ani som si nevsimol, ze v 1 po b sme mali aj sude na sude a liche naliche, ja som spravil len s na l a l na s a cudoval sa preco mam pol boda :idea:

Anonymous wrote:

Ferro_the_King wrote: Nemohl by sem nekdo please napsat jak se to melo resit? Jdu na pristi predtermin, ale s timhle prikladem fakt nehnu.

No myslím, že počet nezávislých podmnožin je roven počtu prvků množiny, asi takhle to vypadá {1} {1,2} {1,2,3} {1,2,3,4} ... {1,2...,2005}. tzn 2005, pak myslím, že stačí vytáhnout každou pátou podmnožinu tzn 2005/5 a výsledek asi bude 401. Doufám, že jsem to dobře pochopil a že to tak je, abych tu nemát. Tak to prosím berte s jistou rezervou, a jestli má někdo jiný názor, nechť ho sem prosím napíše!

No tak takhle to neni, delal jsi to presne opacne - mas vybrat takovej system system podmnozin, ze pro zadne dve mnoziny z tohoto systemu neplati ze jedna je podmnozinou druhe... misto antiretezce jsi napsal retezec...