grafen


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

Een graaf zou je het best kunnen omschrijven als een "schematische tekening". Een tekening waar je handig, in één oogopslag allerlei zaken uit af kan lezen.

Een graaf bestaat uit 2 dingen:

Knooppunten. Dat zijn de "elementen" waartussen we relaties willen aangeven. We geven die meestal aan met dikke stippen.

Verbindingslijnen. Tussen een aantal knooppunten zijn lijnen getrokken. Zo'n lijn staat voor een bepaalde relatie tussen die twee knooppunten. De lengte of de vorm van zo'n lijn doen er niet toe, het gaat er alleen maar om óf er een lijn is of niet.

Hiernaast zie je een voorbeeld van een graaf met de knooppunten A, B, C, D, E.
Nou zijn de termen "elementen" en "relaties" nogal vaag. Daarom eerst een paar mogelijke voorbeelden bij de graaf hiernaast.

•

De knooppunten zouden voor vijf voetbalploegen kunnen staan en de verbindingslijnen voor de relatie "...heeft gespeeld tegen...". Dan zie je in de graaf direct dat B al tegen A en tegen C gespeeld heeft. Ook dat E nog maar één wedstrijd heeft gespeeld, en A al drie.

•

De knooppunten zouden voor vijf plaatsen kunnen staan en de verbindingslijnen voor de relatie "...heeft een treinverbinding met...". Dan zie je in de graaf direct dat je, als je met de trein van E naar A wilt, je via station D zult moeten reizen.

•

De knooppunten zouden voor vijf landen kunnen staan, en de verbindingslijnen voor de relatie "heeft een stuk grens met". Dan zie je aan de graaf direct dat de landen B, C en D elk twee buurlanden hebben.

•

De knooppunten zouden vijf kinderen kunnen zijn, en de verbindingslijnen de relatie "...is bevriend met..." of "...doet aan dezelfde sport als..." of "...zit in de klas bij..." of "...woont niet in dezelfde straat als..."
of ......

En ga zo maar door....
Overal als het gaat om dingen waar relaties tussen gelden, kun je een graaf tekenen.

Speciale verbindingslijnen.

Tot nu toe waren die verbindingslijnen gewoon lijntje van het ene naar het andere knooppunt. Af en toe kan er iets speciaals mee aan de hand zijn. Dat is bijvoorbeeld zo in de volgende drie gevallen.

1. Gerichte verbindingen.

Het kan zijn dat een relatie maar één kant op gaat. Zoals in de liefde bijvoorbeeld. Als je de relatie "...is verliefd op..." bekijkt, dan kan het heel goed dat A verliefd is op B, maar B niet op A.

In een graaf geven we dat aan met een pijltje in de verbindingslijn. Dat betekent dus dat die verbindingslijn een "éénrichtingsweg" is; je mag hem alleen in de richting van het pijltje volgen.

Hiernaast zie je dat iedereen verliefd is op D. En ook dat er maar één beantwoorde liefde is: die tussen A en C. Verder zal B wel jaloers op A zijn, want B is verliefd op C, maar C op A.

Merk verder nog op dat de verbindingslijnen BD en AC elkaar snijden, maar dat dat niet een echt snijpunt is; dan moet er een stip in staan met een letter erbij.

Een graaf waarin verbindingslijnen met een pijl erin voorkomen heet een gerichte graaf.

2. Lussen.

Een lus is een verbinding van een knooppunt met zichzelf. Zet ook in een lus altijd een pijl (maak het dus een gerichte verbinding). Het kan natuurlijk heel goed dat een knooppunt ook de relatie van de graaf met zichzelf heeft.
Neem bijvoorbeeld als knooppunten vier Nederlandse woorden A, B, C, D en als relatie "...heeft minstens één letter gemeenschappelijk met...". Omdat elk woord zeker letters met zichzelf gemeenschappelijk heeft, moet er bij elk knooppunt een lus naar zichzelf gaan.
A, B, C, D zouden hier bijvoorbeeld "klas", "boek", "long" en "gras" kunnen zijn.

3. Gewogen verbindingen.

Meestal gaat het in een graaf er alleen om óf er verbinding is tussen twee knooppunten. Maar af en toe wordt er aan zo'n verbinding ook nog een getal gekoppeld. Het simpelste voorbeeld is natuurlijk de verbindingen tussen een aantal steden. Je kunt aangeven óf er een directe verbinding is tussen twee steden, maar als dat zo is kun je nog meer informatie geven door te zeggen hoe lang die verbinding is.
Als je dat wilt, dan zet je dat getal in de graaf bij de verbindingslijn.

Zo zie je in de graaf hiernaast dat je, als je van C naar B wilt reizen, dat het kortst kunt doen via de route CDAB. Zonder die getallen was dat niet duidelijk geweest (denk erom dat de lengte van de getekende verbindingslijnen in een graaf willekeurig is; dat hoeft niet te kloppen met de werkelijke lengte)

Gewogen verbindingen hoeven niet altijd afstanden aan te geven. Er kan eigenlijk elk "aantal" dat tussen de knooppunten geldt staan. Hiernaast zie je bijvoorbeeld een graaf met van vier personen het aantal gemeenschappelijke facebook-vrienden dat ze hebben.

OPGAVEN

1.	Vier plaatsen (A, B, C) binnen één gemeente gaan in de zomer een festival organiseren. De locatie daarvan kan zijn in één van de plaatsen zelf of op een groot terrein (T)dat ook in de gemeente ligt. Hiernaast zie je een graaf met de afstanden tussen de vijf locaties.

	Men gaat ervan uit dat van elke plaats 10% van de inwoners het festival zal bijwonen. Plaats A heeft 8500 inwoners, plaats B heeft 6100 inwoners en plaats C heeft 4430 inwoners

	a.	Vul de afstandenmatrix A hiernaast in. Neem steeds de kortste route, en denk erom dat het gaat om de kortste route heen én weer terug.

	b.	Waar kan het festival het best plaatsvinden als er zo weinig mogelijk kilometers door alle festivalgangers samen moet worden afgelegd? Geef een berekening met een matrixvermenigvuldiging.

2.	8 schakers spelen op een groot schaaktoernooi een halve competitie. De graaf hiernaast geeft na een aantal speelrondes de gewonnen/verloren wedstrijden van deze schakers. Een gerichte verbindingslijn betekent "heeft gewonnen van" een ongerichte verbinding betekent "remise" en de getallen geven aan hoeveel minuten de hele wedstrijd duurde.

	a.	Eén wedstrijd tussen deze spelers is afgebroken moet nog uitgespeeld worden. Welke was dat?

	Een gewonnen wedstrijd levert 1 punten op voor de winnaar, remise voor beide spelers 0,5 punt. Men heeft afgesproken dat bij gelijke stand de speler die de minste tijd heeft gespeeld hoger staat dan de speler die er langer over heeft gedaan.

	b.	Neem aan dat de afgebroken wedstrijd na in totaal 115 minuten speeltijd eindigt in remise. Maak dan een stand op tot dit moment.

3.	Acht darters spelen een toernooi tegen elkaar. Het toernooi is een "Knock-Out toernooi; dat betekent dat een speler die verliest er direct uitlegt. De winnaars gaan steeds door naar een volgende ronde. Er worden dus 4 kwartfinales gespeeld en 2 halve finales en uiteindelijk één finale. De graaf hiernaast geeft de resultaten. Een verbindingslijn staat voor de relatie "heeft gewonnen van" Leg uit wie er van wie heeft gewonnen in de halve finales.

4.	De volgende matrix geeft van een graaf van 5 knooppunten aan welke knooppunten via twee stappen met elkaar verbonden zijn. De getallen geven aan via hoeveel verschillende routes dat kan.



	Maak hiervan een graaf die aangeeft welke knooppunten via *drie stappen* met elkaar verbonden zijn.

De Vriendenstelling (een toepassing).

De "vriendenstelling" heet ook wel de stelling van Ramsey (dat was degene die er het eerst mee kwam) en luidt als volgt:

"In elke groep van zes mensen zijn er minstens drie gemeenschappelijke vrienden,
óf drie mensen die alle drie geen vrienden van elkaar zijn".

Het bewijs met een graaf.
Teken een graaf met zes knooppunten A tm F (de mensen), en met als verbindingslijn de relatie "..is bevriend met...".
Kies een willekeurig punt A van de graaf. Dan kunnen er vanuit A 0, 1, 2, 3, 4 of 5 verbindingslijnen lopen.

geval 1. Er lopen minstens drie verbindingslijnen vanuit A.
Noem drie punten waar verbindingslijnen vanaf A heen lopen B, C, D.
Zodra er tussen B, C en D ergens één verbindingslijn loopt (bijv. BD), hebben we een driehoek (ABD) dus een groep van drie vrienden.
Maar als er tussen B, C en D geen enkele verbindingslijn loopt, dan hebben we drie mensen die alle drie geen vriend van elkaar zijn. In beide gevallen is de stelling waar.

geval 2. Er lopen vanaf A minder dan 3 verbindingslijnen.
Dan zijn er minstens 3 punten te vinden waar géén lijn vanaf A naar toe loopt. Noem die punten B, C en D.
Zodra er tussen B, C en D ergens ook géén verbindingslijn loopt (bijv. BD), hebben we een drie mensen (ABD) die alle drie geen vriend van elkaar zijn..
Maar als er tussen B, C en D drie verbindingslijnen lopen, dan hebben we een groep van drie vrienden. In beide gevallen is de stelling waar.