Matheminecraft
Illustration Promotion des maths EPFL 2020
Faire des maths en jouant Ă un jeu vidĂ©o ? Si, si, câest possible avec matheminecraft ! DĂ©couvre cette carte aventure un peu spĂ©ciale, crĂ©Ă© par lâĂ©quipe de promotion des maths de lâEPFL !
Activité 1
Pour faire cette 1Úre activité, il te faudra :
- Du papier
- Un crayon
Pour commencer, essaie de trouver des dessins fermés qui se font sans lever le crayon.
Alors, en as-tu trouvé ?
En voici quelques exemples :
Il sâagit de cycles eulĂ©riens, c’est-Ă -dire quâon arrive Ă les dessiner et Ă revenir au point de dĂ©part, sans lever le crayon.
En mathĂ©matiques, les traits sont appelĂ©s des arĂȘtes et les coins des sommets.
Maintenant que tu as dĂ©couvert ces quelques exemples de cycles eulĂ©riens, essaye de rĂ©soudre le mĂȘme problĂšme qu’Euler !
En effet, le mathĂ©maticien suisse LĂ©onhard Euler est le premier Ă sâĂȘtre intĂ©ressĂ© Ă la question. Il a de ce fait fondĂ© la thĂ©orie des graphes.
Un des premiers problÚmes résolus par Euler est le suivant : la ville de Königsberg est constituée de 2 ßles, reliées par un pont. Il existe également 6 autres ponts, comme dessiné sur la carte ci-dessous. Existe-t-il une promenade dans la ville de Königsberg qui passe par les 7 ponts, et chacun une seule fois ?
Alors as-tu résolu le problÚme ?
VĂ©rifie ton raisonnement avec les explications ci-dessous :
Tu n’as pas trouvĂ© de solution et bien tu as raison !
Euler fut le premier Ă dĂ©terminer quâil nâexiste pas de solution Ă ce problĂšme.
En effet, le thĂ©orĂšme Ă©noncĂ© par Euler dit quâun graphe admet un cycle eulĂ©rien si et seulement si, de chacun de ses sommets, sort un nombre pair dâarĂȘtes (on dit que le degrĂ© des sommets est pair). Dans ce cas, on peut parcourir le graphe en ne passant quâune fois sur chaque arĂȘte, et revenir au point de dĂ©part.
Exemple de graphe admettant un cycle eulérien :
Et un graphe admet une chaine eulĂ©rienne (un chemin qui passe par chaque arĂȘte une seule fois mais ne revient pas forcĂ©ment au point de dĂ©part) si :
- tous les sommets sont de degré pair : cas du cycle eulérien vu dans le paragraphe ci-dessus.
- ou si exactement deux sommets sont de degrĂ© impair. Il est alors possible de parcourir le graphe en ne passant quâune fois sur chaque arĂȘte, mais sans revenir au point de dĂ©part.
Exemple : enveloppe ouverte
Si on ajoute une arĂȘte qui relie les 2 sommets dont le degrĂ© est impair, on obtient une chaine eulĂ©rienne fermĂ©e et le graphe devient donc un cycle eulĂ©rien. On peut de nouveau le parcourir en ne passant quâune fois sur chaque arĂȘte et revenir au point de dĂ©part.
Exemple :
Applications
La thĂ©orie des graphes est une branche des mathĂ©matiques comme la gĂ©omĂ©trie ou la logique. Câest un outil trĂšs utilisĂ© dans de nombreux domaines. Planifier des routes efficaces pour distribuer le courrier ou ramasser les ordures, effectuer des diagnostics dans les rĂ©seaux informatiques, planifier les voies aĂ©riennes entre des aĂ©roports, gĂ©rer un rĂ©seau Ă©lectrique, etc. sont autant dâexemples concrets utilisant cette thĂ©orie.
La thĂ©orie des graphes est trĂšs vaste et de nombreux autres problĂšmes existent: comment passer par tous les sommets dâun graphe ? Quel est le plus court chemin passant par tous les sommets dâun graphe et revenant au point de dĂ©part (problĂšme du voyageur de commerce) ? Etc.
Une partie des recherches en théorie des graphes consiste à trouver les algorithmes qui permettent de résoudre ces problÚmes.
Activité 2
Pour faire cette 2e activité, il te faudra :
- Un ordinateur
- Le jeu minecraft (attention, il est payant) et l’extension matheminecraft que tu peux tĂ©lĂ©charger ici .
Dans le jeu matheminecraft, câest le mĂȘme principe que les dessins que l’on a faits dans la premiĂšre activitĂ©! Les graphes sont dĂ©jĂ dessinĂ©s, et câest Ă toi de trouver le chemin qui te permet de les parcourir, sans passer 2 fois sur la mĂȘme arĂȘte. A toi donc de dĂ©terminer le cycle eulĂ©rien admis par ces graphes !
Les arĂȘtes sont reprĂ©sentĂ©es par des ponts, et les sommets par des ronds de couleurs.
