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.

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.

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.

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 = W²informatie 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 W² geeft dus de aantallen 2-stapswegen tussen de punten van de graaf.

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 = W³

		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 Wⁿ het aantal n-stapswegen tussen de punten van een graaf bevat. Hierbij is n = 0, 1, 2, · · ·. We noemen Wⁿ een meerstapsmatrix. Het aantal nulstapswegen vind je in W⁰.

		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

Het bepalen van de diameter met de sommatrix S_n
Onder de sommatrix S_n verstaan we:   S_n = W⁰+ W¹+ W²· · · + Wⁿ. Hierbij is S_n een matrix waarvan de matrixelementen die de som bevatten van de 0-, 1-, ...en n-stapswegen. Met het online computerprogramma kunnen we S_n voor elke waarde van n bepalen.We gaan nu bekijken hoe we met behulp van de reeks S_n 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		= S1 = S0 + 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 S₁ 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		= S2 = S1 + 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 S₂ 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		= S3 = S2 + 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 S₃ 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 = S_n

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 = S_n geen nullen meer bevat.

   

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

Het programma (programma-handleiding)

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.