Oblig 11 i IN1150
Espen Noreng
28. april 2022
Oppgave 1
(a)
a
c
e
b
d
(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:
a
b
c
d
(b)3
(
3
2
)
= 27
(c)2
(
3
2
)
= 8
(d)3
(
n
2
)
1
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 2,3,5 og 6 har oddegrad 3.
(b)ja, en hamiltonsykel: 1234561, siden alle nodene blir gått på og vi re-
turner til starten ved siste node altså 1.
Oppgave 6
(a)Nei, fordi noen av nodene har en oddegrad
Ingen tilbakemedlinger enda