Page 11 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

Wij geven de situatie schematisch weer met een graaf.
Indien de leidingen mekaar onderling mogen snijden dan is er uiteraard een erg eenvoudige oplossing.

Het valt op dat er minder leidingen zijn die elkaar snijden indien we dit schematisch met een zeshoek
(rechtse figuur) weergeven. Er zijn echter nog steeds 3 leidingen die snijden.
Binnen de zeshoek kan maar één leiding worden getekend zonder de andere te snijden. Wij verwijderen
in de volgende figuur de verbinding tussen Huis2 en Water en Huis3 en Gas.
Enkel en alleen het eerste huis is voorzien van water, gas en elektriciteit.
In het tweede huis ontbreekt water en het derde huis gas.

Het is nog wel mogelijk om langs de buitenkant van de zeshoek nog een verbinding te maken die het
tweede huis voorziet van water.

t
e
n
.
o
l
e
h
t
a
Indien we nu huis3 van gas moeten voorzien dan kan dit enkel en alleen indien de gasleiding de vorige m
.
waterleiding snijdt. w

Besluit: De puzzel van de drie nutsvoorzieningen is NIET oplosbaar. w
w
GeoGebra bestand https://www.geogebra.org/m/bfsbxutu

© 2021 Ivan De Winne ivan@mathelo.net 10