verbindingsmatrix


De verbindingsmatrix.	© h.hofstede (h.hofstede@hogeland.nl)

De verbindingsmatrix (V) van een graaf is een matrix met daarin enen en nullen die aangeven welke punten van de graaf met elkaar verbonden zijn (1 = verbonden, 0 = niet-verbonden).
Als een graaf k knooppunten heeft, dan is de verbindingsmatrix dus altijd een k × k matrix (VAN elk knooppunt NAAR elk knooppunt). Zo'n matrix noemen we een vierkante matrix, maar dat had je zelf waarschijnlijk ook nog wel verzonnen.
Hieronder zie je een graaf met rechts de bijbehorende verbindingsmatrix.

Misschien zijn een paar dingen je al opgevallen:

•

Er staat voor de matrix : "naar" en boven de matrix "van", maar dat maakt natuurlijk niet uit; als er een verbinding van A naar B is, is er ook eentje van B naar A. Deze matrix V is symmetrisch in de diagonaal. Omdat we zo meteen ook grafen met éénrichtingsverbindingen gaan bekijken (waar "VAN" en "NAAR" wél van belang zijn), staan ze er nu ook alvast.

•

De verbindingsmatrix V geeft alleen maar aan óf de knooppunten verbonden zijn. Bij gewogen verbindingslijnen zijn de wegingen niet terug te vinden in V. Als je dat wél wilt kun je in plaats van een 1 natuurlijk het gewichtsgetal in de matrix zetten. In dat geval noemen we het niet meer de verbindingsmatrix (V), maar de wegenmatrix (W). In zo'n wegenmatrix kunnen ook éénrichtingsverbindingen zijn weergegeven. De matrix is dan niet meer symmetrisch. Zet in dat geval altijd "van" voor de matrix en "naar" er boven. Als de gewichten echte afstanden zijn dan wordt zo'n wegenmatrix W ook wel een afstandenmatrix (A) genoemd.

Meerstapsverbindingen.

Omdat zo'n verbindingsmatrix vierkant is, kun je hem altijd met zichzelf vermenigvuldigen.
Net als bij getallen noteren we V • V als V². In bovenstaand voorbeeld geeft dat:

De vraag is natuurlijk: "Wat stelt deze V² nou vóór?" "Wat moeten we ermee?" "Waarom is dit interessant?"
Laten we daarom proberen te achterhalen waar een getal van V² vandaan komt. Neem als voorbeeld die 2 in de derde rij en de tweede kolom:

Die 2 ontstond door de derde rij van V te vermenigvuldigen met de tweede kolom (groen met paars). Zoals je ziet is dat 1 • 1 + 0 • 0 + 0 • 0 + 0 • 0 + 1 • 1. En dat wordt 2 omdat er twee keer 1 • 1 in voorkomt.
Die eerste 1 • 1 komt van: (verbinding van C naar A) • (verbinding van A naar B)
Die tweede 1 • 1 komt van: (verbinding van C naar E) • (verbinding van E naar B)
Daar staan dus precies de twee routes C → A → B en C → E → B aangegeven: dat zijn alle routes om in twee stappen van C naar B te komen! We noemen dat het aantal tweestapsverbindingen van C naar B.
Zo zie je in V² ook bijvoorbeeld dat er 3 manieren zijn om van A in A te komen. In de graaf zie je ook direct dat het gaat om de routes A → B → A en A → C → A en A → E → A.

V² geeft het aantal tweestapsverbindingen

En ook als je een wegenmatrix W met gewogen verbindingen gebruikt geldt nog steeds dat W² het aantal tweestapsverbindingen geeft, tenminste als in W het aantal routes staat aangegeven (niet als er iets anders als "kilometers" of zo staat).

Op dezelfde manier (als je het niet gelooft, dan ga je het zelf maar na) stelt V³het aantal driestapsverbindingen voor, en V⁴ het aantal vierstapsverbindigen, enz.
In het algemeen:

Als matrix M het aantal verbindingen tussen de knooppunten van een graaf geeft,
Dan geeft Mⁿ het aantal n-stapsverbindingen.

Dus wil je bijvoorbeeld weten op hoeveel manieren je in bovenstaande graaf in 5 stappen van B in E kunt komen, dan bereken je gewoon eventjes V⁵ .
Nou ja....eventjes......
Dat is nogal een werk. Daarom wordt het nu hoog tijd onze GR in te schakelen voor dit "vieze werk".

Matrices in de GR

Je kunt matrixberekeningen met je TI uitvoeren. Als voorbeeld zal ik V⁵ van bovenstaand voorbeeld gaan berekenen. Dat gaat op de volgende manier.

Druk eerst op 2nd MATRIX en kies 1: [A] en EDIT en dan ENTER

Dan kun je boven in het scherm de afmetingen (rij × kolom) van de matrix invoeren.
In dit geval 5 × 5.
Vervolgens kun je de hele matrix invoeren. Door steeds een element in te voeren en dan op ENTER te drukken loopt je rekenmachine de matrix rij voor rij langs.

Al je klaar bent druk je op 2nd QUIT
V is nu ingevoerd als matrix A in je rekenmachine.
V⁵ bereken je nu als volgt:
2nd MATRIX 1:[A] 5 × 5 ENTER
[A]^5

Door naar rechts te scrollen krijg je alle elementen van V⁵ in beeld.
De conclusie is:

Daarin zie je dat er 38 manieren zijn om in vijf stappen van B naar E te gaan (tweede kolom, vijfde rij).

OPGAVEN

1.	Van een graaf is het kwadraat V² van de verbindingsmatrix gegeven door:

	Teken een mogelijke graaf die hieraan voldoet.

2.	Hiernaast zie je een speelbord met 7 speelvelden. Je kunt in een zet een pion steeds van een speelveld naar een aangrenzend speelveld verplaatsen, maar je mag de rode grenslijnen niet passeren. Bereken met matrixvermenigvuldiging hoeveel mogelijke manieren er zijn om met een pion in zes zetten van veld 4 weer naar veld 4 te gaan.

3	Hieronder zie je een landkaart met de zeven landen die meestal tot Midden-Europa worden gerekend.



	a.	Welk van de onderstaande grafen zou deze kaart kunnen weergeven, als een knooppunt een land voorstelt en een verbindingslijn de relatie "heeft een stuk grens samen met" ?




	b.	Stel van jouw graaf een verbindingsmatrix M op en bereken M² . Leg duidelijk uit wat de getallen op de hoofddiagonaal van M² voorstellen. Leg nog duidelijker uit wat de andere getallen van M² voorstellen.

	c.	Iemand gaat vanuit Duitsland een reis maken. Hij kiest steeds als hij in een land is willekeurig een buurland om naar toe te gaan (teruggaan kan dus ook!) Bereken hoeveel verschillende routes er op die manier gemaakt kunnen worden om na 4 grenzen te zijn overgetrokken in Tsjechië te zijn. Bereken deze kans met een matrixvermenigvuldiging.

4	Zes teams hebben een halve competitie van een volleybaltoernooi gespeeld, en de resultaten daarvan staan in de matrix hiernaast.

	a.	Leg uit hoe je kunt zien dat alle wedstrijden gespeeld zijn.

	b.	Leg uit waarom er niet direct een winnaar kan worden aangewezen.

	c.	Men besluit daarom tweestaps-overwinningen ook een half punt te geven. Bereken met behulp van de tweestapsverbindingen wie de winnaar van dit toernooit wordt.



© h.hofstede (h.hofstede@hogeland.nl)