Samenvatting
Samenvatting Grafentheorie
- Vak
- Instelling
Een samenvatting van het vak Grafentheorie (volledige reader samengevat).
[Meer zien]Voorbeeld 3 van de 24 pagina's
Voorbeeld 3 van de 24 pagina's
In winkelwagen
In winkelwagen
Verkoper
Volgen
cdenhollander
Ontvangen beoordelingen
Voorbeeld van de inhoud
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.
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, Bancontact of creditcard 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 cdenhollander. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €2,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 76449 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen