Oblig 11 IN1150

Oblig 11 i IN1150

Espen Noreng

28. april 2022

Oppgave 1

(a)

c

b

(b)Nei. Kantene{a, e},{a, d},{c, b}og{b, d}mangler for at G skal være en

komplett graph.

(c)Nodene og kantane til

Ger komplementet til G

Oppgave 2

(a)Den rette grafen G har nodene V ={a, b, c, d}og kantene E ={⟨a, b⟩,⟨b, c⟩,⟨c, d⟩}

og kan tegnes slik:

b

d

(b)3

3

)

= 27

(c)2

3

)

= 8

(d)3

n

)

Oppgave 3

(a)6

(b)10

(c)12

(d)0, alle nodene er isolert.

Oppgave 4

(a)Ikke isomorfe, grafen G har flere noder enn grafen i oppgave a.

(b)Isomorf, funksjonen f, slik at f(5) = e, f(2) = o, f(4) = i, f(1) = s og

f(3) = f er en isomorfi.

(c)Isomorf, funksjonen f, slik at f(2) = t, f(3) = a, f(4) = i, f(5) = b og

f(1) = s er en isomorfi.

(d)Ikke isomorfe, i grafen G har alle noder to kanter, mens node b kun

har 1 kant i oppgave d.

Oppgave 5

(a)Nei, hverken en eulervei eller en eulersti. Det er ikke mulig å komme

seg over alle kantene, uten å krysse noen kanter flere ganger. Dette

blant annet på grunn av at nodene