moje zadani:
zadani c.2:1) Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni grafy s nejvyse tremi vrcholy. Nakreslete take vsechny neizomorfni stromy s peti vrcholy.
2) Dokazte vetu charakterizujici orientovane grafy, ktere maji uzavreny orientovany eulerovsky tah
3) pro prirozena cisla n=1,2..... urcete pocet vsech usporadanych dvojic (A,B) takovych ze A (je podmnozinou) B (je podmnozinou) {1,2,......,n}
4) kolik je vzajemne neizomorfnich grafu s 8 vrcholy, jejichz kazdy vrchol ma stupen 0 nebo 2 nebo 7?
1) napiste zneni bin. vety. Rozvinte dle ni vyraz (x - 1/2y)^4 (numericky dopocitejte)
2) uvedte eulerovu formuli vcetne predpokladu a s jeji pomoci ukazte, ze kazdy rovinny graf obsahuje alespon jeden vrchol stupne nejvyse 5.
3) necht uplny graf Kn na mnozine vrcholu {1,2,.....,n} ma hranu {i,j} ohodnocenou cislem i+j. naleznete minimalni kostru a spoctete jeji vahu.
4) dokazte vetu o 4 barvach pro kazdy rovinny graf bez trjuhelniku. S vyjimkou vety o ctyrech barvach muzete pouzit jakekoliv tvrzeni z prednasek, aniz byste je dokazovali. (navod: vyuzijte toho, ze rovinny graf bez trojuhelniku nema "prilis mnoho" hran a proto ma vrchol "maleho" stupne)
zadani c.3:
1) napiste definici tranzitivni relace na mnozine X. urcete , ktere z nasledujicich 3 relaci R1,R2,R3 na mnozine X = {1,2,.....} jsou tranzitivni (zduvodnete.):
(a) xR1y <=> x=y+1
(b) xR2y <=> |x-y| je sude cislo
(c) xR3y <=> x>y/2
2) zformulujte princip I a E a dokazte ho. Uvedte presnou formulaci ("pro kazde n >= 1 a pro kazdych .....").
3) ktere z nasledujicich vyroku jsou spravne? zduvodnete (samozrejme).
(a) grafy G a H jsou isomorfni, prave kdyz existuje bijekce f: E(G) -> E(H)
(b) jestlize jsou grafy G a H isomorfni, pak existuje bijekce f: V(G) -> V(H) takova, ze kazdy vrchol u(patrici do V(G)) ma stejny stupen jako f(u).
4) pro kazde n rozhodnete, zda existuje graf se skore (2,2,.....,2,3,3,.....,3) (n dvojek a n trojek)
zadani c.4:
1) definujte pojem bipartitniho grafu. Kdy je graf Cn (kruznice na n vrcholech) bipartitni? (zduvodnete)
2) zformulujte a dokazte spernerovu vetu o maximalni velikosti systemu nezavislych podmnozin n-prvkove mnoziny.
3) dokazte vetu o 4 barvach pro kazdy rovinny graf bez trojuhelniku. s vyjimkou vety o ctyrech barvach muzete pouzit jakekoliv tvrzeni z prednasek, aniz byste je dokazovali. (navod: vyuzijte toho, ze rovinny graf bez trojuhelniku nema "prilis mnoho" hran a proto ma vrchol "maleho" stupne)
4) je dana relace O na mnozine Z. Rozhodnete, zda O je reflexivni, symetricka, antisymetricka a tranzitivni relace:
(a) xOy <=> x^2 = y
(b) xOy <=> 3|(x+2y)
(c) xOy <=> |x| < |y|
(d) xOy <=> |x| >= |y| (vetsi nebo rovno)
doufam ze jsem vam alespon trosku pomohl, ja uz to mam zdarne za sebou tak preji vam hodne stesti.
Jo a Kral je fakt v pohode...
ja jsem dostal toho orientovaneho eulera a to je fakt vec kterou jsem dostat nechtel ... vpodstate nic jsem o tom nerekl bo jsem se v tom sam nejak totalne zamotal ze uz jsem pak ani nevedel jak to chci vlastne dokazat tak jsem to vzdal ... mno a ten priklad 3 ze zadani 1 ma vyjit 3^n ja se k tomu nedobabral, i kdyz posleze si myslim jsem byl uz na dobre ceste, tak mi to kral ukazal ...
no proste jsem to dal pod me ocekavani veril jsem si vic 