Brommerforum.nl - Print

Brommerforum.nl - Print: Reply

Deze reply is gepost in de afdeling Main Forum in het onderwerp 'puzzle/raadsel' (ID 21241).
De reply is geschreven door Tomos 50 (UserID 4174) op 17-8-2004 14:22.

Het kan niet:
Wanneer is een graaf te tekenen in het platte vlak, zonder dat de zijden elkaar doorsnijden? Hiervoor is een stelling van Kuratowki, die zegt dat een graaf vlak is, precies dan als deze graaf geen deelgraaf heeft die hetzelfde is als K3,3 of K5. Hierin is K5 de volledige graaf op vijf punten die je krijgt door tussen vijf punten elke mogelijke verbinding te trekken. K3,3 krijg je door twee verzamelingen van elk drie punten te nemen en elk punt in de ene met elk punt in de andere te verbinden (Dit is het bekende gas-water-licht probleem: Drie huizen moeten elk van gas, water en licht worden voorzien door een directe verbinding met elk van de fabrieken. Dit is alleen mogelijk als de leidingen mogen kruisen).

Snap je?