hamiltongraaf

Een hamiltongraaf is een graaf waarin je een hamiltoncircuit kunt bepalen. Hiermee bedoelen we:

een gesloten wandeling met minstens drie knopen
waarin, op de begin- en eindknoop na, elke knoop verschillend is
en tegelijk elke knoop voorkomt.

In bovenstaande figuur volgden we de gesloten wandeling(A, C, E, D, F, B, A). Stelling van Dirac: Elke graaf met minstens 3 knopen waarbij elke knoop als graad tenminste n/2 heeft is een hamiltongraaf. Experimenteer in volgende applet: Kan je in dezelfde graaf nog een ander hamiltoncircuit kunt bepalen? Klik op de resetknop en onderzoek ook andere grafen. Speel met de graden en onderzoek de stelling van Dirac. Bekijk ook het GGboek Hamiltongrafen, met oa. de reis rond de wereld en de paardensprong.

handelsreizigersprobleem

Een beroemd en uitdagend optimalisatieprobleem voor wiskundigen en informatici is het zogenaamde handelsreizigersprobleem (travelling salesman problem of TSP), naar een handelaar die wil uitzoeken hoe hij de route langs zijn klanten kan optimaliseren. Je leert er meer over in het GeoGebraboek handelsreizigersprobleem.

hamiltongraaf

handelsreizigersprobleem

Nieuw didactisch materiaal

Ontdek materiaal

Ontdek onderwerpen