Toile d’Araignée©
Nombre de victoires: 161204
| (6 – 20) : | Cycle Chemin Aléatoire Défi |
Définitions + En quoi est-ce un jeu de « maths » ?
Les diagrammes de ce jeu sont basés sur un domaine des mathématiques connu sous le nom de la Théorie des Graphes !
Qu’est-ce qu’un graphe ?
Graphe : Un graphe se compose de nœuds et d’arêtes.
Noeud : Les « objets » que relie un graphe sont appelés des nœuds, des sommets, ou des points. Dans Toile d'Araignée, les nœuds sont les cercles.
Arête : une arête est la connexion entre deux nœuds dans le graphe. Dans Toile d'Araignée, les arêtes sont des lignes.
Extension d’un chemin
Chemin : un chemin est une séquence d’arêtes connectées avec un nœud de début et un nœud d'arrivée.
Chemin eulérien : Il s’agit d’un chemin qui passe par chaque arête du graphe exactement une fois.
Le but de ce jeu est de trouver un chemin eulérien.
Que sont les chemins eulériens dans la vie de tous les jours ?
Un chasse-neige, un camion de nettoyage des rues et un facteur sont des exemples où l'on doit passer par chaque rue tout en évitant de passer par une rue deux fois.
Le nom « Euler » vous semble-t-il familier ?
La Théorie des Graphes a commencé lorsque le mathématicien Leonhard Euler travaillait sur ce type de chemin.
Euler a écrit un article sur les Sept Ponts de Königsberg démontrant qu’il était impossible de traverser la ville en traversant chaque pont une seule fois.
Cliquez sur la carte du problème ci-dessous pour en savoir plus.
Cycle : Un cycle est un chemin qui commence et se termine au même noeud .
Cycle eulérien : Il s’agit d’un chemin eulérien qui est aussi un cycle . Si vous sélectionnez « Cycle » dans notre jeu ci-dessus, la solution sera toujours un cycle eulérien !
Paramètres du jeu
Dans le champ à côté de Noeuds, vous pouvez saisir n’importe quel nombre compris entre 6 et 20. Ce nombre sera le nombre de nœuds affichés sur le graphe. Plus le nombre est élevé, plus la solution devient difficile !
Ensuite, veuillez sélectionner un Type de graphe
Cycle : Les chemins gagnants se termineront toujours au noeud de départ.
Chemin : Les chemins gagnants ne se terminent pas au noeud de départ.
Aléatoire : Des graphes qui peuvent permettre un cycle eulérien ou un chemin eulérien. Les chemins gagnants peuvent se terminer au noeud de départ, ou pas.
Défi : Des graphes faits à la main où les arêtes se croisent et donc les ponts ne sont pas faciles à repérer.
Après avoir effectué ces choix, cliquez sur « Tisser nouvelle Toile » pour voir les modifications apportées aux paramètres !
Quel nœud dois-je choisir en premier ?
Degré : Le degré est une propriété d’un nœud. Il s’agit du nombre d’arêtes qui y sont connectées. En fonction de leur degré, nous distinguerons entre les noeuds de degré impair et les noeuds de degré pair.
Graphe connecté : Un graphe où chaque paire de nœuds peut être reliée via un chemin.
Pont : Une arête est un pont si les deux extrémités de l’arête ne peuvent pas être connectées autrement. Ainsi, après avoir traversé un pont, on ne peut pas revenir au noeud de départ du pont. La suppression d’un pont divise le graphe en deux composants distincts.
Graphe non orienté : Graphe dans lequel les arêtes n’ont pas d'orientation associée. Dans Toile d'Araignée, nous ne considérons que des graphes de ce type.
Graphe orienté : Graphe où chaque arête a une orientation associée, comme une rue à sens unique.
Un graphe non orienté contient un cycle eulérien lorsque tous les noeuds ont un degré pair (degré de 0, 2, 4, 6...) . Pour ceux-ci, vous pouvez sélectionner n’importe quel nœud comme nœud de départ et il sera toujours possible de gagner. Mais n'oubliez pas que vous devrez terminer là où vous avez commencé.
Un graphe contient un chemin eulérien, mais pas un cycle eulérien, lorsque exactement deux nœuds ont un degré impair (degré de 1, 3, 5, 7...) et tous les autres noeuds ont un degré pair. Dans ce cas, vous devez sélectionner un nœud de degré impair comme nœud de départ sinon il sera impossible de compléter le chemin eulérien.
Pourquoi exactement deux nœuds ?
Considérez chaque coup du jeu comme un mouvement « vers l'extérieur » du nœud d’où vous venez et « vers l'intérieur » du nœud auquel vous vous rendez. La plupart des nœuds suivront ce modèle d’appariement, et donc ils sont de degré pair.
Lorsque vous commencez le jeu, la première arête que vous marquez est un mouvement « vers l'extérieur du nœud de départ ». Celui-ci reste non apparié pour l'instant.
Pour créer un cycle eulérien, l’arête finale que vous marquez est un déplacement « vers l'intérieur » du nœud de départ. Cela crée une paire avec le premier coup, ce qui signifie que le nœud de départ a un degré pair.
Si le chemin eulérien du graphe n’est pas un cycle, l’arête finale que vous marquez est un déplacement non apparié vers un nœud qui n’est pas le nœud de départ. Le nœud de départ reste sans paire et donc garde son degré impair, et le nœud de fin aura également un degré impair.
Ne vous inquiétez pas pour les autres cas. Si le nombre de nœuds avec un degré impair n’était pas exactement 0 ou 2, il n’y aurait pas de chemins eulériens ni de cycles eulériens, ce qui signifie qu’il n’y aurait aucun moyen de gagner. De tels graphes ne devraient pas figurer dans ce jeu.
Questions préliminaires
Peut-il y avoir un nombre impair de nœuds avec un degré impair ?
Non.
Pourquoi?
Démonstration :
Le fait de compter toutes les extrémités de toutes les arêtes donne le même somme que d’additionner tous les degrés de tous les nœuds, on est d’accord ?
Étant donné que chaque arête a 2 extrémités, le nombre total d’extrémités de toutes les arêtes doit être pair. (La somme de nombres pairs est lui-même un nombre pair.)
Pour additionner les degrés de tous les nœuds, on additionne les degrés pairs, ce qui donne un nombre pair, et on additionne les degrés impairs.
S’il y avait un nombre impair de nœuds de degré impair, alors cette somme serait impaire, puis pair + impair = impair, donc le nombre total de degrés serait aussi impair. Mais il est égal au nombre total de toutes les extrémités de toutes les arêtes et cela est pair. Par conséquent, le nombre de nœuds de degré impair ne peut pas être impair, il doit forcément être pair.
Par exemple, 1 est un nombre impair, il n’y a donc pas de graphe avec seulement 1 nœud de degré impair.
Quand existe-t-il un chemin ou un cycle eulérien ?
Si un noeud a un degré pair, c’est-à-dire quand il y a 2, 4, 6,... arêtes reliées au nœud, alors en se déplaçant vers ce noeud, il reste un nombre non-nul impair d'arêtes non-empruntées, ce qui veut dire qu'on peut quitter ce noeud et suivre son chemin. Si le degré est impair, c’est-à-dire quand il y a 1, 3, 5,.. arêtes reliées, alors ce noeud est forcément soit le noeud de départ, soit le noeud d'arrivée du chemin. Puisqu’un chemin n’a que 2 extrémités, il ne peut y avoir que 2 nœuds de degré impair. Alors :
Pour avoir un cycle eulérien, un graphe ne doit avoir que des nœuds de degré pair, et pour avoir un chemin eulérien, il doit avoir 2 nœuds de degré impair dont un nœud sera le début et l’autre sera la fin du chemin.
Comment trouve-t-on un chemin ou un cycle eulérien ?
Comme indiqué ci-dessus, s’il n’y a pas de nœuds de degré impair, on peut commencer le chemin à partir de n’importe quel nœud et se terminer au même nœud. S’il y a exactement 2 nœuds de degré impair, l’un d’entre eux doit être le noeud de départ et l'autre sera forcément le noeud d'arrivée.
Est-ce qu'il peut y avoir des fautes lorsqu'on trace le chemin ?
Oui, c'est possible. Par exemple :
2 4 / \ / \ 1---3---5
Le degré de tous les noeuds est 2 sauf le noeud 3 qui a le degré 4. Ainsi, tous les degrés sont égaux et nous pouvons commencer n’importe où. Commençons par le nœud 1 et allons au nœud 3 et laissons tomber toutes les arêtes qui ont été traversées.
2 4 / \ / \ 1 3---5
L’arête 3-2 devient un pont. Le fait de traverser et de supprimer cette arête 3-2 produit un graphe déconnecté
2 4 / / \ 1 3---5
qui ne peut plus être complètement traversé. Par conséquent, il faut continuer à partir du noeud 3 vers le noeud 4 ou 5 pour pouvoir compléter le cycle eulérien.
Comment peut-on éviter de traverser un pont ?
Pour vérifier si une arête est un pont, on commence à une extrémité de l'arête et on visite tous ses nœuds voisins et tous leurs voisins, etc. Si l’on n’arrive pas de l’autre côté de l'arête, alors cette arête est un pont. Une telle recherche complète de tous les voisins n’est pas très coûteuse. Mais s’il faut le faire avant de franchir chaque bord, alors l’effort total est grand. L’algorithme complet s’appelle l’algorithme de Fleury, datant de 1883.
Existe-t-il un algorithme plus efficace ?
Un algorithme plus efficace est celui de Hierholzer (1873).
Si le graphe a 2 noeuds de degré impair, alors on trouve un chemin sinon un cycle, dans les deux cas très rapidement sans vérifier les ponts.
1) Après avoir supprimé toutes les arêtes utilisées, le degré des arêtes inutilisées restantes est pair pour tous les nœuds.
Pourquoi?
Si le degré d’un nœud était pair, alors on est allé vers ce noeud autant de fois qu'on l'a quitté, alors il reste pair. Si le degré était impair, alors c’est soit le nœud de départ, soit le nœud d’arrivée du premier chemin, et donc on est allé vers ce noeud + on l'a quitté au total un nombre impair de fois, donc le degré restant est impair − impair = pair.
2) Il doit y avoir au moins un nœud avec des arêtes adjacentes utilisées et inutilisées.
Pourquoi?
Parce que le graphe d’origine était connecté.
En raison de 1) on peut trouver un cycle d’arêtes inutilisées qui commence et qui se termine à ce nœud. En raison de 2) ce cycle peut être inclus dans le premier chemin/cycle lorsqu’il atteint ce nœud. Ce plongement de cycles d’arêtes jusqu’à présent inutilisées est répété jusqu’à ce que toutes les arêtes soient utilisées et que l’on ait donc un chemin eulérien ou un cycle eulérien qui utilise toutes les arêtes.
Quel est le prix de cette version plus rapide ?
Il faut se souvenir du chemin/cycle précédent afin de pouvoir inclure le cycle supplémentaire.
Exemple :
2 4 / \ / \ 1---3---5
Soit le premier cycle 1-3-2-1. Le nœud 3 se produit dans ce cycle et dans le cycle inutilisé 3-4-5-3. Nous l’insérons dans le premier cycle et obtenons le cycle 1-3-4-5-3-2-1. Il n’y a plus d’arêtes inutilisées donc l’algorithme s’arrête là, nous avons trouvé le cycle eulérien.
Comment insérer un cycle à l’aide de notre interface ?
On peut cliquer sur « Annuler » jusqu’à ce que l’on ait atteint le nœud le plus récent qui a des arêtes utilisées et inutilisées, tout comme le nœud 3 ci-dessus, puis passer par le cycle 3-4-5-3, puis continuer avec les bords annulés.
S’il y a un nœud de degré impair, faut-il trouver les deux pour tracer un premier chemin de l’un à l’autre ?
Non. Si l’on n’en trouve qu’un, alors on peut commencer le chemin à ce nœud et on se retrouvera automatiquement à l’autre nœud de degré impair, que l’on passe par toutes les arêtes ou non.
Pourquoi?
Parce que lorsque l’on arrive sur un nœud de degré pair, alors on est forcément passé par un un nombre impair d’arêtes reliées.
Pourquoi?
Chaque fois que l’on est arrivé à un nœud, on l'a également quitté, de sorte qu’un nombre pair d’arêtes est emprunté. Maintenant, on arrive à un noeud de degré pair, et on emprunte une de ses arêtes. Alors on a utilisé au total un nombre impair d’arêtes du nœud de degré pair.
Pair − impair = impair, donc il reste un nombre impair d’arêtes inutilisées. Un nombre impair est toujours différent de zéro, il y a donc au moins une arête inutilisée qui peut être utilisée pour quitter ce nœud. Par conséquent, l’un d’entre eux se terminera automatiquement au nœud de degré impair, que toutes les arêtes aient été utilisées ou non.
Comment trouver un nœud de degré impair ? Avez-vous des idées ?
On peut bien sûr vérifier le degré de chaque nœud jusqu’à ce que l’on trouve un nœud de degré impair. Voici une méthode sans devoir compter.
On peut choisir n’importe quel nœud. Si son degré est impair, alors on en a trouvé un. Si ce n’est pas le cas, on commence à tracer un cycle à partir de ce nœud. Il se terminera soit à un nœud de degré impair, et alors on a trouvé un nœud de degré impair, soit au nœud de départ. Si ceci arrive, alors on élimine toutes les arêtes utilisées et on recommence, c’est-à-dire qu’on choisit un nœud et qu’on trace un chemin ou un cycle. Cela continue jusqu’à ce que l’on trouve un nœud de degré impair ou qu’il n’y ait plus d’arêtes inutilisées. Dans ce cas, tous les noeuds ont un degré pair.
Que se passe-t-il si le graphe ressemble à une ville avec des rues à sens unique ?
Un graphe dont les arêtes ne peuvent être parcourues que dans une seule direction est appelé graphe dirigé. Suite à l’argumentation ci-dessus, les 2 affirmations suivantes sont plausibles.
Un graphe dirigé permet un cycle eulérien, si et seulement si, pour chaque noeud le nombre d’arêtes sortantes est égal au nombre d’arêtes entrantes.
Un graphe dirigé permet un chemin eulérien, si et seulement si
• un noeud a une arête sortante de plus que d'arêtes entrantes,
• un noeud a une arête entrante de plus que d'arêtes sortantes, et
• Toutes les autres arêtes ont le même nombre d’arêtes sortantes et entrantes.
Suivez ou abonnez-vous à l'Infolettre