Samenvatting Grafentheorie

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