Tietorakenteet / syksy 2009 / Linna

Harjoitus 4, viikko 40

1. Kun binääripuu piirretään kuvaruudulle, täytyy jokaiselle solmulle laskea positio, johon se sijoitetaan. Eräs mahdollisuus voisi olla käydä solmut läpi sisäjärjestyksessä ja asettaa jokaiselle solmulle tämän järjestyksen mukainen positio. Sitten solmut piirrettäisiin tasoittain näihin positioihin.

Esim.

A

/ \

B G

/ \ / \

P R F H

/ \ \

L S J

Järjestysnumerot olisivat P:1, B:2, L:3, R:4, A:5, F:6, S:7, G:8, H:9, J:10.

Nyt käytäisiin läpi puu taso kerrallaan ja aina taso piirrettäisiin riville järjestysnumeron mukaiseen positioon.Tuloksena olisi seuraavanlainen puu (huom:viiva (-) tarkoittaa tyhjää).

----A

-B-----G

P--R-F--H

--L---S—-J

Tee ohjelma, jolla voisit tehdä tämän puun tulostuksen teksti-ikkunaan. (tarvitset hieman muutoksia solmuun – lisää siihen tämä positiotieto. Voi olla kätevää lisätä solmuun myös tieto siitä, millä tasolla se on).

2. a) Olkoon G = (V,E) suunnattu graafi, missä V = {A, B, C, D} ja E = {(A,C), (A,D), (B,C), (C,D), (D,B)}

b)Olkoon G = (V,E) suunnattu graafi, missä V = {A, B, C,D} ja E = {(A,A), (A,B), (A,C), (B,A), (B,B), (B,C), (C,A), (C,B), (C,C)} (siis D:hen ei tule eikä siitä lähde yhtään kaarta).

Esitä ylläolevat verkot käyttäen vierusmatriisia ja vieruslistoja.

3. Suunnattu verkko on talletettu viruslistoja käyttäen.Laadi algoritmi Isolate(A,i), joka poistaa verkosta A kaikki solmusta I alkavat ja siihen päättyvät kaaret.

4. Seuraavat ehdot määrittelevät erään osittaisen järjestyksen:

1<3, 1<4, 1<6, 2<4, 2<7, 3<6, 4<5, 4<6, 5<9, 7<5, 7<8, 7<10, 8<10, 9<10.

Anna kaksi erilaista topologista järjestystä, jotka ovat tämän osittaisen järjestyksen mukaisia. Mitkä annetuista ehdoista voitaisiin poistaa osittaisen järjestyksen muuttumatta? Havainnollista osittaista järjestystä verkolla.

5. Laadi algoritmi, joka muodostaa annetulle verkolle jonkin virittävän puun. Valitse sopiva verkon ja puun esitystapa.

6. Määritellään painotettu suuntaamaton verkko seuraavasti. Verkon solmuina ovat solmut 1, 2, 3, 4, 5, 6, 7, 8, 9 ja 10. Sivut ja niiden painot ovat (1,2)paino1, (1,3)3, (1,4)2, (2,4)2, (2,7)2, (2,8)3, (3,4)3, (3,5)2, (4,5)1, (4,6)3, (4,8)2, (5,6)1, (7,8)3, (7,9)3, (8,9)4, (8,10)4, (9,10)3.

Etsi lyhin reitti solmusta 1 solmuun 10 simuloimalla Dijkstran algoritmia.

7. Sovella Primin algoritmia tehtävän 2 verkkoon.