Un algo poly pour l'isomorphisme de graphes
Je vous propose cet algo en Maple qui me semble correct et polynomial.
C'est un algo de test destiné à ceux qui connaissent Maple ou qui veulent connaitre.
C'est un algo de test destiné à ceux qui connaissent Maple ou qui veulent connaitre.
restart;
with(GraphTheory):
graf:=proc() local g,i,j;global N;
g:={};
for i to N do for j from i+1 to N do
if rand() mod 2=0 then g:=g union {{i,j}};fi;
od;od;
g;
end:
arc:=proc(x,y) global G;
member({x,y},G);
end:
dst:=proc() local x,y,z,ok;global G,N,DST;
for x to N do for y to N do DST[x,y]:=infinity;od;od;
for x to N do DST[x,x]:=0;od;
ok:=true;
while ok do
ok:=false;
for x to N do for y to N do for z to N do if arc(y,z) and (DST[x,z]>DST[x,y]+1) then
ok:=true;DST[x,z]:=DST[x,y]+1;
fi;od;od;od;
od;
end:
v:=proc(x,y) local z,k,l;global T,DST;
l:=[];
for z to N do if arc(y,z) and (DST[x,z]=DST[x,y]+1) then l:=[op(l),v(x,z)];fi;od;
l:=sort(l);
if member(l,T,'k') then else T:=[op(T),l];k:=nops(T);fi;
k;end:
lst:=proc(g) local l,x;global G,N;
G:=g;dst();
l:=[];
for x to N do l:=[op(l),v(x,x)];od;
sort(l);
end:
nb:=0;nb0:=0;nb1:=0;
do
N:=rand() mod 5;N:=N+5;
G0:=graf();
G1:=graf();
ok:=IsIsomorphic(Graph(G0),Graph(G1));
T:=[];
A:=lst(G0);
B:=lst(G1);
ko:=evalb(A=B);
if ok<>ko then print(G0,G1,ok,ko);a:=0;1/a;fi;
nb:=nb+1;
if not ok then nb0:=nb0+1 else nb1:=nb1+1;fi;
if nb mod 1000=0 then print(nb,nb0,nb1);fi;
od:
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Pas de contre exemple et la complexité est clairement polynomiale.
Je lance le challenge de trouver un exemple qui foire.
dst calcule les distances DST minimales entre les sommets
v calcule par récurrence une valeur de typage
lst calcule la liste de ces types.
Elle calcule récursivement un numéro de typage d'un sommet en fonction de l'arborescence autour de ce sommet. Le type est la position dans une liste globale de listes de types qui sera commune pour les deux graphes. Donc un même typage se retrouvera pour le second graphe de la même manière. J'utilise des tris de listes avec $sort$ pour être justement "à isomorphisme près".
Le fait d'utiliser une variable globale dont le nom est, à la casse près, similaire à celui d'une des procédures employées est certainement voulu pour la lisibilité du code.
Quel est le degré de la complexité ?
Merci d'avance et à bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
La complexité de l'algo est grosso modo en $O(N^3)$ à vue de nez. En tout cas polynomiale (ce qui répondrait à une célèbre conjecture).
dst est déjà clairement au moins en $O(N^2)$, il y a aussi le While dont je n'ai pas tenu compte.
La valuation rajoute encore N calculs de dst, au moins.
Et cette valuation est elle même utilisée au moins N fois par lst.
Je ne sais pas comment vous estimez globalement du $O(N^3)$.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Ok...peut-être en $O(N^4)$....no matter.
Même si c'est en $O(N^8)$ c'est polynomial et ce serait TOP !
Mais par expérience, je reste sur du $O(N^3)$.
Pourrais-tu donner un exemple de graphe et des exemples de "valuations" renvoyées par ta fonction ?
De toute façon, même si ton algorithme est correct, je doute fortement qu'il soit polynomial, justement à cause du caractère fortement récursif de ta fonction $v$. En gros, avec un graphe à plein de sommets, chaque sommets ayant plein d'arêtes, le nombre d'appels de la fonction $v$ explose !
J'ai l'impression que pour connaître le type d'une arête, tu es obligé de connaître le type de beaucoup d'autres...
Il y a peut-être moyen de retirer la récursivité en calculant les "types" dans le bon ordre... mais ça ne saute pas aux yeux.
Je pense que si tu refais des tests en augmentant la probabilité d'avoir des arêtes entre deux sommets, tu va avoir des soucis.
restart; with(GraphTheory): graf:=proc() local g,i,j;global N; g:={}; for i to N do for j from i+1 to N do if rand() mod 2=0 then g:=g union {{i,j}};fi; od;od; g; end: arc:=proc(x,y) global G; member({x,y},G); end: v:=proc(x,y) local z,k,L;global G,T; L:=[ ]; for z to N do if arc(y,z) and (Distance(GG,x,z)=Distance(GG,x,y)+1) then L:=[op(L),v(x,z)];fi;od; L:=sort(L); if member(L,T,'k') then else T:=[op(T),L];k:=nops(T);fi; k;end: lst:=proc(g) local l,x;global G,GG,N; G:=g;GG:=Graph(g); l:=[]; for x to N do l:=[op(l),v(x,x)];od; sort(l); end: nb:=0;nb0:=0;nb1:=0; do N:=rand() mod 5;N:=N+5; G0:=graf(); G1:=graf(); ok:=IsIsomorphic(Graph(G0),Graph(G1)); T:=[ ]; A:=lst(G0); B:=lst(G1); ko:=evalb(A=B); if ok<>ko then print(G0,G1,ok,ko);a:=0;1/a;fi; nb:=nb+1; if not ok then nb0:=nb0+1 else nb1:=nb1+1;fi; if nb mod 1000=0 then print(nb,nb0,nb1);fi; od:mais c'est plus lent......
On peut aussi enregistrer les valeurs déjà calculées pour ne pas les recalculer deux fois. Ce sera donc quadratique.
Voici comment :
v:=proc(x,y) local z,k,l;global T,DST,V; if type(V[x,y],numeric) then k:=V[x,y] else l:=[]; for z to N do if arc(y,z) and (DST[x,z]=DST[x,y]+1) then l:=[op(l),v(x,z)];fi;od; l:=sort(l); if member(l,T,'k') then else T:=[op(T),l];k:=nops(T);fi; V[x,y]:=k; fi; k;end: lst:=proc(g) local l,x;global G,N,V; G:=g;dst();unassign('V'); l:=[]; for x to N do l:=[op(l),v(x,x)];od; sort(l); end:g:={{1,2},{1,3}}; en partant de la liste vide T=[ ] lst(g) donne [2, 4, 4] la décomposition du calcul en x,y ----> v(x,y) et la liste globale T 1, 2, ---->, 1, [[]] 1, 3, ---->, 1, [[]] 1, 1, ---->, 2, [[], [1, 1]] 2, 3, ---->, 1, [[], [1, 1]] 2, 1, ---->, 3, [[], [1, 1], [1]] 2, 2, ---->, 4, [[], [1, 1], [1], [3]] 3, 2, ---->, 1, [[], [1, 1], [1], [3]] 3, 1, ---->, 3, [[], [1, 1], [1], [3]] 3, 3, ---->, 4, [[], [1, 1], [1], [3]]ensuite pour un autre graphe (en partant de la même liste $T$)
g:={{1,2},{2,3}}; lst(g) donne [4, 2, 4] qui triée donne encore [2, 4, 4].....donc les deux graphes sont déclarés isomorphes. la décomposition du calcul en x,y ----> v(x,y) et la table globale T 1, 3, "---->", 1, [[], [1, 1], [1], [3]] 1, 2, "---->", 3, [[], [1, 1], [1], [3]] 1, 1, "---->", 4, [[], [1, 1], [1], [3]] 2, 1, "---->", 1, [[], [1, 1], [1], [3]] 2, 3, "---->", 1, [[], [1, 1], [1], [3]] 2, 2, "---->", 2, [[], [1, 1], [1], [3]] 3, 1, "---->", 1, [[], [1, 1], [1], [3]] 3, 2, "---->", 3, [[], [1, 1], [1], [3]] 3, 3, "---->", 4, [[], [1, 1], [1], [3]]Évidemment, si tu compares au calcul de la distance au cas par cas, sans mémoïsation, c'est bien plus lent !
Pour ta fonction $v$, tu devrais sans doute la mémoïser également puisque tu dis que tu te sers des valeurs déjà calculées... mais tant que tu ne mettras pas des mots sur ce que tu fais, même si ça marche vraiment, tu ne convaincras pas grand monde.
[Edit après la réponse ci-dessous] : Je n'avais effectivement pas vu la mémoïsation de $v$ par $V$ deux messages plus haut.
g:={{1,2},{2,3},{3,4},{4,5},{5,1}};N:=5;T:=[ ]; 1, 3, "---->", 1, [[]] 1, 2, "---->", 2, [[], [1]] 1, 4, "---->", 1, [[], [1]] 1, 5, "---->", 2, [[], [1]] 1, 1, "---->", 3, [[], [1], [2, 2]] 2, 5, "---->", 1, [[], [1], [2, 2]] 2, 1, "---->", 2, [[], [1], [2, 2]] 2, 4, "---->", 1, [[], [1], [2, 2]] 2, 3, "---->", 2, [[], [1], [2, 2]] 2, 2, "---->", 3, [[], [1], [2, 2]] 3, 1, "---->", 1, [[], [1], [2, 2]] 3, 2, "---->", 2, [[], [1], [2, 2]] 3, 5, "---->", 1, [[], [1], [2, 2]] 3, 4, "---->", 2, [[], [1], [2, 2]] 3, 3, "---->", 3, [[], [1], [2, 2]] 4, 2, "---->", 1, [[], [1], [2, 2]] 4, 3, "---->", 2, [[], [1], [2, 2]] 4, 1, "---->", 1, [[], [1], [2, 2]] 4, 5, "---->", 2, [[], [1], [2, 2]] 4, 4, "---->", 3, [[], [1], [2, 2]] 5, 2, "---->", 1, [[], [1], [2, 2]] 5, 1, "---->", 2, [[], [1], [2, 2]] 5, 3, "---->", 1, [[], [1], [2, 2]] 5, 4, "---->", 2, [[], [1], [2, 2]] 5, 5, "---->", 3, [[], [1], [2, 2]] lst=[3, 3, 3, 3, 3]Soit je me suis trompé en traduisant ton code (ce que je n'exclus pas, car il est loin d'être simple à traduire à cause des nombreuses variables globales), soit ton algorithme ne fonctionne pas.
Les graphes à 6 sommets numérotés de 0 à 5 dont les arêtes sont respectivement :
[(0, 1), (0, 3), (0, 4), (0, 5), (1, 4), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
et :
[(0, 1), (0, 4), (0, 5), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5)]
renvoient le même résultat [2,3,4,4,5,6] par la fonction "lst"... et pourtant ils sont clairement non isomorphes puisque ils n'ont même pas le même nombre d'arêtes !
Trouves-tu la même chose ?
et mon algo dit clairement NON isomorphes.
tu as dû te planter en codant en Python.
g := {{1, 2}, {1, 4}, {1, 5}, {1, 6}, {2, 5}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}} N := 6 T := [] lst(g);T; [3, 6, 7, 8, 8, 9] [[], [1], [1, 2, 2, 2], [1, 1], [1, 1, 1], [4, 5], [2, 2, 4], [1, 1, 2, 2], [1, 1, 1, 1, 1]]Le second graphe n'a vraiment rien à voir avec le premier :
g := {{1, 2}, {1, 5}, {1, 6}, {2, 5}, {3, 4}, {4, 5}, {4, 6}, {5, 6}} lst(g);T; [11, 13, 15, 16, 17, 18] [[], [1], [1, 2, 2, 2], [1, 1], [1, 1, 1], [4, 5], [2, 2, 4], [1, 1, 2, 2], [1, 1, 1, 1, 1], [2], [1, 10, 10], [1, 2], [2, 12], [2, 4], [14], [1, 2, 4], [1, 1, 1, 2], [2, 2, 2]]tu n'aurais pas "oublié" de faire un reset de la variable globale $V$ de mémoïsation entre les deux calculs par hasard ?
Tu connais assez Maple pour bien traduire ?
par exemple
J'arrive à la même chose que toi pour le cycle de 5 et le graphe {(1,2),(1,3)}... mais je n'ai pas compris pourquoi tu repars de la même table T pour le graphe {(1,2),(2,3)}.
Je pensais en gros que tu calculais un invariant d'isomorphisme (à savoir ta liste "lst(G)"), qui était intrinsèque au graphe G, et que comparer ces invariants permettait de conclure...
Mais apparemment, c'est plus subtil que ça : il faut prendre la même table T pour les deux graphes pour que ça fonctionne.
Voici mon code en Python :
## Importations import networkx as nx # Bibliothèque pour gérer les graphes import matplotlib.pyplot as plt # Bibliothèque d'affichage graphique ## Graphes exemples G0 = nx.Graph() G0.add_edges_from([(1,2), (1,3)]) G1 = nx.Graph() G1.add_edges_from([(1,2), (2,3)]) G2 = nx.Graph() G2.add_edges_from([(1,2), (2,3), (3,4), (4,5), (5,1)]) ## Code def graf(N, p): """Crée au hasard un graphe à N sommets avec une probabilité p de créer une arête entre deux sommets.""" return nx.gnp_random_graph(N, p) def dst(G): """Calcule un tableau des distances deux à deux entre les sommets du graphe G. Renvoie le résultat sous la forme d'un dictionnaire indexé par les couples de sommets du graphe.""" N = len(G) # nombre de sommets du graphe DST = {(x,y) : N+2 for x in G for y in G} # N+2 remplace l'infini for x in G: DST[(x,x)] = 0 modif = True while modif: modif = False for x in G: for y in G: for z in G[y]: if DST[(x,z)] > DST[(x,y)] + 1: modif = True DST[(x,z)] = DST[(x,y)] + 1 return DST def lst(G, verbose=False): """Calcule et renvoie une liste des 'valuations' des couples (x,x) de sommets. La fonction 'valuation' est définie pour chaque graphe et retiens les valeurs déjà calculées dans le dictionnaire V.""" DST = dst(G) T = [] V = {} def v(x, y, verbose=False): """Renvoie une 'valuation' du couple de sommets (x,y) du graphe G""" if (x, y) in V: return V[(x, y)] l = [] for z in G[y]: # on parcourt les voisins de y if DST[(x,z)] == DST[(x,y)] + 1: l.append(v(x, z, verbose)) # on trie l et on la fige pour pouvoir la comparer à d'autres l = tuple(sorted(l)) for k, a in enumerate(T,1): if l == a: if verbose: print((x,y), "-->", k, T) return k T.append(l) if verbose: print((x,y), "-->", len(T), T) return len(T) return tuple(sorted([v(x, x, verbose) for x in G]))Je vais modifier légèrement pour voir si j'obtiens les mêmes résultats que toi en conservant le même T.
En attendant, en modifiant un tout petit peu ce qui est ci-dessus, remplaçant :
def lst(G, verbose=False): """Calcule et renvoie une liste des 'valuations' des couples (x,x) de sommets. La fonction 'valuation' est définie pour chaque graphe et retiens les valeurs déjà calculées dans le dictionnaire V.""" DST = dst(G) T = []pardef lst(G, verbose=False, T=None): """Calcule et renvoie une liste des 'valuations' des couples (x,x) de sommets. La fonction 'valuation' est définie pour chaque graphe et retiens les valeurs déjà calculées dans le dictionnaire V.""" DST = dst(G) if T is None: T = []j'obtiens (enfin) exactement les mêmes résultats, en comparant les graphes que j'ai nommés G0 et G1 ci-dessus.Si on change l'ordre des graphes G1 et G0, mais en initialisant T=[] avant le test et en gardant le même T entre les deux graphes, les listes "lst(G1)" et "lst(G0)" changent, mais elles restent égales entre elles.
Cela donne donc un test en apparence symétrique, même si je ne comprends pas bien pourquoi.
Il reste à savoir si c'est fiable, à expliquer pourquoi ça marche, et à justifier le caractère polynomial.
J'ai quand même vu un point qu'il faut préciser. Je l'ai programmé. Il s'agit de voir aussi en largeur, pas seulement en profondeur.
Ce n'est peut-être pas nécessaire mais pour une preuve, c'est plus clair.
Mes précédents "faux positifs" étaient dus à deux erreurs dans la copie du code :
1) j'avais fait une erreur bête dans le calcul des distances, parcourant les voisins de x au lieu de ceux de y.
2) je numérotais les valeurs de la liste T à partir de 0 au lieu de numéroter à partir de 1 comme le fait Maple, et du coup dans le cas où je rajoutais un élément à la liste T, je faisais un décalage d'indice.
Maintenant que c'est réparé, je n'ai plus ces problèmes-là.
J'ai à peu près compris ce que fait la fonction "v", mais j'avoue avoir encore du mal à mettre des mots classiques dessus.
Il semble y avoir une sorte de parcours (en largeur, en profondeur ?) et une façon de "coder" ce parcours... mais je n'ai pas bien compris le codage.
$v(x,x)$ est défini par les $v(x,y)$ où $y$ est dans un disque de rayon $1$ autour de $x$ qui sont eux-mêmes définis par les $v(x,z)$ accessibles et $z$ à distance $2$ etc....On regarde la structure à isomorphisme près. En gros, ce que peut "visualiser" $x$ autour de lui, indépendamment du nom et de l'ordre des sommets....bref, à isomorphisme près.
Ce qu'il reste à faire c'est montrer :
- si deux graphes sont isomorphes alors le test renvoie True
- si le test renvoie True alors les deux graphes sont isomorphes
- l'algorithme s'exécute en temps polynomial du nombre de sommets des graphes.
De ces 3 points, c'est probablement le 3ème le plus simple à justifier.
Ensuite, le 1er devrait pouvoir se prouver en mathématisant l'algorithme.
En revanche, je n'ai aucune idée de comment on pourrait prouver le 2ème !
Pour faire une preuve, je vais proposer une autre méthode similaire et plus combinatoire et globale. Il s'agit de donner une valuation des graphes en supprimant des sommets.
Les tests vont beaucoup plus vite...mais ce n'est pas forcément moins complexe (en temps au pire des cas).
genl:=proc(g,x) local a,h; h:={}; for a in g do if not member(x,a) then h:=h union {a};fi;od; h;end:l'ensemble des sommets d'un graphe
som:=proc(g) local a,s; s:={};for a in g do s:=s union a;od; s;end:la valuation d'un graphe
v:=proc(g) local k,l,x,s,n;global T,V; if g={} then k:=0 elif type(V[g],numeric) then k:=V[g] else s:=som(g); n:=max(s); l:=[]; for x in s do l:=[op(l),v(subs(n=x,genl(g,x)))];od; l:=sort(l); if member(l,T,'k') then else T:=[op(T),l];k:=nops(T);fi; fi; V[g]:=k; k;end:corps principal :
nb:=0;nb0:=0;nb1:=0; do N:=7; G0:=graf(); G1:=graf(); ok:=IsIsomorphic(Graph(G0),Graph(G1)); T:=[]; unassign('V'); A:=v(G0); B:=v(G1); ko:=evalb(A=B); if ok<>ko then print(G0,G1,ok,ko);a:=0;1/a;fi; nb:=nb+1; if not ok then nb0:=nb0+1 else nb1:=nb1+1;fi; if nb mod 1000=0 then print(nb,nb0,nb1);fi; od:Je ne comprends pas ce que tu substitues et pourquoi.
L'idée n'est-elle pas de supprimer les sommets l'un après l'autre ? Dans ce cas, pourquoi remplacer quoi que ce soit dans ton sous-graphe ?
Si ton idée fonctionne, elle est bien plus simple à comprendre et à mettre en oeuvre (en particulier en Python).
On remplace donc les $n$ par $x$ dans le graphe où on a enlevé les $x$.
Mais ce n'est en effet pas nécessaire de le faire. On peut se contenter de faire
Pour calculer la valuation d'un graphe à N sommets, on doit connaitre les N valuations de N sous-graphes à N-1 sommets...
On obtient au mieux quelque chose en $O(N!)$.
Après, je suis d'accord que cet algo est plus simple à comprendre et risque de ne plus être polynomial. Je suis convaincu que la version initiale est polynomiale...pas pour celle-ci.
Je propose celle-ci pour la pédagogie et pour aiguiller vers des preuves.
Voici comment avec une fonction $dst(x,y,g)$ qui donne la distance dans le graphe $g$ entre deux sommets $x,y$.
bord:=proc(x,d,g) local a,h; h:={}; for a in g do if (dst(x,a[1],g)=d) and (dst(x,a[2],g)=d) then h:=h union {a};fi;od; h;end: v:=proc(x,y,g) local z,k,l;global T,V; if g={} then k:=0 elif type(V[x,y,g],numeric) then k:=V[x,y,g] else l:=[[v(y,y,bord(x,dst(x,y,g),g))]]; for z to N do if arc(y,z,g) and (dst(x,z,g)=dst(x,y,g)+1) then l:=[op(l),v(x,z,g)];fi;od; l:=sort(l); if member(l,T,'k') then else T:=[op(T),l];k:=nops(T);fi; V[x,y,g]:=k; fi; k;end:Tu me corrigeras si je me trompe.
L'idée est d'obtenir une représentation chiffrée de la structure du graphe $G$.
Pour cela, pour chaque sommet $s$ du graphe $G$, on cherche à donner un "type" à l'arbre enraciné en ce sommet $s$ et construit sur le graphe en le parcourant en profondeur depuis ce sommet.
Le type est défini récursivement sur les sous-arbres issus de chaque noeud.
On enregistre les différents types déjà rencontrés dans une liste notée $T$.
Le type d'une feuille est vide [] et on adjoint ce type à la liste $T$. On lui attribue également la valeur 1 puisque ce type [] sera le premier de la liste $T$.
Le type d'un autre noeud est la liste triée des valeurs des types de ses fils. La valeur de ce type est alors sa place dans la liste $T$ des types. Si ce type n'est pas encore dans la liste, on le rajoute, ce qui lui attribue une valeur.
Enfin, on calcule un "archétype" du graphe en établissant la liste des valeurs des types de chaque arbre enraciné en chacun des sommets et en renvoyant cette liste triée dans l'ordre croissant.
Il s'agit donc bien d'une heuristique ?
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-- Schnoebelen, Philippe
Pour la définition d'heuristique, c'est bien la bonne.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
Si on se restreint à l'ensemble des graphes dont le degré maximal est inférieur ou égal à $k$ alors l'algorithme proposé est polynomial, avec un exposant proportionnel à $k\log(k)$.
Réf : E. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences, 25:42-65, 1982.
Est-ce à dire que depuis près de 40 ans il n'y a plus eu d'améliorations sur le sujet ?
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
C'est donc un sujet encore féroce dynamique.
J'aime bien aussi le paragraphe sur le testeur d'algorithme probabiliste polynomial.
À bientôt.
Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.