Písemka 20.1.2006

[zehyo]

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

[Myshaak]

... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.

[Návštěvník]

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?

[Myshaak]

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?

c) ano
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... :)

[zehyo]

... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.

Sorry, mas pravdu..ja to popletl.

[zehyo]

(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,

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.

Ja mel za 1, tak mám radost