Polynomial algorithm for isomorphic graphs, all cases
| Autor: | Mimouni, Mohamed |
|---|---|
| Přispěvatelé: | École Nationale d’Ingénieurs de Monastir (ENIM) |
| Jazyk: | francouzština |
| Rok vydání: | 2020 |
| Předmět: |
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
automorphism hypergraphes isomorphes isomorphic hypergraphs hypergraphes isomorphes 1 MOTS-CLES : graphes isomorphes graphes isomorphes automorphisme hypergraphs isomorphism MOTS-CLES : isomorphic graphs isomorphic graphs isomorphisme isomorphs 1 |
| Popis: | In this paper, I propose an algorithm capable of solving the problem of isomorphic graphs in polynomial time. First, I define a pseudo-tree that allows us to define for each vertex a label or a label. In the second place, I apply the pseudo-tree for the first graph and I calculate the labels of each vertex of the first graph, then I do the same thing for the second graph. Thirdly, for each vertex of graph 1, I look for the vertices of graph2 which have the same label, if at least a vertex of the first graph its label is not in the labels of the second graph we deduce that the two pseudo-trees are not isomorphic. In the other case I generate solutions and I check them in polynomial time ... This algorithm thus makes it possible for the isomorphic graphs to compute the image of each vertex in polynomial time.; Dans ce papier, je propose un algorithme capable de résoudre le problème de graphes isomorphes en temps polynomial. En premier lieu, je définis un pseudo-arbre qui nous permet de définir pour chaque sommet une étiquette ou un label. En second lieu, j'applique le pseudo-arbre pour le premier graphe puis je calcule les étiquette de chaque sommet de premier graphe, puis je fais la même chose pour le deuxième graphe. En troisième lieu je cherche pour chaque sommet de graphe 1 les sommets de graphe 2 qui ont le même étiquette, si ou moins un sommet de premier graphe son étiquette n'est pas dans les étiquette de deuxième graphe on déduit que les deux pseudo-arbres ne sont pas isomorphes. Dans l'autres cas je génère des solutions et je les vérifier en temps polynomiale... Cet algorithme permet donc pour les graphes isomorphes de calculer l'image de chaque sommet en temps polynomial |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|