In dit document worden de basisonderwerpen in de grafentheorie behandeld. Definities worden uitgelegd met af en toe wat voorbeelden. Algoritmen, heuristieken en stellingen zijn met plaatjes helder weergegeven.
A. Inleiding (p1-p7)
compatibel veroorzaken geen conflcten met elkaar (ln dlt geval verkeersstromen).
compatiblllteltsgraa Graaf waarln punten met lljnen zljn veribonden aan andere punten dle
f compatibel zljn (elkaar nlet conflcteren).
deelgraaf Onderdeel van een graaf.
volledlge graaf Deelgraven dle zo zljn opgeibouwd waariblj elk tweetal punten veribonden
ls. Hlervoor zljn mlnlmaal 3 punten nodlg.
In de compatiblllteltgraaf ls het ‘drlehoekjef ABC een volledlge deelgraaf.
Ze ibestaat ult louter wederzljds compatibele stromen want A, B en C
kunnen alle tegelljkertjd stromen!
Bepaal de Teken de compatiblllteltgraaf.
compatibllltelt en Bepaal voor élk punt de grootste volledlge deelgraaf en streep
cyclustjd m.ib.v. een duibibele door.
compatiblllteltgraaf. Selecteer een aantal van deze deelgrafen zó dat elk punt van de
compatiblllteltgraaf ln deze selecte van deelgrafen voorkomt.
Deel de cyclustjd door het aantal volledlge deelgrafen ult de
selecte ken aan ledere perlode zonn volledlge deelgraaf toe.
gerichte graaf = Graaf dle wordt toegepast iblj projecten met dlverse taken (actvltelten).
projectgraaf De projectgraaf houdt rekenlng met:
Van startpunt naar elndpunt vla pljlen.
Volgorde (vla pljlen) en duur van de taken.
Taken dle onafankelljk van elkaar plaatsvlnden (vanult het
startpunt met lljnen).
Maxlmale ultloop proces V iblj volledlge ibezetng =6 3 2 - 4 - 3 = 4 uur
competitiegraaf Graaf dle wordt toegepast om de voedselketen weer te geven. Een
compettegraaf ibestaat ult losse delen (componenten).
Ecologlsche Soorten ult één component van de compettegraaf reageren op dezelfde
ibetekenls van een manler op omgevlngsfactoren zoals temperatuur, vochtgheld en hoogte.
component ln de
compettegraaf
1
, B. Basisbegrippen (p9-p19)
graaf Dlagram, ibestaande ult punten dle al dan nlet veribonden zljn door een lljn.
Tussen een tweetal punten mogen meerdere lljnen lopen (meervoudlge
lljnen) en het ls ook toegestaan dat een lljn loopt van een punt naar zlchzelf
(lus). Opm: een graaf ls géén plategrond op schaal.
slmpele graaf Graaf zonder lussen en meervoudlge lljnen.
gewogen graaf Graaf met lljnen dle zljn voorzlen van een getal (gewlcht).
label (punt = n) Naam van een punt, aangeduld met een hoofdleter.
n = aantal punten een graaf.
label (lijn = m) Naam van een lljn, aangeduld met een klelne leter.
m = aantal lljnen van een graaf.
buren 2 punten dle door een lljn zljn veribonden.
valentie Het aantal lljnen dat aan dat punt vast zlt (een lus telt voor 2).
valentierij De nlet-dalende (stjgende) rlj van alle valentes van een graaf.
geïsoleerd punt Een punt dat nlet veribonden ls met een ander punt.
eindpunt Een punt dat met één lljn ls veribonden met een ander punt.
regelmatig van Een graaf G heet regelmatgg vangdegordegk als leder punt van G valente k
de orde heef.
Regelmatge graaf van de orde 3 (aantal lljnen 12, valentesom 24).
valentesom ls 2m
m = aantal lljnen
P heef valente 5. Q heef valente 3. R ls een geïssoleerd punt en S een
elndpunt. De valentesom ls 1 2 3 3 5= 14. De graaf heef 7 lljnen.
lsomorf structureel gelljk
gelljke grafen Twee gelaibelde grafen noemen we gelljk als er tussen overeenkomstg
gelaibelde punten evenveel lljnen lopen (zle graaf X en Y hleronder).
Als je de laibels van Y julst herplaatst, dan wordt graaf Y gelljk aan X.
isomorfe grafen Twee grafen, gelaibelde of ongelaibelde, noemen we lsomorf als het
mogelljk ls de punten van ibelde grafen te (her-)laibelen zo dat gelljke grafen
ontstaan
Als je ln graaf Z de julste laibels plaatst, dan ls deze gelljk aan graaf X en Y.
wandellng Een rlj opeenvolgende lljnen (ln een graaf). Een punt en lljn mogen ln een
wandellng meerdere keren voorkomen.
pad Een rlj opeenvolgende, verschillende lljnen (ln een graaf). Een punt mag ln
2
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 Quico42. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,49. Je zit daarna nergens aan vast.
