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 ?

Source : https://fr.wikipedia.org/wiki/Probl%C3%A8me_des_sept_ponts_de_K%C3%B6nigsberg

 

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.

Source : https://www.epfl.ch/schools/sb/research/math/wp-content/uploads/2020/04/comprendre_matheminecraft.pdf

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.