Grafentheorie
Hst 1. Basisbegrippen
Begrip Betekenis
n Punten
m Lijnen
Pad Een rij opeenvolgende verschillende lijnen, dus een pad van A naar D. Punten
mogen vaker voorkomen, maar lijnen niet. Het eerste punt heet het beginpunt
en het laatste punt het eindpunt.
Circuit Als het begin- en eindpunt van een pad samenvallen.
Enkelvoudige graaf Een graaf zonder meervoudige lijnen en lussen heeft een enkelvoudige graaf
(dus tussen elk tweetal punten maximaal 1 lijn).
Samenhangende Als er tussen elk tweetal punten een pad bestaat, dus de graaf bestaat uit 1
graaf component.
Componenten Een niet-samenhangende graaf bestaat uit een aantal componenten, die
afzonderlijk samenhangend zijn, maar onderling niet verbonden zijn.
Gerichte graaf Een graaf waarbij de lijnen zijn voorzien van een richting.
Gewogen graaf Een graaf waarbij de lijnen zijn voorzien van een gewicht (getal).
Valentie Aantal lijnen dat aan een punt vastzitten, dus punt P heeft valentie 3.
o Valentie-rij o Een niet-dalende rij van valenties van de punten van de graaf, dus bv.
0,1,2,2,3
Regelmatige graaf Een graaf waarbij elk punt valentie k heeft.
van orde k Regelmatige graaf van orde 3 met 5 punten kan niet, want 5x3=15 en dit is een
oneven valentie som.
Volledige graaf Een graaf waarbij tussen elk tweetal punten één lijn loopt. We noteren een
volledige graaf met n punten als k n. Een volledige graaf is altijd regelmatig van
orde n-1.
Tweedelige graaf Als alle punten van de graaf in twee groepen (Wit en Zwart) kunnen worden
verdeeld, zodat elke lijn van de graaf een W-punt verbindt met een Z-punt (dus
buren mogen niet in dezelfde groep zitten).
o Volledige o Een graaf waarbij élk W-punt met élk Z-punt
tweedelige verbonden is. Notatie: K p , q.
graaf Bv. K 3,3 zie hiernaast.
Platonische graaf Er zijn 5 platonische lichamen, afgeleid van de platonische lichamen.
Handenschud- In elke graaf is de valentiesom gelijk aan 2m, omdat een lijn 2 uiteinden heeft.
lemma valentiesom
Dus m is gelijk aan .
2
Isomorfe graaf Wanneer graven ‘hetzelfde zijn’. Analyse isomorf aantonen:
o Dezelfde aantal punten en lijnen?
o Dezelfde valentie (valentie-rij)?
o Hebben ze dezelfde buren?
o Zo ja, koppelschema maken met oog op buren en aantal valentie.
Isomorfe graven maar 1 keer tekenen, omdat ze ‘hetzelfde’ zijn.
Hst 1. Basisbegrippen
Begrip Betekenis
n Punten
m Lijnen
Pad Een rij opeenvolgende verschillende lijnen, dus een pad van A naar D. Punten
mogen vaker voorkomen, maar lijnen niet. Het eerste punt heet het beginpunt
en het laatste punt het eindpunt.
Circuit Als het begin- en eindpunt van een pad samenvallen.
Enkelvoudige graaf Een graaf zonder meervoudige lijnen en lussen heeft een enkelvoudige graaf
(dus tussen elk tweetal punten maximaal 1 lijn).
Samenhangende Als er tussen elk tweetal punten een pad bestaat, dus de graaf bestaat uit 1
graaf component.
Componenten Een niet-samenhangende graaf bestaat uit een aantal componenten, die
afzonderlijk samenhangend zijn, maar onderling niet verbonden zijn.
Gerichte graaf Een graaf waarbij de lijnen zijn voorzien van een richting.
Gewogen graaf Een graaf waarbij de lijnen zijn voorzien van een gewicht (getal).
Valentie Aantal lijnen dat aan een punt vastzitten, dus punt P heeft valentie 3.
o Valentie-rij o Een niet-dalende rij van valenties van de punten van de graaf, dus bv.
0,1,2,2,3
Regelmatige graaf Een graaf waarbij elk punt valentie k heeft.
van orde k Regelmatige graaf van orde 3 met 5 punten kan niet, want 5x3=15 en dit is een
oneven valentie som.
Volledige graaf Een graaf waarbij tussen elk tweetal punten één lijn loopt. We noteren een
volledige graaf met n punten als k n. Een volledige graaf is altijd regelmatig van
orde n-1.
Tweedelige graaf Als alle punten van de graaf in twee groepen (Wit en Zwart) kunnen worden
verdeeld, zodat elke lijn van de graaf een W-punt verbindt met een Z-punt (dus
buren mogen niet in dezelfde groep zitten).
o Volledige o Een graaf waarbij élk W-punt met élk Z-punt
tweedelige verbonden is. Notatie: K p , q.
graaf Bv. K 3,3 zie hiernaast.
Platonische graaf Er zijn 5 platonische lichamen, afgeleid van de platonische lichamen.
Handenschud- In elke graaf is de valentiesom gelijk aan 2m, omdat een lijn 2 uiteinden heeft.
lemma valentiesom
Dus m is gelijk aan .
2
Isomorfe graaf Wanneer graven ‘hetzelfde zijn’. Analyse isomorf aantonen:
o Dezelfde aantal punten en lijnen?
o Dezelfde valentie (valentie-rij)?
o Hebben ze dezelfde buren?
o Zo ja, koppelschema maken met oog op buren en aantal valentie.
Isomorfe graven maar 1 keer tekenen, omdat ze ‘hetzelfde’ zijn.
