Samenvatting voor grafentheorie hoofdstukken 1, 2, 3, 4 en 7. Tentamenstof voor tentamen grafentheorie op de Fontys lerarenopleiding wiskunde tweedegraads. De stof wordt overzichtelijk weergegeven. Begrippen, algoritmen, specifieke grafen etc. Alles wat je moet weten voor je tentamen.
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.
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper liekevandenoever. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €3,49. Je zit daarna nergens aan vast.
