Wiskunde – Grafen
Biotopen
Hoeveel biotopen moeten er opgesteld worden zodat ze elkaar
niet opeten?
Stel een graaf op:
REPTIEL MAG NIET SAMEN
MET
A D, G, H
B C, G
C B, E, F, G, H
D A, E, G, H
E C, D, F
F C, E
G A, B, C, D
H A, C, D
1. Bepaal de graad van elke knoop
deg(A) = 3 deg(B) = 2 deg(C) = 5 deg(D) = 4
deg(E) = 3 deg(F) = 2 deg(G) = 4 deg(H) = 3
2. De knoop met de hoogste graad is C
Verwijder C en alle bogen uit C
Bepaal opnieuw de graad van elke knoop
deg(A) = 3 deg(B) = 1 deg(D) = 4 deg(E) = 2
deg(F) = 2 deg(G) = 4 deg(H) = 3
3. De knoop met de hoogste graad is D
Verwijder D en alle bogen uit D
Bepaal opnieuw de graad van elke knoop
deg(A) = 2 deg(B) = 1 deg(E) = 1
deg(F) = 1 deg(G) = 2 deg(H) = 1
Blijf zo verder gaan:
1
, start Verwijde Verwijde Verwijde Verwijde Verwijde
r knoop r knoop r knoop r knoop r knoop
C D A B E
Deg(A) 3 3 2 / / /
Deg(B) 2 1 1 1 / /
Deg(C) 5 / / / / /
Deg(D) 4 4 / / / /
Deg(E) 3 2 1 1 1 /
Deg(F) 2 1 1 1 1 0
Deg(G) 4 3 2 1 0 0
Deg(H) 3 1 1 0 0 0
4. Vind de weg: H – G – F – E = B – A – D – C
5. Graafkleuring:
Knoop H krijgt kleur rood
Knoop G is geen buur van H wordt ook rood
Knoop F is geen buur van H of G wordt ook rood
Knoop E is een buur van F, krijgt kleur groen
Knoop B is geen buur van E wordt ook groen
Knoop A is geen buur van E of B wordt ook groen
Knoop D is een buur van A en G, krijgt kleur blauw
Knoop C is geen buur van D wordt ook blauw
Zendmasten
Bepaal hoeveel verschillende
verbindingen er moeten gemaakt
worden zodat er storingen zijn.
Stel een graaf op:
ZENDMAST MAG NIET
VERBINDEN MET
A B, D
B A, C, D
C B, D, E, F
D A, B, C, E, G
E C, D, F, G
F C, E
G D, E
1. Doe exact hetzelfde als bij de biotoop
2
Biotopen
Hoeveel biotopen moeten er opgesteld worden zodat ze elkaar
niet opeten?
Stel een graaf op:
REPTIEL MAG NIET SAMEN
MET
A D, G, H
B C, G
C B, E, F, G, H
D A, E, G, H
E C, D, F
F C, E
G A, B, C, D
H A, C, D
1. Bepaal de graad van elke knoop
deg(A) = 3 deg(B) = 2 deg(C) = 5 deg(D) = 4
deg(E) = 3 deg(F) = 2 deg(G) = 4 deg(H) = 3
2. De knoop met de hoogste graad is C
Verwijder C en alle bogen uit C
Bepaal opnieuw de graad van elke knoop
deg(A) = 3 deg(B) = 1 deg(D) = 4 deg(E) = 2
deg(F) = 2 deg(G) = 4 deg(H) = 3
3. De knoop met de hoogste graad is D
Verwijder D en alle bogen uit D
Bepaal opnieuw de graad van elke knoop
deg(A) = 2 deg(B) = 1 deg(E) = 1
deg(F) = 1 deg(G) = 2 deg(H) = 1
Blijf zo verder gaan:
1
, start Verwijde Verwijde Verwijde Verwijde Verwijde
r knoop r knoop r knoop r knoop r knoop
C D A B E
Deg(A) 3 3 2 / / /
Deg(B) 2 1 1 1 / /
Deg(C) 5 / / / / /
Deg(D) 4 4 / / / /
Deg(E) 3 2 1 1 1 /
Deg(F) 2 1 1 1 1 0
Deg(G) 4 3 2 1 0 0
Deg(H) 3 1 1 0 0 0
4. Vind de weg: H – G – F – E = B – A – D – C
5. Graafkleuring:
Knoop H krijgt kleur rood
Knoop G is geen buur van H wordt ook rood
Knoop F is geen buur van H of G wordt ook rood
Knoop E is een buur van F, krijgt kleur groen
Knoop B is geen buur van E wordt ook groen
Knoop A is geen buur van E of B wordt ook groen
Knoop D is een buur van A en G, krijgt kleur blauw
Knoop C is geen buur van D wordt ook blauw
Zendmasten
Bepaal hoeveel verschillende
verbindingen er moeten gemaakt
worden zodat er storingen zijn.
Stel een graaf op:
ZENDMAST MAG NIET
VERBINDEN MET
A B, D
B A, C, D
C B, D, E, F
D A, B, C, E, G
E C, D, F, G
F C, E
G D, E
1. Doe exact hetzelfde als bij de biotoop
2
