Diskreetit rakenteet (ITKP105)

6. DEMOT (viikko 8)

1. a) Piirrä kaikki keksimäsi keskenään ei-isomorfiset yhtenäiset yksinkertaiset 5-solmuiset verkot, joissa on 6 väliä.

b) Mikä on pienin verkko, jolla ei ole mitään väliä?

2. Tee JOKO a)-kohta TAI b-kohta:

a) Ohessa viime demojen matriisi A, joka esitti verkkoa G. Käsittele viivat nollina ja laske summa A+A ja tulo A2.

A B C D E F

A - 1 - 1 - -

B 1 - 1 - 1 1

C - 1 - - 1 -

D 1 - - - - 1

E - 1 1 - - 1

F - 1 - 1 1 -

Sama matriisi gif-kuvana täällä.

b) Piirrä “euroduaali” eli kaikki nykyiset EU-maat verkkona siten, että jokainen maa on solmu ja mikäli kahden maan välisen rajan voi ylittää autolla niin maita yhdistää väli.

3. Tee kohta a) TAI kohta b):

a) Mitkä yllä olevista kolmesta verkosta ovat tasoverkkoja ja mitkä keskenään isomorfisia verkkoja?

b) Hae lyhin polku solmusta A solmuun H alla olevasta verkosta.

4. a) Piirrä väliverkko ja komplementti yllä oikealla olevalle verkolle.

b) Merkitse verkon mahdolliset leikkaussolmut ja sillat.