Byla v poho..
1:
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í.
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.
c) Definice stromu, nakreslyt vsechny neizomorfní stromi na secti vrcholech.
2: Euleruv vzorec (|V|-|E|-s=2)
Napsat a dokázat.
3: (3,3...3,4,4...4) n trojek a n ctirek, na jake n bude skóre grafu.
4: Jestly muze mit stejne skore:
no...ale ze co tam bylo, ta nevim...stromy, souvisly a 2-souvisly grafy a na konce jeden, ze strom a nerovinny graf. Bylo celkem 7 páru.
Hodne stesti
Písemka 20.1.2006
1c) a 4
1. c) "Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni stromy se sesti vrcholy. (Zduvodnete.)"
4. "Mohou mit dva grafy G1 a G2 stejne skore, jestlize
(a) G1 je souvisily, G2 neni souvisly,
(b) G1 je 2-souvisly, G2 neni souvisly,
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
(d) G1 je strom, G2 neni souvisly,
(e) G1 je strom, G2 je 2-souvisly,
(f) G1 neni rovinny, G2 je kruznice,
(g) G1 neni rovinny, G2 je strom?"
Hint (BEZ ZARUKY!): a) ano, b) ano, c) ne?, d) ne?, e) ne, f) ne, g) ne?
4. "Mohou mit dva grafy G1 a G2 stejne skore, jestlize
(a) G1 je souvisily, G2 neni souvisly,
(b) G1 je 2-souvisly, G2 neni souvisly,
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
(d) G1 je strom, G2 neni souvisly,
(e) G1 je strom, G2 je 2-souvisly,
(f) G1 neni rovinny, G2 je kruznice,
(g) G1 neni rovinny, G2 je strom?"
Hint (BEZ ZARUKY!): a) ano, b) ano, c) ne?, d) ne?, e) ne, f) ne, g) ne?
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 162
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
Re: 1c) a 4
c) anoAnonymous píše:1. c) "Napiste definici izomorfismu grafu. Nakreslete vsechny neizomorfni stromy se sesti vrcholy. (Zduvodnete.)"
4. "Mohou mit dva grafy G1 a G2 stejne skore, jestlize
(a) G1 je souvisily, G2 neni souvisly,
(b) G1 je 2-souvisly, G2 neni souvisly,
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
(d) G1 je strom, G2 neni souvisly,
(e) G1 je strom, G2 je 2-souvisly,
(f) G1 neni rovinny, G2 je kruznice,
(g) G1 neni rovinny, G2 je strom?"
Hint (BEZ ZARUKY!): a) ano, b) ano, c) ne?, d) ne?, e) ne, f) ne, g) ne?
d) ano - G1: cesta z peti vrcholu (1,2,2,2,1) G2: trojuhelnik a dva spojeny body
g) ano - napr. G2: v koreni vetveni na 4 vetve - v tech 4 bodech dalsi vetveni do 3 => 5xvrchol stupne 4 a 12 listu ... G1: K5 a 6 "usecek"
Skvela pisemka, jeste aby tak dopadly principy... :)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
4/c
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,
HINT:
Ja mel za 1, tak mám radost
HINT:
Kód: Vybrat vše
G2:
o---o---o---o { o je vrchol, hrany jsou --- nebo \ nebo / }
\o/ \o/
G1: cyklus delky 6 + jedna hrana.