Oppgave 1

Graf med 6 noder

Fra hver av de seks nodene går det en kant til hver av de fem andre nodene. Men da tar vi med en og samme kant to ganger. Antallet kanter blir derfor 6·5 / 2 = 30 / 2 = 15.

Oppgave 2

Grafen i Figur 11.1.1 a): Vi ser fort at antallet kanter n = 12. Nodene A, B, C, E, F og G har alle grad 3 og noden D har grad 6. Summen blir 6·3 + 6 = 24. Det er det samme som 2·n = 2·12 = 24.

Grafen i Oppgave 1: Grafen har n = 15 kanter. Hver av de seks nodene har grad 5. Summen blir 30 som er lik 2·n = 2·15 = 30.

Oppgave 3

Det er 11 forskjellige veier fra A til G. Den korteste (lengde 8) er A, C, F, G. Det er to som er lengst (lengde 11): A, D, G og A, C, D, G.

A, B, E, G  - 9   A, B, D, E, G  - 9   A, B, D, G  - 10   A, B, D, F, G  - 9
A, D, E, G  - 10   A, D, G  - 11   A, D, F, G  - 10
A, C, D, E, G  - 10   A, C, D, G  - 11   A, C, D, F, G  - 10   A, C, F, G  - 8

Noden A er en kilde og G er et sluk.