Home   Lessen online Functies en Grafieken Onderwerpen  
kader_rand
Startpagina
Bravenet

Matrices en Determinanten Meerstapsmatrices
  

MD-Menu


Grafen
Een graaf bestaat uit een eindig aantal punten waarvan voor ieder tweetal bekend is of er een rechtstreekse verbinding tussen bestaat. Zo'n verbinding geeft een bepaalde relatie tussen de punten aan. In de geografie worden grafen gebruikt om bijvoorbeeld de onderlinge bereikbaarheid van steden aan te geven. Je zou ook kunnen denken aan elektriciteitscentrales die door middel van hoogspanningskabels met elkaar verbonden zijn.  Een punt in een graaf noemen we een knoop (Engels: vertex) en een verbindingslijn wordt een kant (Engels: edge) genoemd.

Er wordt onderscheid gemaakt tussen:

  • Simpele grafen

  • Niet-simpele grafen

In figuur 1 en 2 zie je een een paar voorbeelden.

           

Bij simpele grafen loopt er maximaal één verbindingslijn tussen twee punten en zijn er ook geen lussen. Afhankelijk van de toepassing kunnen de verbindingslijnen gericht zijn, dan worden ze ook wel pijlen genoemd. Ook kunnen punten met zichzelf verbonden zijn, we spreken dan van lussen. In figuur 3 zie je een voorbeeld van een graaf waarin pijlen voorkomen. Je zou hierbij kunnen denken aan een wegennet waarvan sommige wegen éénrichtingsverkeer hebben.

Omhoog


Diameter van een graaf
Bij het aanleggen van een wegennet is het van belang om in een minimaal aantal stappen van de ene naar de andere plaats te kunnen komen. Bovendien moet natuurlijk ook elke plaats bereikbaar zijn. De punten in de graaf moeten dus allemaal onderling verbonden zijn. Dit betekent niet dat elk punt rechtstreeks met elk ander punt verbonden hoeft te zijn. In de graaf van figuur 3 is A via B en D verbonden met C. We noemen zo'n graaf een samenhangende graaf. Bij het bestuderen van grafen zijn een aantal termen van belang:

  • Een wandeling tussen twee verbonden punten P en Q is een rijtje punten met wegen ertussen waardoor P en Q verbonden zijn. In een wandeling mag je een weg niet in twee verschillende richtingen doorlopen. Onder de lengte van de wandeling verstaan we het aantal wegen waaruit de wandeling bestaat.

  • Een pad tussen twee verbonden punten P en Q is de kortste wandeling tussen P en Q (of één van de kortste wandelingen als er meerdere van dezelfde lengte zijn).

  • De afstand tussen twee punten P en Q is de lengte van het pad tussen P en Q.

Onder de diameter van een graaf verstaan we nu de lengte van het langste pad (het maximum van de lengtes van alle paden). Of anders geformuleerd: Bepaal je in een graaf het minimale aantal stappen tussen elk tweetal punten, dan is de diameter dus het grootste aantal dat hierbij voorkomt. De diameter zegt dus iets over de onderlinge bereikbaarheid van de punten in een graaf. We zullen hierna een methode bespreken om m.b.v. het online computerprogramma op deze webpagina de diameter van een graaf te bepalen. In schoolboekjes wordt dezelfde methode behandeld maar daar moet je alles met de hand uitrekenen.

Omhoog


Directe-wegenmatrix
Om met de gegevens uit de graaf te kunnen rekenen stellen we een zgn. directe-wegenmatrix op. In een directe-wegenmatrix staat het aantal rechtstreekse verbindingen tussen elk tweetal punten. Hieronder zie je de directe-wegenmatrix bij de graaf uit figuur 3

              Directe-wegenmatrix
van
A B C D E
naar  A 0 2 0 0 0  = W
B 2 0 1 2 0
C 0 0 0 2 1
D 0 2 1 0 1
E 0 0 1 1 1

In de directe-wegenmatrix staat het aantal rechtstreekse wegen tussen elk tweetal punten van de graaf. Omdat er pijlen in de graaf voorkomen moet je goed op de plaats van de woorden 'van' en 'naar' letten. We zetten 'van' altijd boven de matrix.

Omhoog


Tweestapsmatrix
Beschouw onderstaande graaf met directe-wegenmatrix W.

              Directe-wegenmatrix
van
A B C D E
naar  A 0 2 0 0 0  = W
B 2 0 1 2 0
C 0 0 0 2 1
D 0 2 1 0 1
E 0 0 1 1 1

Ga je van A via B naar D, dan is er sprake van een tweestapsweg van A naar D. Het is gemakkelijk na te gaan dat de matrix W · W = W2informatie geeft over het aantal tweestapswegen tussen elk tweetal punten van de graaf. Zie eventueel de onderwerpen Machten van matrices en Het vermenigvuldigen van matrices. Bekijk onderstaand vermenigvuldigingsschema.

van
         
A
B
C
D
A B C D E
A B C D E
0 2 0 0 0
2 0 1 2 0
0 0 0 2 1
0 2 1 0 1
0 0 1 1 1
 

W  

naar 
A 0 2 0 0 0
B 2 0 1 2 0
C 0 0 0 2 1
D 0 2 1 0 1
E 0 0 1 1 1
4 0 2 4 0
0 8 2 2 3
0 4 3 1 3
4 0 3 7 2
0 2 2 3 1
= W · W = W2
       = W

Om bijvoorbeeld het aantal tweestapswegen van A naar D te bepalen moeten we onderstaande berekening maken.

