Réponses
-
Je me demandais aussi si le polynôme minimal de la matrice d'adjacence est un invariant complet pour les graphes à isomorphisme près.
Quand les graphes n'ont pas de sommets isolés (ligne de la matrice faite de $0$) cela semble assez robu… -
C'est un invariant comme un autre. Ce n'est plus forcément une matrice d'adjacence d'un graphe simple. C'est tout.
Ce qui est clair c'est que deux graphes isomorphes auront la même matrice minimale. Ce qui n'est pas clair c'est s'ils ne … -
Cette forme normale obtenue par permutations indépendantes des lignes et colonnes est la plus petite possible dans l'ordre lexicographique.
Notons que ce n'est pas forcément la matrice d'un graphe. Il se peut que $M\not=M^t$ ou encore qu… -
Pour les amateurs d'heuristiques : j'ai testé une idée saugrenue qui m'est passée dans la tête. Rendre indépendantes les lignes et les colonnes de la matrice d'adjacence. Cela pourrait sembler n'avoir aucun sens...et pourtant....je n'ai aucun exempl…
-
Je ne pense pas que mon algo soit le même que celui de la section 2.3 comme le dit Bisam. Il est polynomial en $N$ quelque soit le degré des sommets. Il est peut-être incomplet comme je l'ai dit et j'ai complété avec l'idée des bords....mais est-il …
-
Je n'ai en effet pas compris puisque je ne connais que cette définition du mot heuristique dans le contexte des mathématiques :
Une heuristique est une méthode de calcul qui fournit r…
-
Non, c'est un algorithme déterministe. Ce n'est pas le problème. La question est d'obtenir une méthode polynomiale si c'est possible.
-
Un survey assez complet et bien rédigé.
-
oui très bien....juste un petit bémol.
en créant une liste TRIEE des VALEURS des différents types déjà rencontrés.
-
Comme je le disais dans un message précédent, il est peut-être nécessaire (pas sûr) de faire aussi une valuation sur les bords des disques autour du centre $x$ considéré.
Voici comment avec une fonction $dst(x,y,g)$ qui donne la distance… -
Cette complexité catastrophique serait obtenue sans la liste $T$ et la mémoïsation dans $V$ et aussi la substitution qui cherchent les structures à isomorphisme près. Dans les faits et en pratique, cela va plus vite.
Après, je suis d'acc… -
On a enlevé le sommet $x$ (c'est un nombre) du graphe. Il n'y apparait plus. Autant utiliser cette place libre pour y mettre le sommet d'indice maximal $n$.
On remplace donc les $n$ par $x$ dans le graphe où on a enlevé les $x$.on supprime un sommet d'un graphegenl:=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 graph…C'est exactement ça bisam.
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 …Dans la fonction $v$, on fait un parcours "autour" d'un centre $x$. C'est à la fois de la profondeur et de la largeur.
$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 p…Les $lst$ de $G0$ et $G1$ ne sont pas égales entre elles. Je t'ai donné les calculs qui montrent qu'ils sont NON isomorphes.En effet, toute la subtilité est d'utiliser la même table $T$ pour le deuxième graphe. Ses calculs vont être obligés de suivre à la trace ceux du premier graphe si c'est possible. Sinon, l'ordre des types pourraient varier par le choix de l'ordre de…Voici comment je définis la représentation binaire d'un nombre $n$ sur $N$ bits.....classique avec de la division entière en base 2.bin:=proc(n,N) local a,l; l:=[];a:=n;while nops(l)…
Par exemple avec $(5x+5y-2z)_3$Peux-tu mettre ici ton code Python que je regarde....c'est comme Pascal...non ?
Tu connais assez Maple pour bien traduire ?
par exemplemember(L,T,'k') retourn…
J'ai fait des millions de tests et pas que sur des petits graphes comme ceux que tu proposes.Oui....la partie entière ne suffit pas. D'où l'usage des bits qui la généralise.
Le $a\oplus b$ est simplement $(a+b)_1$déjà il faut numéroter les sommets de 1 à 6.
et mon algo dit clairement NON isomorphes.
tu as dû te planter en codant en Python.g := {{1, 2}, {1, 4}, {1, 5}, …Un autre exemple : un cycle de longueur $5$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,…J'ai en effet mémoïsé avec la table $V$. Je vois que tu piges au fur et à mesure....cela me suffit amplement de toucher une seule personne.Exemple de calcul :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, ---->…Non, la complexité de $v$ est très simple à voir. On utilise justement un ordre. On tourne autour du sommet $x$. La valeur de $v(x,x)$ dépend des valeurs de $v(x,y)$ avec $y$ à distance $1$ de $x$ qui dépendent des valeurs $v(x,z)$ avec $z$ à distan…Si vous n'aimez pas ma procédure DST, on peut utiliser celle de Maple.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 …oui....on peut utiliser l'algo de Dijkstra pour les distances....peu importe.
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)…DST c'est simplement la distance minimale classique entre les sommets.
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).L'essentiel est dans la fonction de valuation $v$.
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 c…graf contruit un graphe aléatoire
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.L'algo réalise un typage des sommets et les compare à l'ordre près dans les deux graphes.
Pas de contre exemple et la complexité est clairement polynomiale.
Je lance le challenge de trouver un exemple qui foire.Quoi ?????? Mais le nombre de sommets du graphe voyons ! Comme tu le voulais avec tes $N=49$ ou $N=129$ etc....Le but est de faire des calculs par applications affines et autres opérations simples pour des processeurs.
J'avais montré dans un papier que toute opération linéaire sur un corps quelconque de $K^n$ dans $K^n$ se calcule par $2n-1$ opér…MapleG:={[1,2],[2,3]}; N:=3; arc:=proc(i,j) global G;member([i,j],G);end: d1:=proc(x) local k,y;global N; k:=0;for y to N do if arc(x,y) then k:=k+1;fi;od; k;end: d2:=proc(x) local k,y…Dans ce nouveau contexte, le $a\wedge b$ devient $(a+b)_2$ puisque $(a+b)$ vaut respectivement $00,01,01,10$ pour $ab=00,01,10,11$
et le $a\vee b$ devient $(1+a+b)_2$
et $\lnot a$ devient $(1+a)_1$
vous voyez ?En fait, c'est plus intéressant d'oublier la partie entière et de considérer ce qui peut être lu en position $i$ dans un registre.
La motivation est calculatoire. Un ordinateur calcule vite des transformations affines et sait vite lire l…pour NOT...on peut prendre $1-x$Pas il faudrait.....mais il suffirait.
Bonjour!