À l’exemple 7.1.29 ainsi qu’à l’exercice 7.1.6.2 on a remarqué que deux graphes qui sont définis différemment pouvaient décrire la même structure de graphe. À l’inverse, on peut parfois facilement se convaincre que deux graphes sont fondamentalement différents. On aimerait donc pouvoir être en mesure de déterminer, lorsqu’on considère deux graphes, si ceux-ci sont en quelque sorte équivalents, ou bien s’ils sont fondamentalement différents.
Ce problème est un problème très courant dans beaucoup de branches des mathématiques. Pour résoudre cette question, et pour la différencier de la notion d’égalité, les mathématiciens ont développé le concept d’isomorphismes (de graphes dans notre cas.)
Dans cette section, on débutera avec l’étude de deux graphes qui sont essentiellement les mêmes graphes, bien qu’ils soient décrits différemment. De plus, on considère de nouvelles façons de représenter des graphes. Ces outils permettront de mieux détecter si deux graphes sont équivalents, surtout d’un point de vue algorithmique.
Par la suite, on introduit formellement ce qu’on entend lorsqu’on dit que deux graphes sont équivalents à l’aide de la définition d’isomorphismes de graphes. Finalement, on aimerait trouver des critères qui permettent de montrer que deux graphes ne sont pas équivalents. Pour se faire, on identifie des invariants, c’est-à-dire certaines caractéristiques qui sont communes lorsque deux graphes sont équivalents.
On considère les graphes simples \(G_1=(S_1,A_1)\text{,}\) avec \(S_1=\{a,b,c,d\}\) et \(A_1=\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\}\text{,}\) et \(G_2=(S_2,A_2)\text{,}\) avec \(S_2=\{1,2,3,4\}\) et \(A_2=\{\{1,2\},\{2,3\},\{2,4\},\{3,4\}\}\text{.}\) Ces deux graphes ne sont pas égaux. En effet, lorsqu’on définit un graphe, on le fait à l’aide de l’ensemble de ses sommets et l’ensemble de ses arêtes. Pour que deux graphes soient égaux, on doit avoir une égalité entre ces ensembles, c’est-à-dire que \(G_1:=(S_1,A_1)=G_2:=(S_2,A_2)\) si et seulement si \(S_1=S_2\) et \(A_1=A_2\text{.}\) Dans notre cas, puisque \(S_1:=\{a,b,c,d\}\neq S_2=\{1,2,3,4\}\text{,}\) on a que \(G_1\neq G_2\text{.}\)
Cependant, en regardant attentivement ces deux graphes, on remarque beaucoup de similarités. En effet, on voit rapidement que \(|S_1|=4=|S_2|\) et que \(|A_1|=4=|A_2|\text{.}\) Plus encore, on remarque chacun des graphes possède un unique sommet de degré \(3\) (c’est-à-dire que \(\deg(c)=3=\deg(2)\)), et un unique sommet de degré \(1\) (\(\deg(d)=1=\deg(1)\)). Ceci est un indicateur que ces deux graphes sont possiblement équivalents d’une certaine façon. En effet, si on trace les deux graphes, on voit immédiatement qu’ils sont essentiellement les mêmes.
Clairement, ces deux graphes sont essentiellement les mêmes. On donnera la définition d’isomorphisme en 7.2.2 qui permettra de formaliser ce concept. On commence par donner de nouvelles façons pour représenter nos graphes.
Une première façon de représenter un graphe est d’utiliser une liste d’adjacence.
Définition7.2.2.
Soit \(G=(S,A)\) un graphe simple. On représente celui-ci à l’aide d’un tableau dont la première colonne représente les sommets du graphe, et la deuxième colonne représente les voisins du sommet.
Cette représentation peut nous aider à détecter certaines propriétés en commun de nos graphes. En particulier, lorsque le nombre de sommets augmente, la liste d’adjacence est souvent plus pratique que le dessin pour bien comprendre nos graphes. Aussi, on peut se servir d’une liste d’adjacence pour définir un graphe dans sage.
Une autre façon de représenter un graphe est à l’aide d’une matrice d’adjacence. Pour pouvoir définir cet objet, on doit d’abord définir ce qu’est une matrice. Une matrice n’est rien d’autre qu’un tableau de nombre. Il s’agit d’un objet qui est surtout étudié dans un cours d’algèbre linéaire. Ici, on donne la définition d’une matrice ainsi que quelques exemples de base afin de se familiariser avec la notation avant de définir une matrice d’adjacence.
Une matrice \(m\times n\) (on dit \(m\) par \(n\)) est un ensemble de \(m\cdot n\) nombres agencés dans un tableau de \(m\) lignes et \(n\) colonnes. Si\(A\) est une matrice, on dénote souvent par \(a_{i,j}\) l’élément situé à la ligne \(i\) et à la colonne \(j\text{.}\) On écrira alors \(A=\bigl(a_{i,j}\bigr)\) pour vouloir dire
est une matrice \(3\times 3\) avec \(c_{1,1}=1\text{,}\)\(c_{2,2}=2\) et \(c_{3,1}=7\text{.}\) Puisque le nombre de lignes et de colonnes est \(3\text{,}\) on dit que \(C\) est une matrice carrée d’ordre \(3\text{.}\)
On peut maintenant définir la matrice d’adjacence d’un graphe. Il est important de noter que la définition d’une matrice d’adjacence n’est pas unique pour chaque graphe. En effet, la définition dépendra de l’ordre dans lequel on considère les sommets du graphe.
Soit \(G=(S,A)\) un graphe simple à \(n\) sommets, avec \(S=\{s_1, s_2, \dots , s_{n}\}\text{,}\) alors la matrice d’adjacence du graphe \(G\) selon l’ordre des sommets \(s_1, s_2, \dots, s_n\text{,}\) qu’on notera \(M_G=\bigl(m_{i,j}\bigr)\text{,}\) est la matrice \(n\times n\) définie par
Étand donné un graphe, on veut être en mesure de trouver sa matrice d’adjacence. Inversement, étant donnée une matrice d’adjacence, peut-on déterminer un graphe correspondant.
On peut utiliser Sage afin de tracer un graphe à partir d’une matrice d’adjacence. Voici le graphe de l’exemple 7.2.12 obtenu à partir d’une matrice d’adjacence. Ici, on remarque que la forme obtenue par Sage est très différente de celle donnée dans l’exemple 7.2.12. En fait, cette forme semble suggérer que le graphe \(G\) de l’exemple 7.2.10 est équivalent au graphe \(H\) de l’exemple 7.2.12. On montrera en effet que c’est le cas. Pour ce faire, on va enfin définir ce qu’est un isomorphisme de graphes.
On est finalement prêt à donner une définition rigoureuse du fait que deux graphes qui sont décrits différemment peuvent en fait représenter deux graphes équivalents. Pour que deux graphes soient équivalents, il faut que l’un des graphes soit obtenu à partir de l’autre en changeant les noms des sommets. Ce changement de nom sera donné sous la forme d’une bijection entre les ensembles de sommets qui préservent les arêtes.
Soit \(G_1=(S_1,A_1)\) et \(G_2=(S_2,A_2)\) deux graphes. On dit que \(G_1\) et \(G_2\) sont isomorphes s’il existe une fonction \(f:S_1\rightarrow S_2\) telle que:
les sommets \(s\) et \(t\) sont adjacents dans \(G_1\) (c’est-à-dire \(\{s,t\}\in A_1\)) si et seulement si \(f(s)\) et \(f(t)\) sont adjacents dans \(G_2\) (c’est-à-dire \(\{f(s),f(t)\}\in A_2\)).
Lorsque deux graphes sont isomorphes, ceci veut dire que ces deux graphes représentent en fait exactement le même graphe, qu’on a peut-être décrit différemment. En particulier, deux graphes isomorphes ont exactement les mêmes propriétés. De même, les sommets correspondants ont également les mêmes propriétés.
Pour tout sommet \(s\) de \(G_1,\) alors \(V\bigl(f(s)\bigr)=\bigl\{f(t) ~|~ t\in V(s)\bigr\}\text{.}\) En particulier, on a \(\deg(s)=\deg\left(f(s)\right)\text{.}\)
Il existe une coloration à \(n\) couleurs de \(G_1\) si et seulement si il existe une coloration à \(n\) couleurs de \(G_2\text{.}\) En particulier \(\chi(G_1)=\chi(G_2)\text{.}\)
La proposition 7.2.16 est surtout utile pour montrer que deux graphes ne sont pas isomorphes. En effet, si deux graphes sont tels que toutes les conclusions de la proposition précédente sont satisfaites, cela ne garantit par que les graphes seront isomorphes (ce n’est pas un si et seulement si). Cependant, si l’une de ces conclusions ne pas satisfaites, on sait que les graphes ne sont pas isomorphes!
On peut montrer que les deux graphes ci-dessous ne sont pas isomorphes, car il existe une coloration à deux couleurs pour le graphe \(G,\) mais il faut au moins trois couleurs pour une coloration de \(H\text{.}\)
Il, reste à vérifier que \(f\) fait correspondre les arêtes de \(G\) aux arêtes de \(H\text{.}\) On peut le faire en listant toutes les arêtes de \(\{x_1, ,x_2\}\) de \(G\) et toutes les arêtes \(\{y_1, y_2\}\) de \(H\text{,}\) et vérifier que \(\{f(x_1), f(x_2)\}=\{y_1, y_2\}\text{.}\)
Bien que cette méthode fonctionne, elle est un peu longue à écrire. À la place, on propose la démarche suivante. On trouve la matrice d’adjacence \(M_G\) de \(G\) selon l’ordre \(s_1, s_2, s_3, s_4, s_5 \text{.}\) On fait la même chose pour \(H\text{,}\) mais au lieu de trouver la matrice d’adjacence \(M_H\) de \(H\) selon l’ordre habituel \(t_1, t_2, t_3, t_4, t_5 \text{,}\) on prend la matrice d’adjacence selon l’ordre \(f(s_1), f(s_2), f(s_3), f(s_4), f(s_5) \text{,}\) c’est-à-dire selon l’ordre \(t_4, t_5, t_1, t_3, t_2 \text{.}\)
Encore une fois, on va trouver les matrices d’adjacence \(M_G\) et de \(M_H\text{.}\) Pour \(G\text{,}\) on prend l’ordre \(a,b, c, d, e, f\text{,}\) alors qu’on prend l’ordre \(g(a), g(b), g(c), g(d), g(e), g(f)\text{,}\) c’est-à-dire l’ordre \(s_2, s_6, s_4, s_3, s_5, s_1\text{.}\) On obtient
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
On peut voir que le fait d’être isomorphe est une relation entre les différents graphes. On veut montrer que cette relation satisfait certaines propriétés. Une relation ayant les propriétés ci-dessous est appelée une relation d’Équivalence.
S’il existe un isomorphisme \(f:S_1\rightarrow S_2\) du graphe \(G_1=(S_1,A_1)\) vers le graphe \(G_2=(S_2,A_2)\text{,}\) alors il existe un isomorphisme \(g:S_2 \rightarrow S_1\) du graphe \(G_2\) vers le graphe \(G_1\text{.}\)
Il suffit de poser \(g=f^{-1}\text{.}\) En effet, puisque \(f\) est une fonction bijective, \(f_{-1}:S_2\rightarrow S_1\) existe et est également une fonction bijective.
Il reste à vérifier que \(g\) est bien un isomorphisme de graphe, c’est-à-dire que soit \(t_1, t_2\in S_2 \text{,}\) alors \(\{t_1,t_2\}\in A_2\) si et seulement si \(\{f^{-1}(t_1),f^{-1}(t_2)\}\in A_1\text{.}\) Puisque \(f\) est surjective, on peut poser \(t_1=f(s_1)\) et \(t_2=f(s_2)\) pour \(s_1, s_2 \in S_1\text{.}\) Ainsi, on a également \(s_1=f^{-1}(t_1)\) et \(s_2=f^{-1}(t_2).\)
Par ce qui précède, l’énoncé “\(\{t_1,t_2\}\in A_2\) si et seulement si \(\{f^{-1}(t_1),f^{-1}(t_2)\}\in A_1\)” devient “\(\{f(s_1),f(s_2)\}\in A_2\) si et seulement si \(\{s_1,s_2\}\in A_1\)”, ce qui est vrai, car \(f\) est un isomorphisme.
Soit \(G_1=(S_1,A_1)\text{,}\)\(G_2=(S_2,A_2)\) et \(G_3=(S_3,A_3)\) trois graphes simples tels que \(G_1\cong G_2\) et \(G_2\cong G_3\text{.}\) Montrer que \(\text{.}\)
Soit \(f:S_1\rightarrow S_2\) un isomorphisme entre \(G_1\) et \(G_2\text{,}\) et soit \(g:S_2\rightarrow S_3\) un isomorphisme entre \(G_2\) et \(G_3\text{.}\) On pose \(h=f\circ g:S_1\rightarrow S_3\text{.}\) Par la définition de \(f\) et \(g\text{,}\) on vérifie facilement qu’il s’agit d’un isomorphisme.
On considère \(C_n=(S,A)\) le graphe cyclique à \(n\) sommets, disons \(S=\{s_1, s_2, \dots s_n\}\text{.}\) Par l’exercice 7.2.3.1.a, on sait qu’il existe au moins un isomorphisme \(f:S\rightarrow S\text{.}\) Cependant, il pourrait y en avoir plus. Parmi toutes les \(n!\) bijections de \(S\) vers \(S\text{,}\) combien d’entres elles sont des isomorphismes de graphes? Autrement dit, combien d’isomorphisme différent existe-t-il allant de \(C_n\) vers \(C_n\text{.}\)
