Samenvatting
Samenvatting Grafentheorie (OAWI-H1GRAAF-12)
- Vak
- Instelling
Samenvatting voor grafentheorie (behaald cijfer: 8,1)
[Meer zien]Voorbeeld 1 van de 9 pagina's
Voorbeeld 1 van de 9 pagina's
In winkelwagen
In winkelwagen
Verkoper
Volgen
joshtukker
Ontvangen beoordelingen
Voorbeeld van de inhoud
1755945 Josh TukkerGrafentheorie
Hoofdstuk 1 – Inleiding en basisbegrippen
1.2 Basisbegrippen
• 𝑛 is het aantal punten, 𝑚 is het aantal lijnen.
• Een graaf is een diagram die bestaat uit punten die wel of niet verbonden worden door één of
meer lijnen.
§ Is de lijn voorzien van een richting? Dit is een gerichte graaf.
§ Is de lijn voorzien van een gewicht? Dit is een gewogen graaf.
• Twee verbonden punten zijn buren, twee verbonden lijnen heten buurlijnen.
§ Er is sprake van meervoudige lijnen als tussen twee punten meer dan één lijn loopt.
§ Een lus is een lijn van een punt naar zichzelf.
§ Een graaf zonder meervoudige lijnen en lussen is een enkelvoudige graaf.
§ Als van graaf 𝐺 enkele lijnen en/of punten worden weggelaten, dan ontstaat de deelgraaf
van 𝐺.
• De valentie van een punt geeft aan hoeveel lijnen er aan een punt vastzitten, waarbij een lus voor
twee telt.
§ Bij enkelvoudige grafen wordt ook het begrip lijnvalentie gebruikt. Dit geeft het aantal andere
lijnen aan die vastzitten aan die lijn.
§ Een geïsoleerd punt is een punt met valentie 0.
§ De valentie-rij is de niet-dalende rij van valenties van de punten van de graaf.
§ Een graaf 𝐺 is regelmatig van de orde 𝒌 als ieder punt van 𝐺 valentie 𝑘 heeft.
• Handenschud-lemma:
§ In elke graaf is de valentiesom gelijk aan 2𝑚.
• Een ongelabelde graaf is een graaf waarbij de punten geen naam hebben.
§ Als er voor de tekening van twee ongelabelde grafen een naamgeving te verzinnen is zo dat ze
dezelfde (gelabelde) graaf voorstellen, dan zijn beide ongelabelde grafen isomorf.
- Twee ongelabelde grafen 𝐺 en 𝐻 zijn isomorf als het mogelijk is de punten van 𝐺 en 𝐻 zo te
labelen dat gelijk gelabelde punten van 𝐺 en 𝐻 gelijke buren hebben.
• Een pad in een graaf is een rij opeenvolgende verschillende lijnen.
§ Een pad wordt genoteerd als een rij opeenvolgende lijnen.
§ Paden worden aangegeven met Griekse letters (α, β, γ, etc.).
§ Het eerste punt heet het beginpunt en het laatste punt heet het eindpunt.
- Als het beginpunt en eindpunt van een pad α samenvallen, heet het pad α een circuit.
o Een circuit van drie lijnen noem je een driehoek, een circuit van vier lijnen noem je een
vierhoek, etc.
• Een graaf heet een samenhangende graaf als er tussen elk tweetal verschillende punten van de
graaf een pad bestaat.
§ Een niet-samenhangende graaf bestaat uit een aantal componenten, die ieder afzonderlijk wel
samenhangend zijn, maar onderling niet verbonden zijn.
1.3 Verbindingsmatrices
• Een graaf kan numeriek worden weergegeven door middel van een verbindingsmatrix.
§ In een verbindingsmatrix geeft het getal 1 aan dat punten buren zijn.
§ Het aantal tweestap-, driestap-, vierstap-, etc-routes zijn te berekenen met behulp van de
matrixvermenigvuldiging.
1/9
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 joshtukker. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €4,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 67163 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen