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

De directeur, de verkoopleider en het hoofd van de werkplaats van een bedrijf hebben regelmatig overleg. De directeur verblijft in het hoofdkantoor (H), de verkoopleider heeft elders zijn eigen kantoor (K) en het hoofd van de werkplaats is normaal in de werkplaats (W). Het overleg tussen de drie kan plaatsvinden in H, K of W of ook in een externe vergaderruimte (V). De afstanden tussen deze locaties staan in de graaf hiernaast.

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.

Waar kan het overleg het best plaatsvinden als er zo weinig mogelijk gereden moet worden?

De directeur ontvangt een reisvergoeding van €0,60 per km. De verkoopleider krijgt €0,40 per km en het hoofd van de werkplaats krijgt €0,30 per km.

Maak een 3 × 1 kosten matrix K en bepaal vervolgens met matrixvermenigvuldiging de vergaderplaats die de minste reiskosten met zich meebrengt.

De graaf hiernaast geeft de gespeelde wedstrijden vlak na het begin van de Nederlandse voetbalcompetitie weer. Een gerichte verbindingslijn betekent "heeft gewonnen van", en de getallen geven aan met hoeveel doelpunten verschil die winst was.

Eén wedstrijd tussen deze teams onderling is afgelast. Welke was dat?

Twente-PSV

Neem aan dat de afgelaste wedstrijd wordt ingehaald en in gelijkspel eindigt. Maak dan een stand op tot dit moment. Houd daarbij ook rekening met het doelsaldo. Bedenk dat een gewonnen wedstrijd 3 punten oplevert voor de winnaar en 0 voor de verliezer. Een gelijkspel geeft beide teams 1 punt.

Acht teams doen mee aan een klein jeugdvoetbaltoernooi.
Eerst spelen de teams volgens loting vier wedstrijden. De winaars gaan door naar de twee halve finales (bij gelijkspel worden strafschoppen genomen totdat er een winnaar is). De winnaars van die twee halve finales spelen tenslotte de finale tegen elkaar.
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.

E van F, D van C

Maak een graaf met als knooppunten de provincies van Nederland en als verbindingslijnen de relatie: "...heeft een grens gemeenschappelijk met..." (tel de afsluitdijk ook als "aangrenzend")

examenvraagstuk HAVO Wiskunde A, 1997

Een liter benzine kost niet in ieder land evenveel. In een voorlichtingsfolder van de ANWB werden prijsverschillen van juni 1995 in een tabel vermeld. Zie de volgende tabel. Alle bedragen zijn omgerekend in guldens.

Waar is benzine goedkoper?
Grensovergang	goedkoper in	gld/liter voordeel
Nederland/België Belgie/Luxemburg Luxemburg/Frankrijk België/Frankrijk Frankrijk/Spanje Nederland/Duitsland Duitsland/Oostenrijk Duitsland/Zwitserland Oostenrijk/Italië Zwitserland/Italië	België Luxemburg Luxemburg België Spanje Duitsland Oostenrijk Zwitserland Oostenrijk Zwitserland	0,17 0,33 0,48 0,15 0,44 0,05 0,19 0,25 0,09 0,15

Het prijsvoordeel in deze tabel is gebaseerd op Eurosuper (loodvrij 95)

In onderstaande graaf zijn de grensovergangen van de negen genoemde landen aangegeven.

Bij de overgang NL/België is de benzine in België f 0,17 per liter goedkoper. In de graaf geef je dat aan met een pijl en een bedrag:

Geef in de graaf de gegevens van de grensovergangen die in de tabel zijn genoemd aan.

Zet in de graaf de juiste pijlen en bedragen bij de resterende grensovergangen.

In juni 1995 kostte een liter benzine in Nederland f 1,90.

Noem de drie landen met de laagste benzineprijzen en vermeld bij elk van deze landen de prijs per liter.

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.

We zullen later nog meer van Ramsey horen...