Diskreetti matematiikka, syksy 2010
Harjoitus 8 (11.-12.11., to 16-18 ja pe 12-14 M107)

Torstaina 4.11. olemme demoajan klo 16-18 tietokoneluokassa MP103. Teemme Matlab-demoja 2-3. Matlab-demot (yhteensä nelisen tilaisuutta) ja niihin liittyvät lisäkotitehtävät rinnastetaan kotitehtäviin, niistä saa siis rukseja. Tavallisia demojahan emme ehdi pitää kuin noin 12 kpl. Hyppäämme myös lukuteorialuvun 11 yli.
 
1. kertauskuulustelu ke 10.11. on luentoaikaan klo 12-14 salissa M102 (tulkaa paikalle niin, että voimme aloittaa tasalta). Koealue on monisteen luvut 1-10, vastaavat demot 1-7.
 
Toinen kertauskuulustelu on ke 8.12. klo 12-14 salissa M103.

  1. Tarkastellaan oheista verkkoa G = (X, E, Y):
    2. DM0904_02.png
    a) Määritä solmujen asteet.
    b) Muodosta vastaavuuskuvaus Y.

     
  2. Tarkastellaan edelleen tehtävän 1 verkkoa G.
    3. a) Määritä verkon pisin ketju ja pisin suljettu ketju.
    b) Määritä pisin suljettu kaarijono.

     
  3. Muodosta tehtävän 1 verkolle yhteys- (eli vierekkäisyysmatriisi) ja vastaavuusmatriisi.

    4.  
  4. Määritä tehtävän 1 verkolle G solmujoukon {x1, x3, x4} virittämä aliverkko G¢. Mikä on verkon G¢ komplementin yhteysmatriisi?

    5.  
  5. Olkoon G = (X,E,Y) suuntaamaton verkko, jonka yhteysmatriisi on
    6. MG =  æ
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    ç
    è
    0 
    1 
    0 
    1 
    1 
    0 
    1 
    1
    1 
    1 
    0 
    1 
    0 
    1 
    1 
    1
    0 
    0 
    1 
    1 
    1 
    1 
    1 
    1
    1 
    1 
    1 
    0 
    1 
    1 
    1 
    0
    1 
    0 
    1 
    1 
    0 
    0 
    1 
    1
    0 
    1 
    1 
    1 
    0 
    0 
    0 
    1
    1 
    1 
    1 
    1 
    1 
    0 
    1 
    0
    1 
    1 
    1 
    0 
    1 
    1 
    0 
    0
    		ö
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ÷
    ø
    a) Onko G yksinkertainen?
    b) Onko G täydellinen?
    c) Mikä on verkon G komplementin matriisi?

     
  6. Miten verkon yhteysmatriisista näkyy seuraavat asiat:
    7. a) Mitkä ovat solmujen asteet?
    b) Onko verkko yksinkertainen?
    c) Onko verkko täydellinen?

     
  7. Olkoon G = (X,E,Y) yksinkertainen suuntaamaton verkko ja G¢=(X,E¢,Y¢) sen komplementti. Olkoon verkossa G n solmua, joista vain yksi on parillista astetta. Kuinka monta paritonasteista solmua on verkossa G¢?

    8.  

File translated from TEX by TTH, version 3.33.
On 02 Nov 2010, 11:15.