1. a) definice transitivní relace + pár příkladů k určení, jestli jde o trans. 1. (a) Definujte tranzitivní relaci na nožině X. Určete, které z následujících tří relací R1,R2,R3 na množině X = {1,2,...} jsou tranzitivní (i) xR1y <=> x (se nerovná) y (ii) xR2y <=> x^2 > y (iii) xR3y <=> x > y^2 (Zdůvodněte) a)pocet prostych zobrazeni strana 57 kolik je zobrazení z X do Y + vysvětlit + moznost PIE (b) Kolik existuje zobrazení (funkcí) z {1,2,3,5,7} do {4,5,6,7,8}. Kolik z nich je bijekcí? Zdůvodněte. a) Co je usporádání na mnozine, a zda je usp.: i) X={1..100} x(R1)y <=> x-y<10 ii) X={1..100} x(R2)y <=> x/y<=10 iii) X je mnozina zobrazení z {a,b,c,d,e} do {1,2,3} f(R3)g <=> f(a)>=g(a), f(c)>=g(c), f(e)>=g(e) HINT: Ani jedno nejni usporádání. jak je definováno n nad k + dokázat nějakou nerovnost (už nevím jakou) ta nerovnost bola (x nad 2) + (y nad 2) =< (x+y nad 2) strana 60 2. Formulace a důkaz binom. věty... strana 63. 1) Zformuluj a dokaž binomickou větu b) Binomiální veta, a pomocí: (sqrt(14^13)-1)(sqrt(14^13)+1) je delitelne 169 HINT: roznasob zavorky, dostanes 14^13-1, a to uz jsme resily v jiném fóru. 1)a) zneni binomicke vety + dokazat s jeji pomoci ze (14^13)-1 je delitelne 169 cez binomicku vetu: 14=1+13, no a dalej to vies rozlozit podla vzorca, jednicky sa zozeru a odvsadial vyjmes 13^2 jenom dodat ze po pozrani je posledni clen (nejmensi) (13nad1)*13^1 coy je 13^2..tohle vzmzslet mi teda dalo trochu zabrat, protoze k tem neco nad neco sem napsal ze to je odpad a pak se divil proc ten posledni ma jen jendu trinactku 2. Zformulujte a dokažte Princip inkluze a exkluze. 3. Máte písmena A,O,K,P,S,T,V,D a máte zjistit kolika způsoby je lze seřadit, aby z nich nešlo sestavit ani jedno ze slov: KOP,PAST,VODA pozn.: př. K .... O .... P ... z takové kombinace lze KOP sestavit.. 2) Vzorec pro pocet permutaci bez pevnyho bodu na mnozine (1..n) a tento vzorec dokazte. (pevny bod je ze napr 1 nesmi byt na prvnim miste) b) definovat indukovany podgraf + kolik nesouvislych indukovanych podgrafu ma graf Km,n b)pocet podgrafu uplneho bipartitniho grafu se stejnym poctem vrcholu c)zda muze mit strom a 2-souvisly graf stejny skore co je skóre + 2 neizomorfní stromy se stejným skóre c) definice stromu + dokazat ze strom s vrcholem stupne 4 ma aspon 4 listy 2) Co je to kostra a najdi graf s právě 6ti kostrami Co 3ky týče, ta byla težší, ale měl jsem nápad. Pro strom to totiž platí - má minimálně dva listy, které můžeš sebrat bez porušení souvislosti. No a pro jiný graf si najdeš kostru. Ta je strom a tak má aspoň 2 listy. No a pak mi jen trvalo, než jsem si uvědomil, že je můžu utrhnout bez obav, a zbytek grafu dostanu zpětným dodáním hran - čímž určitě neporuším souvislost. b) definice stromu + dk. ze strom s vrcholem stupně 4 má alespoň 4 listy 1. c) "Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni stromy se sesti vrcholy. (Zduvodnete.)" (c) Napište definici izomorfismu grafů. Nakreslete všechny neizomorfní stromy se čtyřmi vrcholy a všechny neizomorfní stromy s pěti vrcholy. Zdůvodněte. 3)pocet neizomorfnich grafu na 8 vrcholech ktery maj skore slozeny z 0,2,7 Prázdný graf, graf s 8 dvojkama a úplný na 8 vrcholech, to jsou 3 a každý je složen jen ze stejných číslic. A pak musíš rozmyslet kombinace. A protože k 7 už nic nepřihodíš, protože je úplný, zbývají ti kombinace 0 a 2 na 8 vrcholech. Buď nějak dopočítat nebo rozmyslet. Budou to kružnice a pak vždycky izolované vrcholy + třeba další kružnice (dva ctverecky nebo dva trojuhelnicky a 2 izolovane) Tak s tím grafem s 8 dvojkama jsem tě trochu mystifikoval, ono jich je sakra víc Smile konkrétně jsem myslel kružnici. A taky existujou kombinace se 7 vrcholem. Bez těch možností se 7 je jich dvanáct, zkusim ještě zbytek No a těch 7 musí být sudý počet, graf se 2 sedmama a zbytkem 2 je jen jeden a víc to nejde. Necht pro n >= 1 znaci symbol Gn graf, jehoz vrcholy jsou vsechna slova delky n nad triprvkovou abecedou {a,b,c} (napr: pro n = 5 jeden takovy vrchol je slovo aacbb) a dva vrcholy tvori hranu, prave kdyz se dve odpovidajici slova lisi na jedinem miste a jinak se shoduji. Rozhodnete, pro ktere n = 1,2,... se graf Gn da nakreslit jednim uzavrenym tahem bez opakovani hran. 2: Euleruv vzorec (|V|-|E|-s=2) Napsat a dokázat. strana 181 . najít nesouvislý rovinný graf s 9 vrcholy a 18 hranami c) definice barevnosti a pár grafů určit barevnost 2)veta o 5 barvach - dukaz 2. důkaz věty o 5 barvách 3. Dokažte větu o 4 barvách pro každý rovinný graf bez trojúhelníku. Můžete použít jakékoliv tvrzení dokázané na přednášce, aniž byste je dokazovli. (Návod: Využijte toho, že rovinný graf bez trojúhelníku nemá "příliš mnoho" hran a proto má vrcholy "malého stupně".) 3: (3,3...3,4,4...4) n trojek a n ctirek, na jake n bude skóre grafu. 4. Pro každé "n" rozhodněte, zda existuje v grafu na "n" vrcholech se skóre (3,3,...,3) (n trojek). (Zdůvodněte) 4)pro ktery souvisly grafy plati: u,v,w libovolne ruzne vrcholy G pak d(u,v) 5xvrchol stupne 4 a 12 listu ... G1: K5 a 6 "usecek" (c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla, ) Dokaž, že pro každý souvislý graf G existují 2 vrcholy u, v, že G-u, G-v, i (G-u)-v jsou souvislé 3) Mohou mit dva grafy stejne skore, pokud a) 2-souvisly, nesouvisly b) strom, nesouvisly c) nerovinny, kruznice d) nerovinny strom 4. počet koster grafu složenýho z K5, K4, K3, vždycky jeden vrchol měli společnej