Matrices en grafen > Grafen
123456Grafen

Antwoorden van de opgaven

Opgave V1
a

Doen, teken een sterk vereenvoudigde situatie waarin het alleen gaat om het wel of niet bestaan van een rechtstreekse verbinding tussen twee knooppunten.

b

Geef eerst zelf een antwoord. Bekijk vervolgens de Uitleg .

Opgave 1
a

.

b

c

Tussen 0 en 1. Er is een hoge dichtheid van de verbindingen als de verbindingsgraad dicht bij 1 ligt.

d

e

CS - ND - CS, CS - ZD - CS, CS - BA - CS.

f

.
Welke twee stations je van deze vijf ook kiest, je kunt er altijd rechtstreeks of met één overstap komen.

Opgave 2
a

2

b

Noord en Bijlmer ArenA, Noord en Sloterdijk.

Opgave 3
a

Doen, gebruik je grafische rekenmachine.

b

Er komen in C + C 2 geen nullen meer voor.

c

C-B-E-C en C-E-B-C.

d

Het maximale aantal verbindingslijnen is 5 4 / 2 = 10 . Ontbrekende verbindingen zijn A-B, A-C, A-D en C-D.

Opgave 4
a

De pijlen geven eenrichtingsverkeer aan.

b

Hij is niet symmetrisch in de hoofddiagonaal.

c

D + D 2 = ( 1 0 1 1 1 1 1 2 1 2 1 1 2 1 2 0 1 1 0 1 1 2 1 1 2 ) en D + D 2 + D 3 = ( 1 2 1 1 3 2 3 4 2 5 2 4 3 2 5 1 2 2 1 2 3 2 5 3 4 ) .
Omdat in D + D 2 + D 3 voor het eerst geen nullen meet voorkomen is elk knooppunt met elk ander knooppunt verbonden in 3 of minder stappen.

d

De kortste route van D naar C.

e

5 4 = 20 , vanuit elk knooppunt zijn er 4 directe wegen naar een ander knooppunt. De graad van verbinding is 9 20 .

Opgave 5

De grafen I en III zijn gelijk. Het zijn eigenlijk beide gelijke driehoeken met aan dezelfde hoekpunten nog een extra verbindingsweg.

Opgave 6
a

Doen.

b

C = ( 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 )

c

Even nagaan door C 2 te berekenen vanuit het antwoord bij b.

Opgave 7
a

Ja, altijd is een stemming eenrichtingsverkeer. Je stemt immers altijd op iemand anders.

b

Neem aan "stemmen op" betekent: "de stem gaat van ... naar ..."
Verder doe je het "van" boven en het "naar" links. Dan krijg je:


als de knooppunten op een rij van links naar rechts en in een kolom van onder naar boven alfabetisch zijn gerangschikt.

c

B zou gekozen worden. Hij krijgt de meeste stemmen, zie de som van de kentallen van de tweede rij.

d

e

De matrices K en N optellen. Bepaal de som van de kentallen van de kolommen. Nu hebben en een even goed resultaat en is er een tweede stemronde tussen hen beide nodig.

f

Eigen antwoord.

Opgave 8
a

In de antwoorden wordt de volgorde Papeete (de hoofdstad), Punaauia, Papara, Papeari en Mahina gebruikt. Doen.

b

c

Papeete - Punaauia - Papeete; Papeete - Mahina - Papeete; Papeeta - Punaauia - Papara; Papeete - Mahina - Papeari.

d


Deze matrix geeft aan of plaatsen met elkaar zijn verbonden in één of twee stappen. Kennelijk is dat altijd het geval.

e

Er zijn 5 knooppunten, dus er zijn in totaal 10 wegen mogelijk. Er zijn er slechts 5 getekend. De graad van verbinding is: 5 10 = 0 , 5 .

f

Er zijn veel plaatsen die niet rechtstreeks met elkaar verbonden zijn. De graad van verbinding is laag.

Opgave 9
a

Zie figuur.

b

In de eerste graaf is de verbinding minimaal. In de eerste graaf is de graad van verbinding 5 15 = 1 3 en bij de tweede graaf 6 15 = 2 5 .

c

De diameter in de eerste graaf is 2 en in de tweede is hij 3.

d

De tweede situatie; omdat het eiland erg bergachtig is in het binnenland en alle plaatsen langs de kust liggen.

Opgave 10
a

Er zijn 4 tweestapsverbindingen van dat punt naar zichzelf.

b

Zie de figuur.

c

C = ( 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 )

d

In de graaf is te zien dat de diameter 2 is.

Opgave 11
a

Er zijn verbindingen die een richting hebben.

b

Minstens , bijvoorbeeld is een mogelijkheid.

c

d


Deze matrix geeft het aantal éénstaps-, tweestaps- of driestapsverbindingen tussen twee plaatsen.

e

f

Tel de kentallen van de kolommen in matrix A op. Je vindt dan: 6, 8, 7, 9, 8 en 10. Plaats de zender in F , want je hebt vanuit F de meeste uitzendingen nodig.

Opgave 12
a

b

R + R 2 geeft het totaal van alle één- en tweestapsverbindingen. Er komen nog nullen in voor, want A - E is een driestapsverbinding.

c

Doen.

d

e

De tweestapsverbindingen vanuit E zijn: E - D - E , E - D - C en E - D - B .

f

De graad van verbinding van de graaf is 0,6.

g

Er komen nog twee nullen in voor, want A - E en E - A zijn driestapsverbindingen.

verder | terug