Summary
Samenvatting Grafentheorie
- Course
- Institution
Een samenvatting van het vak Grafentheorie (volledige reader samengevat).
[Show more]
Seller
Follow
cdenhollander
Reviews received
Content preview
GRAFENTHEORIE SAMENVATTINGHOOFDSTUK 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.
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 cdenhollander. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.44. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
76449 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now