Le graphe d'isomorphisme peut être décrit comme un graphe dans lequel un seul graphe peut avoir plusieurs formes. Cela signifie que deux graphiques différents peuvent avoir le même nombre d'arêtes, de sommets et la même connectivité d'arêtes. Ces types de graphiques sont appelés graphiques d'isomorphisme. L’exemple d’un graphe d’isomorphisme est décrit comme suit :
Le graphique ci-dessus contient les éléments suivants :
- Le même graphique est représenté sous plusieurs formes.
- On peut donc dire que ces graphes sont des graphes d’isomorphisme.
Conditions d'isomorphisme des graphes
Deux graphiques quelconques seront appelés isomorphisme s'ils satisfont aux quatre conditions suivantes :
- Il y aura un nombre égal de sommets dans les graphiques donnés.
- Il y aura un nombre égal d’arêtes dans les graphiques donnés.
- Il y aura une quantité égale de séquences de degrés dans les graphiques donnés.
- Si le premier graphe forme un cycle de longueur k à l'aide des sommets {v1, v2, v3,…. vk}, alors un autre graphe doit aussi former le même cycle de même longueur k à l'aide des sommets {v1, v2, v3, …. vk}.
Remarque : La séquence de degrés d'un graphique peut être décrite comme une séquence de degrés de tous les sommets par ordre croissant.
Les points importants
- Pour que deux graphes soient un isomorphisme, les conditions nécessaires sont les quatre conditions définies ci-dessus.
- Il n’est pas nécessaire que les conditions définies ci-dessus soient suffisantes pour montrer que les graphiques donnés sont isomorphes.
- Si deux graphes satisfont aux quatre conditions définies ci-dessus, même dans ce cas, il n'est pas nécessaire que les graphes soient sûrement isomorphes.
- Si le graphique ne satisfait aucune condition, alors nous pouvons dire que les graphiques ne sont sûrement pas un isomorphisme.
Conditions suffisantes pour l'isomorphisme du graphique
Si nous voulons prouver que deux graphes quelconques sont un isomorphisme, il existe des conditions suffisantes que nous fournirons pour garantir que les deux graphes sont sûrement un isomorphisme. Lorsque les deux graphiques auront réussi à effacer les quatre conditions ci-dessus, nous vérifierons alors ces graphiques selon des conditions suffisantes, qui sont décrites comme suit :
- Si les graphes complémentaires des deux graphes sont des isomorphismes, alors ces graphes seront sûrement un isomorphisme.
- Si les matrices adjacentes des deux graphiques sont les mêmes, alors ces graphiques seront un isomorphisme.
- Si les graphiques correspondants de deux graphiques sont obtenus en supprimant certains sommets d'un graphique et que leurs images correspondantes dans d'autres images sont un isomorphisme, alors seulement ces graphiques ne seront pas un isomorphisme.
Lorsque deux graphiques satisfont à l’une des conditions ci-dessus, alors nous pouvons dire que ces graphiques sont sûrement un isomorphisme.
Exemples d'isomorphisme de graphe
Il existe de nombreux exemples d'isomorphisme de graphes, qui sont décrits comme suit :
Exemple 1:
Dans cet exemple, nous avons montré si les graphiques suivants sont des isomorphismes.
Solution: Pour cela, nous vérifierons les quatre conditions de l’isomorphisme des graphes, qui sont décrites comme suit :
Condition 1 :
- Dans le graphique 1, il y a un total de 4 sommets, c'est-à-dire G1 = 4.
- Dans le graphique 2, il y a un total de 4 sommets, c'est-à-dire G2 = 4.
Ici,
Il y a un nombre égal de sommets dans les graphes G1 et G2. Ces graphiques satisfont donc à la condition 1. Nous allons maintenant vérifier la deuxième condition.
Condition 2 :
- Dans le graphique 1, il y a un total de 5 arêtes, c'est-à-dire G1 = 5.
- Dans le graphique 2, il y a un total de 6 arêtes, c'est-à-dire G2 = 6.
Ici,
Il n’y a pas un nombre égal d’arêtes dans les graphiques G1 et G2. Ces graphiques ne satisfont donc pas à la condition 2. Nous ne pouvons désormais pas vérifier toutes les conditions restantes.
Puisque ces graphiques violent la condition 2. Ces graphiques ne sont donc pas un isomorphisme.
∴ Les graphiques G1 et G2 ne sont pas des graphiques d'isomorphisme.
Exemple 2 :
Dans cet exemple, nous avons montré si les graphiques suivants sont des isomorphismes.
Solution: Pour cela, nous vérifierons les quatre conditions de l’isomorphisme des graphes, qui sont décrites comme suit :
Condition 1 :
- Dans le graphique 1, il y a un total de 4 sommets, c'est-à-dire G1 = 4.
- Dans le graphique 2, il y a un total de 4 sommets, c'est-à-dire G2 = 4.
- Dans le graphique 3, il y a un total de 4 sommets, c'est-à-dire G3 = 4.
Ici,
Il y a un nombre égal de sommets dans tous les graphes G1, G2 et G3. Ces graphiques satisfont donc à la condition 1. Nous allons maintenant vérifier la deuxième condition.
Condition 2 :
- Dans le graphique 1, il y a un total de 5 arêtes, c'est-à-dire G1 = 5.
- Dans le graphique 2, il y a un total de 5 arêtes, c'est-à-dire G2 = 5.
- Dans le graphique 3, il y a un total de 4 arêtes, c'est-à-dire G2 = 4.
Ici,
- Il y a un nombre égal d’arêtes dans les graphes G1 et G2. Ces graphiques satisfont donc à la condition 2.
- Mais il n’y a pas le même nombre d’arêtes dans les graphes (G1, G2) et G3. Les graphes (G1, G2) et G3 ne satisfont donc pas à la condition 2.
Puisque les graphes (G1, G2) et G3 violent la condition 2. On peut donc dire que ces graphes ne sont pas un isomorphisme.
∴ Le graphe G3 n'est ni un isomorphisme avec le graphe G1 ni avec le graphe G2.
Puisque les graphes G1 et G2 satisfont à la condition 2. On peut donc dire que ces graphes peuvent être un isomorphisme.
∴ Les graphiques G1 et G2 peuvent être un isomorphisme.
Nous allons maintenant vérifier la troisième condition pour les graphiques G1 et G2.
Condition 3 :
- Dans le graphe 1, le degré de la séquence s est {2, 2, 3, 3}, c'est-à-dire G1 = {2, 2, 3, 3}.
- Dans le graphe 2, le degré de la séquence s est {2, 2, 3, 3}, c'est-à-dire G2 = {2, 2, 3, 3}.
Ici
Il y a un nombre égal de séquences de degrés dans les graphiques G1 et G2. Ces graphiques satisfont donc à la condition 3. Nous allons maintenant vérifier la quatrième condition.
Condition 4 :
est égal à une chaîne en Java
Le graphe G1 forme un cycle de longueur 3 à l'aide des sommets {2, 3, 3}.
Le graphe G2 forme également un cycle de longueur 3 à l'aide des sommets {2, 3, 3}.
Ici,
Cela montre que les deux graphiques contiennent le même cycle car les deux graphiques G1 et G2 forment un cycle de longueur 3 à l'aide des sommets {2, 3, 3}. Ces graphiques satisfont donc à la condition 4.
Ainsi,
- Les graphiques G1 et G2 satisfont aux quatre conditions nécessaires ci-dessus.
- Donc G1 et G2 peuvent être un isomorphisme.
Nous allons maintenant vérifier des conditions suffisantes pour montrer que les graphes G1 et G2 sont un isomorphisme.
Vérification des conditions suffisantes
Comme nous l’avons appris, si les graphes complémentaires des deux graphes sont des isomorphismes, les deux graphes seront sûrement un isomorphisme.
Nous allons donc tracer les graphes complémentaires de G1 et G2, qui sont décrits comme suit :
Dans les graphiques complémentaires ci-dessus de G1 et G2, nous pouvons voir que les deux graphiques sont des isomorphismes.
∴ Les graphiques G1 et G2 sont des isomorphismes.
Exemple 3 :
Dans cet exemple, nous avons montré si les graphiques suivants sont des isomorphismes.
Solution: Pour cela, nous vérifierons les quatre conditions de l’isomorphisme des graphes, qui sont décrites comme suit :
Condition 1 :
- Dans le graphique 1, il y a au total 8 sommets, c'est-à-dire G1 = 8.
- Dans le graphique 2, il y a au total 8 sommets, c'est-à-dire G2 = 8.
Ici,
Il y a un nombre égal de sommets dans les graphes G1 et G2. Ces graphiques satisfont donc à la condition 1. Nous allons maintenant vérifier la deuxième condition.
Condition 2 :
- Dans le graphique 1, le nombre total d’arêtes est de 10, c’est-à-dire G1 = 10.
- Dans le graphique 2, le nombre total d’arêtes est de 10, c’est-à-dire G2 = 10.
Ici,
Il y a un nombre égal d’arêtes dans les graphes G1 et G2. Ces graphiques satisfont donc à la condition 2. Nous allons maintenant vérifier la troisième condition.
Condition 3 :
- Dans le graphe 1, le degré de la séquence s est {2, 2, 2, 2, 3, 3, 3, 3}, c'est-à-dire G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- Dans le graphe 2, le degré de la séquence s est {2, 2, 2, 2, 3, 3, 3, 3}, c'est-à-dire G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Ici
Il y a un nombre égal de séquences de degrés dans les graphiques G1 et G2. Ces graphiques satisfont donc à la condition 3. Nous allons maintenant vérifier la quatrième condition.
Condition 4 :
- Le graphique G1 forme un cycle de longueur 4 à l'aide de sommets de degré 3.
- Le graphique G2 ne forme pas un cycle de longueur 4 à l'aide de sommets car les sommets ne sont pas adjacents.
Ici,
Les graphiques G1 et G2 ne forment pas le même cycle de même longueur. Ces graphiques violent donc la condition 4.
Puisque les graphiques G1 et G2 violent la condition 4. Donc en raison de la violation de la condition 4, ces graphiques ne seront pas un isomorphisme.
∴ Les graphiques G1 et G2 ne sont pas un isomorphisme.