GRAFENTHEORIE SAMENVATTING
HOOFDSTUK 1: BASIS
Een graaf is een wiskundige structuur die bestaat uit punten (vertices) en lijnen (edges).
Definitie
Een graaf G bestaat uit een eindige verzameling V, waarvan de elementen punten heten, en een
verzameling E, bestaande uit ongeordende paren van verschillende punten, welke lijnen genoemd
worden.
Een lijn heeft een begin-
en eindpunt, maar het
G wordt vaak aangeduid als (V, E)
kan ook andersom.
en soms als V(G) en E(G).
Volgens de definitie zijn er nu wat situaties te bedenken die hier net wel, of net niet, aan voldoen.
We bakenen de definitie dus af.
• Een verbinding van een punt met zichzelf?
Nee, want de verzameling E bestaat uit paren verschillende punten. Dit komt echter in de
opgaven af en toe wel voor.
• Twee verschillende verbindingen tussen twee punten?
Nee, want we hebben het over een verzameling paren en dus komt
één paar niet twee keer voor.
• Punten zonder verbindingen met anderen?
Ja, dat wordt niet uitgesloten. Dit noemen we dan een geïsoleerd punt.
Notaties
Punten hebben vaak een naam of een label, zoals 1, 2, 3 of a, b, c. Lijnen worden zo mogelijk
aangegeven door de labels van beide uiteinden achter elkaar te schrijven, zoals ab, 1a of 13, maar ba,
a1 of 31 zijn dan dezelfde lijnen.
Isomorfe grafen
Twee grafen G en H zijn isomorf als er een bijectie is tussen V(G) en V(H) en tussen E(G) en E(H). Dit
wil dus zeggen dat er bij één punt uit de ene graaf precies één punt uit de tweede graaf hoort en
omgekeerd. Zo hoort bij iedere lijn uit de eerste graaf ook precies één lijn uit de tweede graaf en
omgekeerd.
,• Deelgraaf: een deel van de punten en lijnen weggelaten.
• Opspannende deelgraaf: alleen een deel van de lijnen weggelaten.
• Geïndiceerde deelgraaf: elke lijn in de graaf die punten uit de deelgraaf verbindt, zit ook in de
deelgraaf. Dus als je een punt weglaat, laat je automatisch de lijn weg die eraan vastzit.
• Punten u en v die met elkaar verbonden zijn noemen we
buren.
• Punten u en v die met elkaar verbonden zijn heten de
uiteinden van de lijn uv.
• Twee lijnen met een gemeenschappelijk uiteinde heten
aangrenzend.
• Punt u en lijn uv heten incident met elkaar.
• De graad d(v) van een punt v van graaf G is het aantal lijnen van G dat incident is met v. De graad
van v zegt dus eigenlijk hoeveel verschillende lijnen er samenkomen in v.
• Een punt met graad 0 heet een geïsoleerd punt.
• Een punt met graad 1 heet een eindpunt.
Gradentheorie
De som van de graden van de punten van een graaf is altijd even.
Bewijs:
Elke lijn is incident met twee punten en telt dus bij twee punten mee in de graad. Dus ook geldt dat
het aantal punten van een oneven graad in een graaf even is.
Soorten grafen
Reguliere graaf
• Alle punten hebben dezelfde graad.
• k-regulier wil zeggen dat alle punten k als graad hebben.
• Volledige graaf: alle mogelijke lijnen tussen ieder tweetal punten komen voor.
Notatie: 𝐾𝑛
, Paden
• Notatie: 𝑃𝑛 .
• n geeft het aantal punten aan.
• 𝑃1 gebruiken we niet.
Cykels
• Notatie 𝐶𝑛 .
• n geeft het aantal punten aan.
• 𝐶1 en 𝐶2 bestaan we niet.
Wielen
• Notatie 𝑊𝑛.
• n geeft het aantal punten aan.
• Dit is pas zinvol vanaf n = 4.
Bipartiete graaf (tweedelingsgraaf)
• Punten vallen uiteen in twee verzamelingen
𝑉1 en 𝑉2 .
• Iedere lijn verbindt een punt uit 𝑉1 met een
punt uit 𝑉2 .
Volledige tweedelingsgraaf
• Ieder punt van 𝑉1 is verbonden met ieder punt van 𝑉2 .
• Als #𝑉1 = 𝑛 en #𝑉2 = 𝑚 dan is 𝐾𝑛,𝑚 de volledige
tweedelingsgraaf.
Bomen
• Een boom is een graaf zonder cykels.
• De eigenschappen van bomen volgt later.
HOOFDSTUK 1: BASIS
Een graaf is een wiskundige structuur die bestaat uit punten (vertices) en lijnen (edges).
Definitie
Een graaf G bestaat uit een eindige verzameling V, waarvan de elementen punten heten, en een
verzameling E, bestaande uit ongeordende paren van verschillende punten, welke lijnen genoemd
worden.
Een lijn heeft een begin-
en eindpunt, maar het
G wordt vaak aangeduid als (V, E)
kan ook andersom.
en soms als V(G) en E(G).
Volgens de definitie zijn er nu wat situaties te bedenken die hier net wel, of net niet, aan voldoen.
We bakenen de definitie dus af.
• Een verbinding van een punt met zichzelf?
Nee, want de verzameling E bestaat uit paren verschillende punten. Dit komt echter in de
opgaven af en toe wel voor.
• Twee verschillende verbindingen tussen twee punten?
Nee, want we hebben het over een verzameling paren en dus komt
één paar niet twee keer voor.
• Punten zonder verbindingen met anderen?
Ja, dat wordt niet uitgesloten. Dit noemen we dan een geïsoleerd punt.
Notaties
Punten hebben vaak een naam of een label, zoals 1, 2, 3 of a, b, c. Lijnen worden zo mogelijk
aangegeven door de labels van beide uiteinden achter elkaar te schrijven, zoals ab, 1a of 13, maar ba,
a1 of 31 zijn dan dezelfde lijnen.
Isomorfe grafen
Twee grafen G en H zijn isomorf als er een bijectie is tussen V(G) en V(H) en tussen E(G) en E(H). Dit
wil dus zeggen dat er bij één punt uit de ene graaf precies één punt uit de tweede graaf hoort en
omgekeerd. Zo hoort bij iedere lijn uit de eerste graaf ook precies één lijn uit de tweede graaf en
omgekeerd.
,• Deelgraaf: een deel van de punten en lijnen weggelaten.
• Opspannende deelgraaf: alleen een deel van de lijnen weggelaten.
• Geïndiceerde deelgraaf: elke lijn in de graaf die punten uit de deelgraaf verbindt, zit ook in de
deelgraaf. Dus als je een punt weglaat, laat je automatisch de lijn weg die eraan vastzit.
• Punten u en v die met elkaar verbonden zijn noemen we
buren.
• Punten u en v die met elkaar verbonden zijn heten de
uiteinden van de lijn uv.
• Twee lijnen met een gemeenschappelijk uiteinde heten
aangrenzend.
• Punt u en lijn uv heten incident met elkaar.
• De graad d(v) van een punt v van graaf G is het aantal lijnen van G dat incident is met v. De graad
van v zegt dus eigenlijk hoeveel verschillende lijnen er samenkomen in v.
• Een punt met graad 0 heet een geïsoleerd punt.
• Een punt met graad 1 heet een eindpunt.
Gradentheorie
De som van de graden van de punten van een graaf is altijd even.
Bewijs:
Elke lijn is incident met twee punten en telt dus bij twee punten mee in de graad. Dus ook geldt dat
het aantal punten van een oneven graad in een graaf even is.
Soorten grafen
Reguliere graaf
• Alle punten hebben dezelfde graad.
• k-regulier wil zeggen dat alle punten k als graad hebben.
• Volledige graaf: alle mogelijke lijnen tussen ieder tweetal punten komen voor.
Notatie: 𝐾𝑛
, Paden
• Notatie: 𝑃𝑛 .
• n geeft het aantal punten aan.
• 𝑃1 gebruiken we niet.
Cykels
• Notatie 𝐶𝑛 .
• n geeft het aantal punten aan.
• 𝐶1 en 𝐶2 bestaan we niet.
Wielen
• Notatie 𝑊𝑛.
• n geeft het aantal punten aan.
• Dit is pas zinvol vanaf n = 4.
Bipartiete graaf (tweedelingsgraaf)
• Punten vallen uiteen in twee verzamelingen
𝑉1 en 𝑉2 .
• Iedere lijn verbindt een punt uit 𝑉1 met een
punt uit 𝑉2 .
Volledige tweedelingsgraaf
• Ieder punt van 𝑉1 is verbonden met ieder punt van 𝑉2 .
• Als #𝑉1 = 𝑛 en #𝑉2 = 𝑚 dan is 𝐾𝑛,𝑚 de volledige
tweedelingsgraaf.
Bomen
• Een boom is een graaf zonder cykels.
• De eigenschappen van bomen volgt later.
