Examenhandleiding & Studiegids
Grafentheorie en Netwerkopti malisati e (OR1 - Diagnosti sche Toets Week
5)
Inhoud
1. Fondamenten van de Grafentheorie en Vlakke Grafen...............................................................3
Introductie & Strategisch Belang..................................................................................................3
Basiseigenschappen en Takken Tellen..........................................................................................3
De Stelling van de Graadsom....................................................................................................3
Synthese van de Graadsomlogica.............................................................................................3
Vlakke Grafen en Facetten............................................................................................................3
Formele Definities.....................................................................................................................3
Stelling voor de Facetgradensom..............................................................................................4
De Formule van Euler....................................................................................................................4
Wiskundige Formulering...........................................................................................................4
Analyse en Gestructureerde Berekeningen..............................................................................4
Uitgewerkt Examenvoorbeeld...................................................................................................4
Klassieke Grafen en Kuratowski's Stelling.....................................................................................5
De Niet-Vlakke Klassiekers........................................................................................................5
Stelling voor Simpele Vlakke Grafen.........................................................................................5
Definities: Onderverdeling en Uitbreiding................................................................................5
De Stelling van Kuratowski........................................................................................................6
Didactische Analyse van een Kuratowski-Graaf........................................................................6
Examenprotocol Vlakheidsonderzoek..........................................................................................6
Protocol Details:........................................................................................................................7
Verbinding & Transitie..................................................................................................................8
2. Het Maximale Stroom Probleem (Maximum Flow Problem).......................................................8
Introductie & Strategisch Belang..................................................................................................8
Netwerkelementen en Probleemformulering..............................................................................8
Techniek voor Meervoudige Bronnen en Putten..........................................................................9
Het Augmenting Path Algoritme (Toenemende Paden Methode).............................................10
Residueel Netwerk en Residuele Capaciteiten.......................................................................10
Augmenting Path (Toenemend Pad).......................................................................................10
1
, Het Stapsgewijze Algoritme (3 Fasen).....................................................................................11
De Waaierprocedure (Fanning-out Procedure)......................................................................11
De Max-Flow Min-Cut Stelling....................................................................................................12
Definities..................................................................................................................................12
De Stelling................................................................................................................................12
Volledig Uitgewerkte Casus: Seervada Park...............................................................................12
Stapsgewijze Iteration van het Augmenting Path Algoritme..................................................13
Optimale Eindoplossing en Snedeverificatie...........................................................................13
Exacte Minimale Snede Verificatie (Figuur 10.10)..................................................................14
Praktijktoepassingen en Bedrijfsimpact.....................................................................................14
Hewlett-Packard (HP)..............................................................................................................14
Gassco & StatoilHydro.............................................................................................................14
Excel Solver Formulering.............................................................................................................14
Verbinding & Transitie................................................................................................................15
3. Het Minimale Kosten Stroom Probleem (Minimum Cost Flow Problem)..................................15
Introductie & Strategisch Belang................................................................................................15
Kernkenmerken en Reducties.....................................................................................................16
De 8 Randvoorwaarden...........................................................................................................16
Speciale Gevallen (Reducties van het Koepelmodel)..............................................................17
Essentiële Examenvalkuil & Mathematische Restrictie..............................................................17
Wiskundige Onderbouwing.....................................................................................................17
Examenconsequentie..............................................................................................................17
Verbinding & Transitie................................................................................................................17
4. Examenvoorbereiding: Valkuilen, Formules en Kernbegrippen.................................................18
Introductie & Strategisch Belang................................................................................................18
Veelgemaakte Fouten & Rekenregels.........................................................................................18
Formule- en Stellingencarrousel (LaTeX Overzicht)....................................................................19
Begrippenlijst & Definities..........................................................................................................20
Korte Eindsamenvatting..............................................................................................................20
2
, 1. Fondamenten van de Grafentheorie en
Vlakke Grafen
Introductie & Strategisch Belang
Binnen de Operations Research vormt de grafentheorie de wiskundige hoeksteen voor het
modelleren, analyseren en optimaliseren van fysieke en abstracte netwerkstructuren. Een
fundamenteel vraagstuk binnen het netwerkontwerp is het modelleren van verbindingen die
elkaar niet mogen kruisen. Denk hierbij aan het ontwerpen van een wegennet zonder kostbare
viaducten of tunnels, of het solderen van een elektronisch circuit op een printplaat waarbij
geleidende sporen elkaar niet mogen raken. Het opstellen van zulke kruisingsvrije netwerken
leidt direct tot de theorie van de vlakke grafen. Het beheersen van de topologische
eigenschappen van deze grafen is van cruciaal strategisch belang voor het succesvol afleggen
van de diagnostische toets van week 5.
Basiseigenschappen en Takken Tellen
De Stelling van de Graadsom
Voor elke willekeurige graaf G= (V , E ) met n=|V | knopen en m=|E| takken (of lijnen) geldt de
Stelling van de Graadsom:
∑ deg ( v ) =2 m
v ∈V
Waarbij deg ( v ) de graad van knoop v voorstelt (het aantal takken dat in knoop v samenkomt).
Synthese van de Graadsomlogica
De wiskundige onderbouwing van deze stelling rust op een fundamenteel telprincipe: elke
individuele tak e ∈ E verbindt precies twee knopen (of vormt een lus op één knoop). Wanneer
de graden van alle knopen in het netwerk worden opgeteld, levert elke tak exact twee bijdragen
aan de totale som — één bijdrage aan elk van zijn twee eindpunten. Dit betekent dat de som
van de knoopgraden in een graaf zonder uitzondering gelijk is aan het dubbele van het aantal
takken (2 m). Een direct en universeel gevolg hiervan is dat de graadsom van elke graaf altijd een
even getal is.
Vlakke Grafen en Facetten
Formele Definities
Vlakke Graaf (Planar Graph): Een graaf heet vlak als er een representatie van bestaat die
in het platte vlak getekend kan worden zonder dat de takken elkaar doorsnijden of
kruisen (behalve in hun gemeenschappelijke knopen).
Vlakke Tekening: Een specifieke weergave van een vlakke graaf waarin geen enkele
doorsnijding van takken optreedt. Een graaf kan vlak zijn, zelfs als een initiële weergave
van die graaf wél kruisende takken vertoont.
3
Grafentheorie en Netwerkopti malisati e (OR1 - Diagnosti sche Toets Week
5)
Inhoud
1. Fondamenten van de Grafentheorie en Vlakke Grafen...............................................................3
Introductie & Strategisch Belang..................................................................................................3
Basiseigenschappen en Takken Tellen..........................................................................................3
De Stelling van de Graadsom....................................................................................................3
Synthese van de Graadsomlogica.............................................................................................3
Vlakke Grafen en Facetten............................................................................................................3
Formele Definities.....................................................................................................................3
Stelling voor de Facetgradensom..............................................................................................4
De Formule van Euler....................................................................................................................4
Wiskundige Formulering...........................................................................................................4
Analyse en Gestructureerde Berekeningen..............................................................................4
Uitgewerkt Examenvoorbeeld...................................................................................................4
Klassieke Grafen en Kuratowski's Stelling.....................................................................................5
De Niet-Vlakke Klassiekers........................................................................................................5
Stelling voor Simpele Vlakke Grafen.........................................................................................5
Definities: Onderverdeling en Uitbreiding................................................................................5
De Stelling van Kuratowski........................................................................................................6
Didactische Analyse van een Kuratowski-Graaf........................................................................6
Examenprotocol Vlakheidsonderzoek..........................................................................................6
Protocol Details:........................................................................................................................7
Verbinding & Transitie..................................................................................................................8
2. Het Maximale Stroom Probleem (Maximum Flow Problem).......................................................8
Introductie & Strategisch Belang..................................................................................................8
Netwerkelementen en Probleemformulering..............................................................................8
Techniek voor Meervoudige Bronnen en Putten..........................................................................9
Het Augmenting Path Algoritme (Toenemende Paden Methode).............................................10
Residueel Netwerk en Residuele Capaciteiten.......................................................................10
Augmenting Path (Toenemend Pad).......................................................................................10
1
, Het Stapsgewijze Algoritme (3 Fasen).....................................................................................11
De Waaierprocedure (Fanning-out Procedure)......................................................................11
De Max-Flow Min-Cut Stelling....................................................................................................12
Definities..................................................................................................................................12
De Stelling................................................................................................................................12
Volledig Uitgewerkte Casus: Seervada Park...............................................................................12
Stapsgewijze Iteration van het Augmenting Path Algoritme..................................................13
Optimale Eindoplossing en Snedeverificatie...........................................................................13
Exacte Minimale Snede Verificatie (Figuur 10.10)..................................................................14
Praktijktoepassingen en Bedrijfsimpact.....................................................................................14
Hewlett-Packard (HP)..............................................................................................................14
Gassco & StatoilHydro.............................................................................................................14
Excel Solver Formulering.............................................................................................................14
Verbinding & Transitie................................................................................................................15
3. Het Minimale Kosten Stroom Probleem (Minimum Cost Flow Problem)..................................15
Introductie & Strategisch Belang................................................................................................15
Kernkenmerken en Reducties.....................................................................................................16
De 8 Randvoorwaarden...........................................................................................................16
Speciale Gevallen (Reducties van het Koepelmodel)..............................................................17
Essentiële Examenvalkuil & Mathematische Restrictie..............................................................17
Wiskundige Onderbouwing.....................................................................................................17
Examenconsequentie..............................................................................................................17
Verbinding & Transitie................................................................................................................17
4. Examenvoorbereiding: Valkuilen, Formules en Kernbegrippen.................................................18
Introductie & Strategisch Belang................................................................................................18
Veelgemaakte Fouten & Rekenregels.........................................................................................18
Formule- en Stellingencarrousel (LaTeX Overzicht)....................................................................19
Begrippenlijst & Definities..........................................................................................................20
Korte Eindsamenvatting..............................................................................................................20
2
, 1. Fondamenten van de Grafentheorie en
Vlakke Grafen
Introductie & Strategisch Belang
Binnen de Operations Research vormt de grafentheorie de wiskundige hoeksteen voor het
modelleren, analyseren en optimaliseren van fysieke en abstracte netwerkstructuren. Een
fundamenteel vraagstuk binnen het netwerkontwerp is het modelleren van verbindingen die
elkaar niet mogen kruisen. Denk hierbij aan het ontwerpen van een wegennet zonder kostbare
viaducten of tunnels, of het solderen van een elektronisch circuit op een printplaat waarbij
geleidende sporen elkaar niet mogen raken. Het opstellen van zulke kruisingsvrije netwerken
leidt direct tot de theorie van de vlakke grafen. Het beheersen van de topologische
eigenschappen van deze grafen is van cruciaal strategisch belang voor het succesvol afleggen
van de diagnostische toets van week 5.
Basiseigenschappen en Takken Tellen
De Stelling van de Graadsom
Voor elke willekeurige graaf G= (V , E ) met n=|V | knopen en m=|E| takken (of lijnen) geldt de
Stelling van de Graadsom:
∑ deg ( v ) =2 m
v ∈V
Waarbij deg ( v ) de graad van knoop v voorstelt (het aantal takken dat in knoop v samenkomt).
Synthese van de Graadsomlogica
De wiskundige onderbouwing van deze stelling rust op een fundamenteel telprincipe: elke
individuele tak e ∈ E verbindt precies twee knopen (of vormt een lus op één knoop). Wanneer
de graden van alle knopen in het netwerk worden opgeteld, levert elke tak exact twee bijdragen
aan de totale som — één bijdrage aan elk van zijn twee eindpunten. Dit betekent dat de som
van de knoopgraden in een graaf zonder uitzondering gelijk is aan het dubbele van het aantal
takken (2 m). Een direct en universeel gevolg hiervan is dat de graadsom van elke graaf altijd een
even getal is.
Vlakke Grafen en Facetten
Formele Definities
Vlakke Graaf (Planar Graph): Een graaf heet vlak als er een representatie van bestaat die
in het platte vlak getekend kan worden zonder dat de takken elkaar doorsnijden of
kruisen (behalve in hun gemeenschappelijke knopen).
Vlakke Tekening: Een specifieke weergave van een vlakke graaf waarin geen enkele
doorsnijding van takken optreedt. Een graaf kan vlak zijn, zelfs als een initiële weergave
van die graaf wél kruisende takken vertoont.
3
