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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller liekevandenoever. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.75. You're not tied to anything after your purchase.
