Graphiques non orientés avec choix

Question

Je dois faire un algorithme en utilisant deux graphes non orientés G1 = (V1, E1) et G2 = (V2, E2) en utilisant la règle que le nombre de V1 = V2 et E1 = E2. La question est que les graphiques G1 et G2 sont isomorphes? Je dois prouver que l'utilisation d'un algorithme (avec choix)

J'ai prouvé que les graphes étaient isomorphes mais comment prouver l'implémentation d'un algorithme?

Answer 1

Deux graphes isomorphes ont le même nombre de sommets et de bords, mais ce n'est pas suffisant. De plus, ils doivent avoir la même séquence de degrés et il devrait aussi y avoir une série d'opérations de matrice élémentaires telles que vous pouvez convertir la matrice d'adjacence de l'une à l'autre. Voir this link pour un algorithme détaillé et une discussion approfondie.