Diskreetti matematiikka, syksy 2010
Harjoitus 10 (25.-26.11, to 16-18 M107, pe 12-14 M107)
  1. Etsi virittävät puut suuntaamattomalle verkolle G = (X, E, Y), kun
    2. X : = {x, y, z, t},
    E : = { {x, y}, {x, z}, {x, t}, {y, t}, {z, t} },
    ja Y on identtinen kuvaus.
  2. Olkoon G = (X, E, Y) suuntaamaton verkko, jossa on n solmua, m kaarta ja p yhtenäistä komponenttia. Osoita, että
    3. m ³ n - p,
    ja että yhtäsuuruus pätee jos ja vain jos G on metsä.
  3. Osoita, että äärellisessä suuntaamattomassa puussa, joka ei ole pelkästään yksi solmu, on ainakin 2 solmua, joiden aste on 1.
  4. Etsi virittävät puut depth-first- ja breadth-first-menetelmillä suuntaamattomalle verkolle G, jonka matriisi on
    5. MG : =  æ
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    è
    1 
    0 
    2 
    0 
    0 
    0 
    0 
    1 
    1 
    0 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    1 
    2 
    0 
    0 
    1 
    0 
    0 
    1 
    0 
    0 
    0 
    0 
    1 
    1 
    1 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    1 
    1 
    0 
    1 
    0 
    0 
    1 
    0 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    1 
    0 
    1 
    1 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    1 
    1 
    1 
    0 
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    1 
    1 
    0
    		ö
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ø
  5. Olkoon G = (X, U, Y) suunnattu verkko, jossa ei ole erillisiä solmuja, ja jossa on nuolet
    6. {(a,b), (a,c), (a,f), (b,a), (b,d), (b,f), (c,b), (c,d), (c,f), (d,e), (e,d), (e,e), (e,f)}
    a) Piirrä verkko nuolikaaviona.
    b) Muodosta verkon G yhteysmatriisi.
  6. Onko tehtävän 5 verkko G
    7. a) yksinkertainen tai täydellinen?
    b) yhtenäinen tai vahvasti yhtenäinen? Jos ei, määritä komponentit.
    c) Eulerin verkko?
    d) Hamiltonin verkko?
    Vihje: Yhtenäisyys: tarkastele vastaavaa suuntaamatonta verkkoa. Vahva yhtenäisyys: Tarkastele solmujoukon osajoukkojen virittämiä aliverkkoja.
  7. Olkoon G äärellinen suunnattu verkko yhteysmatriisina M. Osoita, että arvoilla k Î N tulomatriisin (bij)n×n : = Mk alkio bij ilmoittaa erilaisten k-pituisten nuolijonojen xi® xj lukumäärän.
    8. Vihje: Rakenna induktiotodistus nuolijonon pituuden suhteen.

File translated from TEX by TTH, version 3.80.
On 16 Nov 2010, 15:48.