Aantal éénstapswegen van A naar A     Aantal éénstapswegen van A naar D  =  0    0  =  0
Aantal éénstapswegen van A naar B     Aantal éénstapswegen van B naar D  =  2    2  =  4
Aantal éénstapswegen van A naar C     Aantal éénstapswegen van C naar D  =  0    1  =  0
Aantal éénstapswegen van A naar D     Aantal éénstapswegen van D naar D  =  0    0  =  0
Aantal éénstapswegen van A naar E     Aantal éénstapswegen van E naar D  =  0   1  =  0  +
 
Aantal tweestapswegen van A naar D  =  4

Dit is precies het product van de eerste kolom en de vierde rij van W. Matrix W2 geeft dus de aantallen 2-stapswegen tussen de punten van de graaf.

Omhoog


Meerstapsmatrices
Ga je in de graaf van figuur 3 van A via B en D naar C, dan is er sprake van een driestapsweg van A naar C.

              Directe-wegenmatrix
van
A B C D E
naar  A 0 2 0 0 0  = W
B 2 0 1 2 0
C 0 0 0 2 1
D 0 2 1 0 1
E 0 0 1 1 1

 Het aantal driestapswegen vind je in W · W · W = W3

Aantal driestapswegen
van
A B C D E
                    naar  A   0 16 4   4 6  = W · W · W = W3
B 16 4 13 23 7
C   8   2 8 17 7
D   0 22 9 8 12
E   4   6 8 11 8

In het algemeen geldt dat Wn het aantal n-stapswegen tussen de punten van een graaf bevat. Hierbij is n = 0, 1, 2, · · ·. We noemen Wn een meerstapsmatrix. Het aantal nulstapswegen vind je in W0.

Aantal nulstapswegen
van
A B C D E
naar  A 1 0 0 0 0  = W0
B 0 1 0 0 0
C 0 0 1 0 0
D 0 0 0 1 0
E 0 0 0 0 1

Omhoog


Het bepalen van de diameter met de sommatrix Sn
Onder de sommatrix Sn verstaan we:   Sn = W0+ W1+ W2· · · + Wn. Hierbij is Sn een matrix waarvan de matrixelementen die de som bevatten van de 0-, 1-, ...en n-stapswegen. Met het online computerprogramma kunnen we Sn voor elke waarde van n bepalen.We gaan nu bekijken hoe we met behulp van de reeks Sn de diameter van de graaf in figuur 3 kunnen bepalen.

              Directe-wegenmatrix
van
A B C D E
naar  A 0 2 0 0 0  = W
B 2 0 1 2 0
C 0 0 0 2 1
D 0 2 1 0 1
E 0 0 1 1 1

Voor de graaf in figuur 3 geldt:

0-stapswegen
van
A B C D E
naar  A 1 0 0 0 0  = S0               
B 0 1 0 0 0
C 0 0 1 0 0
D 0 0 0 1 0
E 0 0 0 0 1
    
0+1-stapswegen
van
A B C D E
naar  A 1 2 0 0 0  = S1S0 + W
B 2 1 1 2 0
C 0 0 1 2 1
D 0 2 1 1 1
E 0 0 1 1 2

In S1 staan nog matrixelementen die gelijk aan 0 zijn. Dat wil zeggen dat er punten zijn die niet door een 0-stapsweg of een 1-stapsweg met elkaar verbonden zijn. De diameter van de graaf is dus groter dan 1. Er geldt:

0+1+2-stapswegen
van
A B C D E
naar  A 5 2 2 4 0  = S2S1 + W2
B 2 9 3 4 3
C 0 4 4 3 4
D 4 2 4 8 3
E 0 2 3 4 5

In S2 staan nog matrixelementen die gelijk aan 0 zijn. Dat wil zeggen dat er punten zijn die niet door een 0-stapsweg, 1-stapsweg of een 2-stapsweg met elkaar verbonden zijn. De diameter van de graaf is dus groter dan 2. Er geldt:

0+1+2+3-stapswegen
van
A B C D E
naar  A   5 18 6   8 6  = S3S2 + W3
B 18 13 16 27 10
C 8 6 12 20 11
D 4 24 13 16 15
E 4 8 11 15 13

In S3 staan geen matrixelementen meer die gelijk aan 0 zijn. Dat wil zeggen dat alle punten door een 0-stapsweg, 1-stapsweg, 2-stapsweg of een 3-stapsweg met elkaar verbonden zijn.

De diameter van de graaf is dus 3.

Ga dit voorbeeld met het onderstaande online computerprogramma na. Hierbij ga je als volgt te werk:

  1. Kies in het Bestand-menu de optie Nieuw Project. Je krijgt dan het volgende dialoogkader:


     
    Kies in dit dialoogkader de optie C = Sn

  2. Maak het aantal kolommen (en automatisch het aantal rijen) gelijk aan 5 door op de Up/Down knop te klikken.
      
           
       

  3. Druk op de - knop.
     

  4. Vul matrix A in en verhoog de waarde van n -door op de Up/Down knop te klikken- net zolang tot de matrix C = Sn geen nullen meer bevat.

    De waarde van n is dan de diameter van de graaf.

 Omhoog


Het programma (programma-handleiding)



Disclaimer:
 Browsers sometimes crash when running computation-intensive ActiveX controls.
 Make sure your important work is saved before running this utility.

Omhoog


Opgave

Gegeven is de graaf in figuur 4.

  1. Stel bij deze graaf een directe-wegenmatrix W op.

  2. Bepaal met het online computerprogramma de diameter van deze graaf.


Omhoog

Wiskunde online ----- is speciaal ontworpen voor:
Microsoft  Internet Explorer 5.5 of hoger
Beeldschermresolutie minimaal 800×600
JavaScript-Interpretatie ingeschakeld!