Hallo tenniskampioenen,

FUNDAMENTELE INFORMATICA 1/2
testje Grafen
Vrijdag 10 oktober, 2014, 11.15
Antwoorden
Vraag 1 Graaf G = ({p, q, r, s, t, u}, E) met E gegeven door
p
p 0
q
1
r
0
s
1
t 1
u 0

q
1
0
1
0
1
0
r
0
1
0
0
1
1
s
1
0
0
0
1
0
t u

1 0
1 0

1 1

1 0

0 1
1 0
p
q
r
s
t
u
De graad (aantal incidenties) van q is 3 en deg(t) = 5.
Het pad p, q, t, r, u, t, s.
is niet gesloten: het beginpunt is niet ook het eindpunt.
is niet een simpel pad: knoop t komt twee keer voor.
is wel een trail: elke tak langs het pad komt een keer voor.
G geen Eulerse graaf: er is geen gesloten traversable trail die alle takken een
keer passeert, want niet alle knopen zijn van even graad.
G heeft een Hamiltons circuit, bijvoorbeeld p, q, r, u, t, s, p.
De afstand tussen p en u is 2 (de lengte van een kortste pad als p, t, u).
De diameter van G is het maximum van alle afstanden tussen twee knopen
van G, dus 2.
De deelgraaf van G ge¨ınduceerd door de knopen p, q, r en t
G als gerichte graaf (volgens het alfabet) en een lus (t, t).
p q

p
q
r
p 0 1
q
0 0
0 0
r
t

s
0 0
t 0 0
u 0 0
Vraag 2 K4 de volledige graaf met 4 knopen:
en daarnaast
r
0
1
0
0
0
0
s
1
0
0
0
0
0
t u

1 0
1 0

1 1

1 0

1 1
0 0

Download Report