3.2 – Les chaînes et les cycles
Comme vous l'aurez remarqué, même un graphe relativement simple peut offrir une grande variété de combinaisons d'arêtes et de sommets. Évidemment, ces combinaisons ont été étudiées par plusieurs mathématiciens dans le passé. Cette section vous offrira un aperçu de ces observations et aussi de l'utilité que peut renfermer un simple graphe.
3.2.1 – Les chaînes et les cycles
Lorsqu'on se «déplace» dans un graphe, on effectue un enchaînement de sommets et d'arêtes. Cet enchaînement est donc appelé une chaîne. Lorsque cet enchaînement retourne au même sommet d'où il origine, on l'appellera plutôt un cycle.
Chaîne : On établit une chaîne en passant d'un sommet à un autre en suivant des arêtes.
Cycle : On complète un cycle lorsque l'on revient au sommet de départ après avoir passé par d'autres sommets
Prenons par exemple le graphe suivant :
Sur ce graphe, on peut établir une chaîne en se déplacent dans l'ordre suivant : ABCDE Sur le même graphe, on peut compléter le cycle en continuant la chaîne précédente vers le sommet A (cycle ABCDEA)
3.2.2 – Caractéristiques des chaînes et des cycles
Pour les cycles et les chaînes, on dénote trois caractéristiques importantes
- La longueur d'une chaîne ou d'un cycle : C'est le nombre d'arêtes empruntée pour rejoindre les sommets [de la chaîne ou du cycle].
- La distance entre deux sommets : C'est le nombre minimal d'arêtes qu'il faut emprunter pour passer d'un sommet à un autre.
- Chaîne ou cycle simple : Une chaîne ou un cycle est simple s'il peut être complété sans emprunter deux fois la même arête.
Reprenons notre graphe de départ pour faire quelques exemples :
| Caractéristiques | Exemples | |
|---|---|---|
| Longueur | La chaîne AEBC a une longueur de 3 | La chaîne AEBD a une longueur de 4 (il faut passer par C pour se rendre à D) |
| Distance | La distance AB est de 1 | La distance CE est de 2 (puisqu'il faut passer par B ou D) |
| Simple ou non | La chaîne CBEAD est simple | Le cycle ABCDEDA n'est pas simple |
3.2.3 – Les chaînes et cycles connus
Comme mentionné plus tôt, plusieurs mathématiciens se sont intéressés aux cycle et aux chaînes. Cette année, nous nous concentrerons sur deux mathématiciens connus et leur type particulier de graphe.
Leonhard Euler
Que vous le sachiez ou non, Euler est probablement l'un des mathématiciens qui a le plus influencé vos cours de mathématiques depuis les dernières années! Né en Suisse en 1707, Euler a travaillé dans plusieurs domaines des mathématiques et de la physique. Il a entre autres inventé le concept des fonctions!!! Il a aussi travaillé sur les graphes et les calculs infinitésimaux (ce qui se passe lorsque les mathématiques approchent l'infini).
Les graphes (chaînes ou cycles) d'Euler ont les caractéristiques suivantes :
On établit une chaîne Eulérienne ou un cycle Eulérien si on emprunte toutes les arêtes d'un graphe une seule fois. On ne doit pas passer deux fois sur la même arête, peu importe le sens emprunté. Par contre, on accorde peu d'importance au fait de repasser par des sommets.
Les chaînes eulériennes sont légèrement plus faciles à réaliser que les cycles eulériens, c'est pourquoi Euler a préparé une mise en garde pour construire un graphe qui pourra supporter un cycle eulérien : Tous les sommets de ce graphe doivent être de degré pair (deux, quatre, six, etc. arêtes par sommet).
Sir William Rowan Hamilton
Le travail de Sir Hamilton vous est probablement moins connu directement mais sans lui, plusieurs champs de la physique moderne ne serait pas ce qu'ils sont aujourd'hui. Ce mathématicien irlandais né en 1805 a notamment revisité et reformulé les principes de la physique newtonienne (au point où elle porte maintenant son nom), ce qui a jeté les bases de la physique classique comme l'électromagnétisme et a même un impact sur la physique quantique. Quel génie!
Les cycles et les chaînes hamiltoniennes sont plus simples.
Pour qu'une chaîne ou un cycle se qualifie de «Hamiltonien(ne)», la séquence doit simplement passer par tous les sommets une seule fois. On n'accorde aucune importance au fait de passer par toutes les arêtes ou non.
Les exercices liés à la section 3.2 se trouvent dans le manuel Vision Vol. 2 : p. 27 # 1, 2, 4, 5, 6, 7, 9, 10, 11, 14, 15, 16, 18 et 19