1. Conventies
2. Tips
3. Definities
3.1. Schema wandeling
3.2. Schema graaf
4. Eigenschappen
5. Kortste pad
6. Optimale netwerk
7. Doolhof
8. Chinese postbodeprobleem
9. Handelsreizigersprobleem
10. Ondergrens LHC
11. Maximale afwijking t.o.v. het LHC
12. Vinden van een K3,3
13. Kleurbaarheid
13.1. Kleurgetal bepalen
13.2. Landkaartkleuring
14. Compatabilieitsgraaf
1/9 © Peter Zomerdijk
, 1. Conventies
• voorbeelden zijn omkaderd
• G: graaf
• A ⇒ B : als A dan B (nodig)
• A ⇔ B : als A dan B en als B dan A (nodig ꓥ voldoende: A ⇒ B ꓥ B ⇒ A)
2. Tips
• bewijzen vaak vanuit het ongerijmde
• bij vraag naar "minstens" of "minimaal", gebruik kleurbaarheid (zie 13)
3. Definities
graaf : diagram, bestaande uit punten die al dan niet verbonden zijn met lijnen
aantal punten n : aantal punten (knopen) in een G
aantal lijnen m : aantal lijnen in een G
label : unieke identificatie, hoofdletter voor punt, kleine letter voor lijn
buren : 2 direct verbonden punten
geïsoleerd punt : punt met valentie 0
eindpunt : punt met valentie 1
valentie : aantal lijnen aan een punt = aantal buren
lus : lijn vanaf een punt naar hetzelfde punt
dubbele lijn : meerdere lijnen tussen dezelfde buren
valentierij : niet-dalende rij van valenties
valentiesom V : som van de valenties
gerichte G : lijnen zijn pijlen en geven een gedwongen richting aan
gewogen G : lijnen hebben waardes
simpele G : bevat geen lussen en geen dubbele lijnen
wandeling = weg : serie aaneengesloten lijnen
rondwandeling : wandeling met start = finish
pad = pennenstreek : wandeling met elke lijn maximaal 1 keer
samenhangende G : tussen elk paar punten bestaat een pad
component = deel G : los gedeelte binnen een niet-samenhangende G
brug : lijn die bij weglating het aantal componenten verhoogd
orde k : dezelfde valentie van elk punt
regelmatige G : simpele G van orde k
volledige G Kn : regelmatige G van n punten met een lijn tussen elk paar punten
2-delige G : punten kunnen in 2 groepen (W,Z) met elke lijn tussen 1 W en 1 Z
volledige 2-delige G Kp,q : tussen elk puntenpaar W-Z precies 1 lijn
circuit : pad met startpunt = finishpunt
n-hoek : circuit met n punten en n lijnen
complement Gc : bestaat uit alle punten en de ontbrekende lijnen t.o.v. de volledige
gelijke G : evenveel lijnen tussen overeenkomstig gelabelde punten (exact gelijk)
isomorfe G ; gelijk maar met andere of zonder labels
zelfcomplementaire G ; de originele G (5-hoek) is isomorf met het complement (5-puntige ster)
eulerpad ; pad met elke lijn precies 1 keer
semi-euler G ; samenhangende G met eulerpad
eulercircuit : circuit met elke lijn precies 1 keer
euler G : samenhangende G met eulercircuit
2/9 © Peter Zomerdijk
2. Tips
3. Definities
3.1. Schema wandeling
3.2. Schema graaf
4. Eigenschappen
5. Kortste pad
6. Optimale netwerk
7. Doolhof
8. Chinese postbodeprobleem
9. Handelsreizigersprobleem
10. Ondergrens LHC
11. Maximale afwijking t.o.v. het LHC
12. Vinden van een K3,3
13. Kleurbaarheid
13.1. Kleurgetal bepalen
13.2. Landkaartkleuring
14. Compatabilieitsgraaf
1/9 © Peter Zomerdijk
, 1. Conventies
• voorbeelden zijn omkaderd
• G: graaf
• A ⇒ B : als A dan B (nodig)
• A ⇔ B : als A dan B en als B dan A (nodig ꓥ voldoende: A ⇒ B ꓥ B ⇒ A)
2. Tips
• bewijzen vaak vanuit het ongerijmde
• bij vraag naar "minstens" of "minimaal", gebruik kleurbaarheid (zie 13)
3. Definities
graaf : diagram, bestaande uit punten die al dan niet verbonden zijn met lijnen
aantal punten n : aantal punten (knopen) in een G
aantal lijnen m : aantal lijnen in een G
label : unieke identificatie, hoofdletter voor punt, kleine letter voor lijn
buren : 2 direct verbonden punten
geïsoleerd punt : punt met valentie 0
eindpunt : punt met valentie 1
valentie : aantal lijnen aan een punt = aantal buren
lus : lijn vanaf een punt naar hetzelfde punt
dubbele lijn : meerdere lijnen tussen dezelfde buren
valentierij : niet-dalende rij van valenties
valentiesom V : som van de valenties
gerichte G : lijnen zijn pijlen en geven een gedwongen richting aan
gewogen G : lijnen hebben waardes
simpele G : bevat geen lussen en geen dubbele lijnen
wandeling = weg : serie aaneengesloten lijnen
rondwandeling : wandeling met start = finish
pad = pennenstreek : wandeling met elke lijn maximaal 1 keer
samenhangende G : tussen elk paar punten bestaat een pad
component = deel G : los gedeelte binnen een niet-samenhangende G
brug : lijn die bij weglating het aantal componenten verhoogd
orde k : dezelfde valentie van elk punt
regelmatige G : simpele G van orde k
volledige G Kn : regelmatige G van n punten met een lijn tussen elk paar punten
2-delige G : punten kunnen in 2 groepen (W,Z) met elke lijn tussen 1 W en 1 Z
volledige 2-delige G Kp,q : tussen elk puntenpaar W-Z precies 1 lijn
circuit : pad met startpunt = finishpunt
n-hoek : circuit met n punten en n lijnen
complement Gc : bestaat uit alle punten en de ontbrekende lijnen t.o.v. de volledige
gelijke G : evenveel lijnen tussen overeenkomstig gelabelde punten (exact gelijk)
isomorfe G ; gelijk maar met andere of zonder labels
zelfcomplementaire G ; de originele G (5-hoek) is isomorf met het complement (5-puntige ster)
eulerpad ; pad met elke lijn precies 1 keer
semi-euler G ; samenhangende G met eulerpad
eulercircuit : circuit met elke lijn precies 1 keer
euler G : samenhangende G met eulercircuit
2/9 © Peter Zomerdijk
