Matrices en grafen > Grafen
123456Grafen

Uitleg

Het metronetwerk van Amsterdam is een graaf met knooppunten (de stations) en verbindingen (de spoorlijnen).

Bekijk alleen de stations Noord, Centraal, Zuid/WTC, Isolatorweg, Westwijk, Gein en Gaasperplas. Stel je voor dat er geen andere stations zijn. Je kunt dan deze graaf maken. De genoemde stations zijn de knooppunten van de graaf en de verbindingslijnen geven aan of er een rechtstreekse (zonder tussenstation) verbinding tussen twee stations is. Dat kunnen er meerdere zijn, er wordt ook dan maar één verbinding getekend.

Deze graaf geeft de metroverbindingen tussen de stations Noord, Centraal, Zuid, Sloterdijk en Bijlmer ArenA weer. Er staan geen getallen bij, een verbindingslijn betekent een rechtstreekse (zonder overstappen) verbinding tussen twee stations.
Je kunt de knooppunten rustig verplaatsen en de wegen mogen ook best kromme lijnen zijn, de graaf verandert wel van vorm, maar niet van betekenis.

Je kunt bij deze graaf een verbindingsmatrix C opstellen.
Daarin vind je het aantal éénstapsverbindingen tussen twee punten, in C 2 het aantal tweestapsverbindingen (verbindingen met één overstap) tussen twee punten, enz.
Een verbindingsmatrix is altijd vierkant en symmetrisch t.o.v. de hoofddiagonaal want elke weg werkt hier in beide richtingen.

De graad van verbinding van zo'n graaf is het aantal bestaande verbindingen (hier 7) gedeeld door het totaal aantal mogelijke verbindingen (hier 5 4 / 2 = 10 ).

Opgave 1

Bekijk in de Uitleg hoe van de metroverbindingen tussen 5 stations in Amsterdam een graaf is gemaakt.

a

Stel zelf de bijbehorende verbindingsmatrix C op .

b

Bereken de graad van verbinding van deze graaf.

c

Tussen welke waarden kan de graad van verbinding van een graaf liggen? Wanneer is er sprake van een hoge "dichtheid" van de verbindingen?

d

Bereken C 2 . Leg uit waarom deze matrix alle zogenaamde tweestapsverbindingen in de graaf weergeeft.

e

Schrijf alle tweestapsverbindingen vanuit het Centraal Station op.

f

Welke betekenis heeft de matrix C + C 2 ? Waarom komen er in deze matrix geen nullen voor?

Opgave 2

Onder de "diameter" van een graaf versta je het maximale aantal stappen dat nodig is om vanuit een willekeurig knooppunt in een willekeurig ander knooppunt te komen.

a

Hoe groot is de diameter van de graaf van de vorige opgave?

b

Van twee plaatsen die minstens net zoveel stappen van elkaar verwijderd liggen als de diameter van de graaf bedraagt, zeg je dat ze diametraal liggen. Noem alle plaatsen die diametraal liggen.

verder | terug