Matrices en grafen

Matrices en grafen > Grafen

Uitleg

Het metronetwerk van Amsterdam is een graaf met knooppunten (de stations) en verbindingen (de spoorlijnen). Bekijk alleen de stations 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 overstappen) verbinding tussen twee stations is.

Deze graaf geeft de metroverbindingen tussen de stations Centraal, Zuid/WTC, Isolatorweg, Westwijk, Gein en Gaasperplas 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 verbindingen mogen ook best kromme lijnen zijn, de graaf verandert niet.

Je kunt bij deze graaf een verbindingsmatrix $C$ opstellen. In $C$ 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 verbinding werkt in beide richtingen.

De graad van verbinding van een verbindingsgraaf is het aantal bestaande verbindingen (hier $8$ ) gedeeld door het totaal aantal mogelijke verbindingen (hier $6 \cdot 5 / 2 = 15$ ).

Opgave 1

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

Stel zelf de bijbehorende verbindingsmatrix $C$ op .

Bereken de graad van verbinding van deze graaf.

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

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

Schrijf alle tweestapsverbindingen vanuit het Centraal Station op.

Welke betekenis heeft de matrix $C + C^{2}$ ? Waarom komen er in deze matrix nog nullen voor?

Welke driestapsverbindingen zijn er vanuit het Centraal Station mogelijk?

Komen er in de matrix $C + C^{2} + C^{3}$ ook nog nullen voor? Waarom?

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.

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

Van twee plaatsen die 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