Classes de connexité et chemins hamiltoniens
Dans les grandes entreprises et autres organisations, plusieurs branches des mathématiques trouvent une application pratique dans l’aide à la décision. On les regroupe sous la locution recherche opérationnelle. Parmi celles-ci, la théorie des graphes tient une place de choix, notamment dans le transport, l’énergie et la gestion de projets, avec pour double but de gagner du temps tout en rationalisant les coûts.
Cette page vous présente quelques notions de cette théorie, indissociable des matrices. Son niveau est celui de la première année après le bac. Au préalable, il est utile de connaître la notion de chemin.
Les classes de connexité
La connexité est une notion qui s’applique aux graphes non orientés mais aussi aux graphes orientés.
Soit un ensemble \(E.\)
On appelle classe de connexité d’un élément \(x \in E\) l’ensemble des éléments de \(E\) pour lesquels il existe un chemin qui a pour origine et pour extrémité \(x\) ainsi que l’élément \(x\) lui-même. Ceux qui ont pour origine \(x\) sont descendants et ceux qui ont pour extrémité \(x\) sont ascendants. Dans un chemin de longueur 1 (ou d’ordre 1), l’ascendant est l’antécédent et le descendant est l’image.
L’ensemble des classes de connexité (ou composantes connexes) de \(E\) forme une partition de \(E.\)
Soit la relation \(R.\) Si \(x\) précède \(y\) ou est confondu avec lui, nous avons \(x\, R\, y.\) Donc \(x\, R\, x.\) Par ailleurs, si \(x\, R\, y\) et \(y\, R\, z\) alors \(x\, R\, z.\) Si vous êtes observateur, vous en concluez que la relation \(R\) est un préordre (elle est réflexive et transitive).
Si \(\forall x \in E\) et \(\forall y \in E\) nous avons \(x\, R\, y\) et \(y\, R\, x\) alors \(E\) est fortement connexe. La matrice (booléenne) associée à la fermeture transitive forte de \(R\) n’est composée que de 1.
Exemple
Soit le graphe suivant. Quelles sont les classes de connexité ?
La première technique consiste à observer directement le graphe.
On part d’un élément et, outre lui-même, on liste ses ascendants et descendants. Ainsi \(a\) a pour ascendant \(b\) et donc \(c\) qui est ascendant de \(b,\) et pour descendants \(e\) puis \(d\) et \(c\) puis \(b.\) Donc \(A_a = \{a, b, c\}\) et \(D_a = \{a, b, c, d, e\}.\) D’où \(A_a \cap D_a = \{a, b, c\}.\) C’est notre première classe. Attachons-nous aux éléments qui nous restent. \(A_d = \{a, d, e\}\) et \(D_d = \{d, e\}.\) Nous avons identifié une seconde classe. Il n’est pas utile de réitérer l’opération avec \(b,\) \(c\) et \(e\) puisque tous les éléments sont identifiés comme faisant partie d’une classe.
La seconde technique consiste à chercher la fermeture transitive de la matrice \(M\) associée au graphe.
\(M = \left( {\begin{array}{*{20}{c}} 0&0&1&0&1\\ 1&0&1&0&0\\ 0&1&0&0&0\\ 0&0&0&1&1\\ 0&0&0&1&0\end{array}} \right)\)
Nous devons lui ajouter la matrice identité.
\(M + I = \left( {\begin{array}{*{20}{c}} 1&0&1&0&1\\ 1&1&1&0&0\\ 0&1&1&0&0\\ 0&0&0&1&0\\ 0&0&0&1&1\end{array}} \right)\)
Commençons par élever au carré la matrice obtenue (revoir les puissances d'une matrice carrée, le cas échéant).
\((M + I)^2 = \left( {\begin{array}{*{20}{c}}0&1&0&1&1\\ 0&1&1&0&1\\ 1&0&1&0&0\\ 0&0&0&1&1\\ 0&0&0&1&1\end{array}} \right)\)
On peut essayer toutes les puissances jusqu’à trouver celle au-delà de laquelle il est inutile de continuer (la matrice ne « bouge » plus) ou élever la précédente au carré et encore au carré, voire tester directement des puissances très élevées. En effet, nous ne cherchons pas quand la matrice se stabilise mais seulemnt à quoi elle ressemble lorsqu’elle est associée à la fermeture transitive.
\((M + I)^3 = \left( {\begin{array}{*{20}{c}}1&0&1&1&1\\ 1&1&1&1&1\\ 0&1&1&0&1\\ 0&0&0&1&1\\ 0&0&0&1&1\end{array}} \right)\)
\((M + I)^4 = \left( {\begin{array}{*{20}{c}}0&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 0&0&0&1&1\end{array}} \right)\)
\((M + I)^5 = \left( {\begin{array}{*{20}{c}}1&1&1&1&1\\ 1&1&1&1&1\\ 1&1&1&1&1\\ 0&0&0&1&1\\ 0&0&0&1&1\end{array}} \right)\) \(=\) \((M +I)^6\)
Nous avons trouvé la fermeture transitive.
Commençons par \(a.\) La première ligne est celle de ses descendants et la première colonne est celle de ses ascendants. Les éléments communs sont ceux de la classe de connexité de \(a.\) Même chose avec \(d.\) Vérifiez que l’on trouve bien le même résultat qu’avec la technique précédente.
Chemin hamiltonien
Un chemin qui passe une fois et une seule par tous les sommets d’un graphe est un chemin hamiltonien. S'il est fermé, c’est un circuit hamiltonien.
Ce qui peut s’apparenter à un jeu si le graphe est petit et à un casse-tête monstrueux s’il est grand est facilité par la mise en évidence des classes de connexité.
Dans notre exemple, une seule relation existe entre les deux sous-ensembles : celle qui a pour origine \(a\) et pour but \(e.\)
Il faut donc partir de la classe qui contient \(a\) et placer \(a\) en dernier. Donc \((c, b, a).\) La seconde classe doit bien sûr commencer par \(e.\)
Il s’ensuit que le chemin hamiltonien est \((c, b, a, e, d).\) Vérifiez sur le graphe que ce chemin passe bien une fois et une seule par chaque élément. C’est OK ?
