# Písemka 20.1.2006

<{ForumPost(poster="zehyo", timestamp=2006-01-20 12:00:20)}>
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
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2006-01-20 12:33:55)}>
... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2006-01-20 18:06:10)}>
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?
<{/ForumPost}>

<{ForumPost(poster="Myshaak", timestamp=2006-01-20 19:06:21)}>

 > Anonymous wrote: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... :)
<{/ForumPost}>

<{ForumPost(poster="zehyo", timestamp=2006-01-20 20:34:29)}>

 > Myshaak wrote:... ted jsi me dostal. Ja mel pocit ze tam je def. izomorfismu.

Sorry, mas pravdu..ja to popletl.
<{/ForumPost}>

<{ForumPost(poster="zehyo", timestamp=2006-01-20 20:39:01)}>
(c) G1 je 2-souvisly, zadna komponenta G2 neni 2-souvisla,  
  
HINT:

    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 :)
<{/ForumPost}>