Diskreetti matematiikka, syksy 2010
Harjoitus 11 (pe 3.11. klo 12-14 M107)

Ennakkotietoja lopunajan meiningistä (salivaraukset ovat osin hämärän peitossa vielä)
Luentoja on jäljellä ti-ke 30.11. ja 1.12. sekä loppuajan vajetta korvaava to 2.12. klo 12-14 tai 14-16 ja Matlab-demo 4 klo 16-18, koskien verkkoja.
Laskuharjoitukset 12-13 ovat yhdessä ryhmässä luentoaikaan tiistaina 7.12. klo 16-18 salissa M102.
Toinen kertauskuulustelu on keskiviikkona 8.12. klo 12.00-14.00 salissa M102, alkaen tasalta.
Koealue: Pääpiirteissään monisteen luvut 12-18. Pääpaino on kuitenkin niissä (ala)luvuissa, joista on kotitehtäviäkin (tarkemmin sähköpostiviestissä).


  1. Aseta 8 nollaa ja 8 ykköstä renkaaksi niin, että jokainen yhdistelmä 0000, 0001, ..., 1111 esiintyy täsmälleen kerran.
    2. Vihje: Tulkitse de Bruijnin jonon etsimiseksi sopivassa aakkostossa, sopivalle sanapituudelle.

     
  2. Olkoon G äärellinen suunnattu juurellinen puu, jossa on k lehteä, h haarasolmua ja jokaisella haarasolmulla d kappaletta seuraajia. Osoita, että (d-1)h = k-1.

    3.  
  3. Näytä seuraavat verkot isomorfisiksi määritelmän mukaan, ts. keksi sopivat bijektiot solmujoukkojen ja kaarijoukkojen välille, sekä tarkasta sitten itse isomorfisuusvaatimus.
    4. DM0904_06.png

     
  4. Ovatko seuraavat verkot isomorfiset?
    5. DM1204_6.png

     
  5. Piirrä kaikki suunnatut puut, joilla on solmut 1, 2, 3 ja 4 sekä juurena solmu 1. Kuinka monta eri isomorfiatyyppiä niitä on?

    6.  
  6. Onko seuraavan matriisin kuvaama verkko tasoverkko?
    7. æ
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    è
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    0 
    1 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    1 
    0 
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    0 
    0 
    0 
    0 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    1 
    1 
    0 
    1 
    0 
    1 
    1 
    1 
    0 
    0 
    0 
    0 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    0 
    1 
    0 
    0 
    1 
    0 
    1 
    0 
    0 
    0 
    0 
    1 
    1 
    0 
    0 
    0 
    1 
    0 
    0 
    0 
    0 
    1 
    0 
    0 
    0 
    0 
    0 
    0 
    1 
    1 
    1 
    0
    		ö
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ø

     
  7. Etsi lyhimmät ketjut verkon
    8. DM1204_8.png
    solmusta A muihin solmuihin.

     
  8. Etsi tehtävän 7 verkosta minimaalinen virittävä puu
    9. a) Primin menetelmällä.
    b) Krushkalin menetelmällä.
     

File translated from TEX by TTH, version 3.33.
On 24 Nov 2010, 00:54.