Oppgave 4

Her er det ingen fasit i den forstand at det kun er ett minimalt spenntre. Det er mange, men alle har samlet kantvekt på 29. Det er rekkefølgen som vi ser på kanter med samme vekt, som avgjør dette. Det kan f.eks. gjøres slik:

Alle kantene med vekt 2 må være med, dvs. (A,B,2), /A,D,2) og (E,G,2). Så ser vi på de med vekt 3. (B,D,3) kan vi ikke ta med for det vil gi A,B,D,A som sykel. Vi tar med (A,C,3) og (G,H,3). Så de med vekt 4. (B,E,4) tar vi med, men ikke (D,G,4) siden det gir A,B,E,G,D,A som sykel. Videre tar vi med (F,I,4) og (I,J,4). Vi er ikke ferdig ennå siden vi har to disjunkte trær. Vi kan ikke ha med (C,D,5), (D,E,5) og (E,H,5). Men (F,G,5) tar vi med og dermed får vi ett tre. Sammenlagt vekt er 2 + 2 + 2 + 3 + 3 + 4 + 4 + 4 + 5 = 29.

Data for grafen:

A B 2 C 3 D 2
B A 2 D 3 E 4
C A 3 D 5 F 7
D A 2 B 3 C 5 E 5 F 6 G 4
E B 4 D 5 G 2 H 5
F C 7 D 6 G 5 I 4
G D 4 E 2 F 5 H 3 I 6 J 7
H E 5 G 3 J 5
I F 4 G 6 J 4
J G 7 H 5 I 4

Oppgave 6

Se løsningsforslaget for Oppgave 4 i Avsnitt 11.2.5.