Problème de l'isomorphisme des graphes
Un petit tour ici pour vous présenter mon dernier travail concernant un problème célèbre ayant pas mal d'applications.
Etant donnés deux graphes $G=(V,E)$ et $H=(V,F)$, existe-t-il une permutation $\sigma$ sur $V$ telle que :
$\{x,y\}$ est une arête de $G$ si et seulement si $\{\sigma(x),\sigma(y)\}$ est une arête de $H$.
On peut résumer cela en $\sigma(E)=F$.
La question porte sur la possibilité d'avoir une méthode efficace pour décider cela.
Bien sûr, on peut essayer toutes les $N!$ permutations pour $N=|V|$. Mais peut-on faire mieux ? Une question difficile de longue date.
Voici ma réponse : OUI et même en $O(N^3)$. Je vous joins ici la méthode pour vous amuser. C'est soumis à une revue (dans mon style).
Bien à vous, bonne journée.
modif 1 : petite adaptation aux graphes avec des boucles... ça peut-être utile pour certaines applications.
modif 2 : allègement après une "réaction allergique" de Seirios
modif 3 : petite remarque sur les boucles.
modif 4 : du coup...simplifié !
modif 5 : petite preuve
Etant donnés deux graphes $G=(V,E)$ et $H=(V,F)$, existe-t-il une permutation $\sigma$ sur $V$ telle que :
$\{x,y\}$ est une arête de $G$ si et seulement si $\{\sigma(x),\sigma(y)\}$ est une arête de $H$.
On peut résumer cela en $\sigma(E)=F$.
La question porte sur la possibilité d'avoir une méthode efficace pour décider cela.
Bien sûr, on peut essayer toutes les $N!$ permutations pour $N=|V|$. Mais peut-on faire mieux ? Une question difficile de longue date.
Voici ma réponse : OUI et même en $O(N^3)$. Je vous joins ici la méthode pour vous amuser. C'est soumis à une revue (dans mon style).
Bien à vous, bonne journée.
modif 1 : petite adaptation aux graphes avec des boucles... ça peut-être utile pour certaines applications.
modif 2 : allègement après une "réaction allergique" de Seirios
modif 3 : petite remarque sur les boucles.
modif 4 : du coup...simplifié !
modif 5 : petite preuve
Réponses
-
LOL...je fais des tests comparatifs.
Sur certains exemples, la fonction intégrée dans la librairie de Théorie des Graphes de Maple prend plus de 17 heures pour décider de l'isomorphisme de deux graphes ! Alors que mon algo prend 1/4 de seconde. -
Problème de l'isomorphisme des graphes je ne savais pas qu'il était étudié.
On dirait qu'en 2015 quelqu'un a trouvé un algorithme quasi-polynomial. -
Raoul.S
Oui László Babai a donné une méthode quasi polynomiale (pas polynomiale).
Méthode d'abord controversée et réfutée puis refondue.
Je n'en sais pas plus car je ne lis jamais les travaux des autres.
Mais je lui ai envoyé mon papier ainsi qu'à une revue.
Peut-être qu'il ne lira pas non plus ce que je lui ai envoyé (s'il est comme moi). -
@Martial....zut je viens de lire ton message. Du coup, je ne peux plus réfléchir indépendamment à ces deux questions profondes : tu m'as influencé.
Plus sérieusement, je pense qu'il faut ces deux formes de chercheurs pour faire des grandes avancées. Des rêveurs bordéliques et intuitifs et des bosseurs rigoureux et assidus qui vont d'abord démolir les délires des premiers mais ensuite quand même y trouver, une fois calmés, un petit truc à développer ou à comprendre. Les premiers seront oubliés, mais ils s'en foutent en général. -
C'est une plaisanterie ? Le ton du message est sérieux, mais le contenu du pdf paraît plutôt ridicule, alors je doute…
Prétendre s'attaquer à un problème de tout premier plan et écrire :Many experimentations with a computer confirm this. We leave for the moment the proof of that.
Ça part mal. Et puis, affirmer que l'algorithme est quadratique et commencer par calculer les distances entre chaque paire de sommets, bon…Plus sérieusement, je pense qu'il faut ces deux formes de chercheurs pour faire des grandes avancées. Des rêveurs bordéliques et intuitifs et des bosseurs rigoureux et assidus qui vont d'abord démolir les délires des premiers mais ensuite quand même y trouver, une fois calmés, un petit truc à développer ou à comprendre. Les premiers seront oubliés, mais ils s'en foutent en général.
Des exemples ? -
@Seirios
L'algorithme de Floyd-Warshall par exemple pour calculer toutes ces distances...tu connais ?
La complexité est une fonction de la taille de la donnée...tu connais ?
Un exemple ? Oui...ce que tu fais là avec ce que j'ai fait là !
Mais je vais tirer les leçons de ta réaction et enlever ces allusions au quadratique et aux calculs de test.
MERCI donc...ça va raccourcir la page de l'article...je le trouvais aussi trop long. -
@Seirios
En effet, tu as raison, j'avais trop rapidement noté $O(N^2)$ dans le premier post ici alors que j'avais aussi pris $N$ pour le nombre de sommets et pas la taille de la donnée. C'est corrigé....merci. -
Génial : une affirmation générale illustrée par ton cas particulier. Ça fait très génie incompris.Un exemple ? Oui...ce que tu fais là avec ce que j'ai fait là !
Libre à toi de considérer ma réaction comme "allergique", mais la forme laisse vraiment à désirer pour un article prévu pour la publication. Quelques citations :
Donc aucune mise en contexte. Sur un problème important, on s'attendrait à ce que le travail soit comparé aux résultats antérieurs. En quoi ce que tu fais est-il différent ou même meilleur que ce qui a déjà été fait ?We assume that the reader is familiar with these notions and with this problem.
Ce que je comprends, c'est que tu n'es même pas sûr que ton algorithme fonctionne, qu'il ne repose sur aucune preuve. Quel en est donc l'intérêt ?In this short paper, we wanted to present this method that we claim to be correct and polynomial. We expect that a complete formal proof will confirm that soon.
Affirmation totalement gratuite. Et qui n'a d'ailleurs pas grand intérêt : un algorithme court et faux fera de même en partant d'exemples où tu trouves la bonne solution par miracle.On some instances, the Graph Theory package of Maple took more than 17 hours to give an answer. This method took 1/4 of second.
Maintenant, nous sommes bien d'accord : c'est une critique sur la forme et non sur le fond. J'admets que ce n'est pas mon domaine, et que j'ai de tout même d'autres choses à faire que d'étudier de près ce que tu as écrit. Ce qui m'a fait tilter, c'est que tu dis avoir soumis ton article pour publication. Je ne sais pas dans quel journal, mais, pour moi, tant qu'il n'y a pas de preuve, ton article n'a pas le moindre intérêt. -
Bonjour.
Serge burckel : Sans vouloir être péremptoire, le noeud de ta méthode pour déterminer l'isomorphisme de deux graphes, c'est un distancier ?
C'est effectivement quadratique en le nombre de sommets de chaque graphe, mais absolument pas approprié pour déterminer l'isomorphisme de manière générale, c'est plutôt l'isométrie de deux graphes que tu testes.
Cordialement.
[Édit : Correction de coquilles et d'omissions dans le message, j'ajoute aussi que je n'avais initialement pas vu que Seirios avait fait la même remarque fondamentale sur le calcul des distances.]Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bon, @Dreamer m'encourage positivement à donner des explications et un semblant de preuve. Je vais donc le faire rapidement.
Pour les autres commentaires (moins positifs, mais c'est normal)...mais oui, je n'ai testé qu'une paire de graphes au hasard et je n'ai aucune idée sur ce que j'ai fait...j'ai été comme un chimpanzé devant une machine à écrire à taper n'importe quoi....LOL -
Alors si c'est normal...
-
Voilà...un sketch de preuve élaboré.
-
D'accord.
Je dois dire que le "sketch", écrit d'une traite sans respirer, est assez dur à suivre pour moi.
Je vois aussi que la partie algorithmique n'est pas modifiée.
Cela tombe bien car je compte te demander de faire un petit test :
1) Générer un seul graphe G, comme ton générateur en est sans doute capable.
2) En faire une copie que tu renommes H.
3) Aller dans la description de H pour modifier juste la distance d'une arête de l'enveloppe du graphe, en y ajoutant une valeur pas trop grande mais quand même non négligeable (du style nouvelle valeur = 1,1 fois la valeur d'origine).
4) Tester ce que ton programme dit de l'isomorphisme entre G et H.
Je prédis déjà sa réponse : "no".
Or les deux graphes sont pourtant isomorphes...
Reviens vite dire si je me suis trompé.
À bientôt.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
@Dreamer
Je crois qu'on ne parle pas de la même chose.
Les arêtes de ces graphes ne sont pas évaluées. La distance entre deux sommets est égale au nombre d'arêtes minimal entre eux. Ce n'est pas la somme minimale de leurs poids. Leurs poids est toujours invariablement fixé à $1$ si tu veux.
Bien évidemment, si tu veux me faire changer la valuation des arêtes pour brouiller les distances mais considérer ensuite que deux arêtes de valeurs différentes sont équivalentes, on va droit à un problème de cohérence et à une réponse "NO". Mais l'algorithme aura raison. C'est toi qui aura voulu faire des mélanges de genres incohérents et indigestes il me semble. -
Ce que j'essaie de te faire comprendre, c'est que la liste de liste de distances que tu tries sur chacun de tes graphes et qui sert de critère de décision pour évaluer leur isomorphisme n'évalues en fait pas leur isomorphisme.
C'est même pire que cela car je comptais te montrer ensuite qu'il existe aussi des instances de graphes non isomorphes mais ayant le même nombre de sommets et d'arêtes (et des longueurs équivalentes pour les arêtes) et que ces instances de graphes seraient déclarées isomorphes par ton critère de décision (qui termine par un tri brut des listes de distances avant de vérifier leur égalité, ce qui au passage détruit leurs structures respectives en tant que graphe).
Nous en resterons donc là.
Bonne continuation.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
@Dreamer
Ce que tu devrais comprendre c'est que la méthode ne repose pas seulement sur ces distances mais sur les structures.
Je ne fais pas du tout des listes de distances. Je fais des listes de types qui reflètent des structures.
Les distances ne sont qu'un support de plus à cette structure...comme le sont aussi les arêtes.
Oui, ce n'est pas parce que deux graphes ont chacun 23 arêtes qu'ils sont isomorphes.
Et c'est aussi pareil pour les distances et plein d'autres mesures.
Deux graphes k-réguliers peuvent être non isomorphes.
Tu sais peut-être pas que je sais tout cela.
Alors nous sommes d'accord ? -
J'ai mis à jour la dernière version. Elle est soumise à un journal spécialisé.
Un petit retour sur ce que je disais sur la complexité. La représentation standard pour une machine de Turing d'un graphe à $N$ sommets est donnée par une matrice d'adjacence symétrique $N\times N$ avec des valeurs $1$ ou $0$ qui indiquent la présence ou l'absence d'arête.
Sa taille $T$ est donc en $N^2$. Un algo en $N^3$ étapes est donc de complexité moindre que $T^2$ (moins que quadratique donc). -
Bon ben tu nous diras si ça a été accepté. Mais c'est vrai que tu as ton "style particulier" de présentation... J'avais déjà survolé ton texte sur $P=NP$ et je trouve que tu es un peu avare de détails et de clarté.
-
Bonsoir.
Je suis d'accord avec Georges Abitbol.
Après avoir tenté de déchiffrer (et ce n'est pas la traduction qui a posé problème) l'algorithme (le "sketch", désolé ce sera pour plus tard), je me retrouve avec plusieurs questions quant-à son fonctionnement.
Peut-être qu'une partie des réponses à mes questions sont dans le "sketch", mais elles ne peuvent pas s'y trouver toutes, étant donné que le "sketch" est une tentative de clarification de l'algorithme, or une partie de mes questions à trait au choix même des variables, de leur nom et de leur 'type' (sic).
1) En filigrane, il est question d'une sorte d'entier qui est appelé "type", pourquoi ce nom alors qu'une appellation un peu plus judicieuse aurait pu être "norme adjacente" (abrégée en Nadj) ?
Cela aurait au moins eu le mérite de mettre en avant qu'il est question d'une sorte de distance liée à la matrice d'adjacence d'un graphe.
2) Il est question initialement d'un $t_{x,y}$ (je suppose une matrice d'entiers), d'un $\tau_K(x,y)$ (je suppose une fonction qui a notamment le bon goût d'être récursive, merci la mémoïsation prise en charge de manière transparente), et d'un $\sigma_K(x,y)$ (je penche pour une matrice d'entiers, mais comme elle est nommée comme une fonction, c'est du grand art, au passage, elle est renseignée comme "un plus court chemin", comprenne qui peut), de plus, le $v_z$ qui sort du chapeau dans la sous-routine de calcul de la liste de distances, lui, je ne sais pas comment il atterrit dans la soupe ; je vois bien comment il est calculé, pour le reste cela dépasse mes compétences en compréhension d'algorithme, j'espère que c'est bien expliqué dans le "sketch".
Au final, cela fait beaucoup de 'choses' différentes pour calculer des distances, entières de surcroît...
3) Entre les matrices et les listes de listes, je pense qu'il serait opportun d'harmoniser un peu les choses (par exemple, Matlab voit les listes de listes comme des matrices, je dis cela, je dis rien).
4) Complexité : elle est effectivement polynomiale, et pour peu que la machine soit puissante, que la procédure ait été optimisée en interne et que la mémoire allouée soit conséquente, je veux bien croire que cela paraisse rapide, mais en aucun cas il est question d'une complexité en $n^{3/2}$.
Pour moi, on est plus sur du $n^{7/2} \ln(n)$, je pourrais détailler, mais ce que je ferais comme simplifications pourrait amener à penser que je me trompe et pas dans le bon sens pour Serge Burckel.
L'impression d'ensemble est que si ce sont les calculs menés pour conduire à la solution de l'isomorphisme de graphes en toute généralité, ce n'est pas suffisant.
L'approche par manipulation de la matrice d'adjacence est effectivement ce qui est utilisé pour attaquer les instances qui peuvent effectivement être résolues de manière polynomiale, mais cela n'épuise pas le problème général, et il s'en faut de beaucoup.
[Édit : Encore une toute petite question, parce que ça me trotte dans la tête : comment ils sont générés, les graphes qui sont mangés par cet algorithme ?]
En tous cas, merci pour cette tentative, j'ai plein de nœuds à défaire.
Je souhaite aussi bonne chance au comité de lecture, ce serait bien d'avoir son avis quand il le remettra.
À bientôt.
[Édit 2 : J'ai hésité à me lancer dans une explication dessus, mais j'ai eu peur de passer pour le schtroumf à lunettes des méthodes de programmation.
La memoïsation est une technique de gestion de la mémoire permettant notamment de contourner certaines restrictions dues à l'explosion des mises en mémoire redondantes des instances récursives avant résolution en fin d'exécution.
En l'occurrence, ce terme appuyait la suggestion d'une optimisation peut-être inconnue de Serge Burckel, étant donné que beaucoup d'architectures actuelles s'en chargent de manière transparente.]Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Je suis en voyage mais je bosse encore sur ce truc.
Vos questions montrent que ce n'est vraiment pas clair... je ne vais pas y répondre là puisque j'ai cherché ces deux derniers jour <<l'âme>> du truc. Je prépare une version bien plus simple et NON récursive mais itérative... je rédige à mon retour à la maison et enverrai ici et à la revue
cette version "simplifiée".
Juste pour les variables :
tau(x,y) est une fonction récursive qui calcule un entier
t_xy est un entier qui se souvient des valeurs de tau(x,y) calculées
v_x c'est juste pour écrire de cette façon la fonction qui suit....c'est du style.
sigma....je crois que je ne m'en sers plus.
Mais je répète... une nouvelle version est prête. Je l'ai programmée... ça marche pareil et encore plus vite et les arguments sont les mêmes mais plus visibles et plus facilement prouvables. Et il n'y a presque plus de variables qui font peur à certains... LOL
Sur P<>NP... le papier de deux pages est soumis depuis un an. Ce n'est pas tout à fait la preuve de P<>NP mais c'est très proche.
Voici la quasi dernière version en PDF joint. -
Bon allez, puisque je suis avare en explications, je vous donne en exclusivité une image simple de l'idée à méditer.
Soit G le graphe d'un triangle X Y Z. Chaque sommet est de degré 2.
Soit H le transformé de G qui consiste à enlever l'arête Y-Z et à mettre sur Y et Z une boucle.
Là encore les sommets sont de degrés 2...mais G et H ne sont bien sûr pas isomorphes.
Un point de vue GLOBAL de ces degrés ne voit pas de différence et on se dit : <<les degrés...c'est nul !>>
Mais en fait non, prenons la "perspective" de chacun des sommets. Cela consiste à regarder à distance 0 puis 1 puis 2 etc....
Et là, les points de vues LOCAUX sont différents. De plus, il suffit de regarder le degré d'un sommet sur l'horizon à distance d d'un sommet dans la restriction du graphe à cet horizon. Disons le "degré plat". Par exemple, dans la perspective de X, le sommet Y est à distance 1 de X et son degré plat dans G est 0 mais dans H c'est 1.
Ensuite la preuve se fait par induction. Soit le plus petit graphe M où ce principe serait archi con pour avoir un invariant de M par isomorphisme. On regarde l'horizon d'un sommet. C'est plus petit et c'est donc pas archi con et en plus on montre que ça reste pertinent dans M.
Voilà. -
Il faut aussi penser à considérer tous les sommets et leurs perspectives respectives. Pourquoi ?
1. Un graphe n'est pas forcément connexe...donc un sommet ne peut pas forcément "tout voir".
2. On ne peut pas savoir quel "point de repère" a été pris dans chacun des graphes G,H à comparer.
On fait aussi des tris de listes pour donner de l'invariance par rapport aux sommets.
Bref...cette nouvelle méthode est plus simple et plus rapide....quadratique je pense....je verrai en rédigeant. -
Et pour ceux qui "pigent" le truc et Maple, voici la procédure itérative principale du calcul de la perspective d'un sommet dans un graphe :
lst:=proc(x) local s,l,d,ll,dd,y,z,t; s:={x};l:={x};t:=[]; while l<>{} do ll:={};dd:=[]; for y in l do d:=0; for z to N do if arc(y,z) then if member(z,l) then d:=d+1;fi; if not member(z,s) then ll:=ll union {z};fi; fi;od;#z dd:=[op(dd),d]; od;#y l:=ll;s:=s union l;t:=[op(t),sort(dd)]; od;#l t;end:Bon, j'anticipe vos "kézakos ?" :
s : le disque des sommets vus...le disque des horizons vus...au départ horizon n°0 qui contient seulement x.
l : le bord extérieur de ce disque...les sommets à distance k...l'horizon n°k.
ll : le bord extérieur supérieur...les sommets à distance k+1
d : le degré plat d'un sommet de ce bord l
dd : la liste de ces degrés plats
t: la liste de ces dd ordonnés...la perspective de x
EXEMPLE :
Graphe=
{{1,1}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 8}, {1, 9}, {2, 3}, {2, 7}, {2, 8}, {2, 9}, {3, 9}, {4, 6}, {4, 7}, {5, 8}, {5, 10}, {6, 7}, {6, 8}, {6, 9}, {7, 8}, {9, 10}}
lst(1)=1], [1, 1, 1, 2, 2, 3], [0, 1, 1
Après, il suffit de construire la liste des N perspectives pour chacun des deux graphes G,H et de comparer ces deux listes A,B à l'ordre près des éléments. Par exemple comme suit :eq:=proc() local a,b,ok,k;global A,B; ok:=true;b:=B; for a in A while ok do if member(a,b,'k') then b:=subsop(k=NULL,b) else ok:=false;fi; od; ok;end:
Voilà ! -
Une remarque : on peut encore simplifier la perspective.
Il suffit de faire la liste pour les horizons de [cardinal de cet horizon, nombre d'arêtes dans cet horizon]
L'ensemble des N perspectives permet de reconstruire le graphe...à isomorphisme près.
Sur l'exemple donné plus haut :
{{1,1}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {1, 8}, {1, 9}, {2, 3}, {2, 7}, {2, 8}, {2, 9}, {3, 9}, {4, 6}, {4, 7}, {5, 8}, {5, 10}, {6, 7}, {6, 8}, {6, 9}, {7, 8}, {9, 10}}
la perspective de 1 devient simplement : 1, 1], [6, 5], [3, 1 -
Bon, je sais....deux pages, c'était trop long....voici mieux et en une seule page.
Plus facile à voir avec une induction sur les arêtes. -
Je pense que ce nouvel algorithme fourni prouve l'existence d'un isomorphisme lorsqu'il répond "oui" mais ne prouve pas l'inexistence lorsqu'il répond "non".
Je suis même prêt à parier sur le fait que rien qu'en prenant un graphe $G$ et en renumérotant les sommets de ce graphe $G$ pour en faire un graphe $H$, ce qui change l'ordre de parcours des sommets dans l'algorithme, l'algorithme peut répondre parfois "non"... -
@bisam
Je suis en voyage dans mon fourgon...pas facile de me connecter et de bosser. Mais pour ton pari, c'est justement le cas facile. Observe que l'algo n'a absolument que faire des noms des sommets. C'est indépendant. Le cas plus "chaud" c'est une réponse oui alors qu'ils seraient non isomorphes.
Mais je suis ravi que vous vous posiez des questions sur cet algo. Je suis conscient que je vais devoir expliquer le petit "game" que je laisse pour l'instant....une sorte de SUDOKU...amusez-vous ! -
Bonjour.
Bisam : Je pense la même chose, et puis il y a cette histoire de tri sur les distances-perspectives-horizons, il y a encore pleins de choses que je ne comprends pas bien.
Serge Burckel. Cela fait plaisir de te voir reformuler ton algorithme, cela va sans doute m'aider dans ma compréhension, pour l'instant c'est encore le brouillard, et le renommage en perspectives et horizons me semble rajouter du flou, ce n'est que mon avis.
À bientôt.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bon, j'explique un peu ces variables pour Dreamer.
-
Bon, d'après les éditeurs de la revue....il manque des explications. C'est clair qu'ils ont raison. Une page c'est court.
Le but était surtout que cet algo soit présenté et existe.
Je vais m'y remettre dès que je pourrai.
Sinon, pour l'article sur P<>NP (2 pages) cela semble suffisant depuis 1 an pour que se soit étudié de près.
J'ai remis la main sur la dernière version...la voici. -
@Serge: quelle serait l'idée clé qui annoncerait (si elle est exprimable courtement) le succès de ta preuve (je précise que je n'ai pas la dispo pour avoir lu le fil)?Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Christophe.
Soit l'ensemble de tous les chemins sans cycles (mais avec possibles redondances des sommets dans les branches distinctes) en partant de chaque sommet comme racine des arbres. Ceci est un invariant complet. Mais son calcul peut vite conduire à une explosion combinatoire.
Le truc est de calculer autrement en ne refaisant pas par exemple des calculs redondants et en mettant un ordre (basé sur les distances) tout en étant quand même invariant par rapport à l'ordre et aux noms des sommets du graphe. -
Merci pour ta réponse. Avant de dire si elle m'éclaire, je prendrai le temps de l'évaluer plus précisément.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
-
Pourquoi tu ne vérifies pas ton algo sur des graphes aléatoirement produits et en comparant avec ce qui existe (par exemple NetworkX a des fonctions permettant de vérifier si feux graphes sont isomorphes).
-
Héhéhé
Mais c'est exactement ce que j'ai fait sur des millions d'exemples. Pour ma part, je compare à Maple. -
L'aléatoire est certes bien souvent utile pour éliminer les erreurs grossières, par contre dans ces problèmes de complexité P vs NP, il ne sert généralement à rien puisque "presque tous" les problèmes sont faciles, les exceptions étant les objets de problèmes ouverts.
Par exemple
- "presque toute" les formules sont faciles à statuer comme étant ou pas des tautologies
- "presque tous" les graphes vérifient la conjecture d'Hadwiger, la conjecture de Hedtniemi, etc.
Pourtant le premier est ouvert, le deuxième est résolu comme étant vrai qu'il y a des exceptions
Autre exemple plus éloigné: "presque tous" les entiers sont des "confirmations" qu'un nombre impair n'est pas parfait (on ne sait toujours pas à l'heure actuelle s'il existe des parfaits impairs)
Presque tous les nombres pairs sont (de plein de manières différentes en plus) somme de deux nombres premiers
Entre deux entiers $n$ et $10^{10^n}$ on trouvera "presque toujours" 2 nombres premiers jumeaux, (on ignore s'il en existe une infinité)
Pour finir quelle que soit la théorie humainement pratiquable $T$ (ie récursivement énumérable), presque tous les énoncés sont indécidables par $T$. Or, face à des problèmes ouverts les mathématiciens cherchent des années, au risque de perdre leur temps sur un problème indécidable.
L'usage de l'alea est célèbrement ultra-efficace pour prouver, en revanche, des résultats d'existence. Il y a des exemples notoires où on ne sait pas prouver $\exists x: R(x)$ de façon "non alaétoire", alors qu'on prouve en quelques lignes que $\forall^* x :R(x)$ (qui entraine évidemment $\exists x: R(x)$)
Pour les visiteurs occasionnels, je rappelle ce qu'est "le problème de l'isomorphisme de graphe":
étant données deux matrices carrées $A,B$ avec des $0$ et des $1$, existe-t-il une matrice $S$ de permutation telle que $AS=SB$?
On ignore s'il existe des algorithmes polynomiaux pour le résoudre $(P)$ et il est évidemment dans $NP$
Le présent fil de Serge est consacré, sauf erreur de ma part, à étudier des preuves qu'il propose de ce problème serait, selon lui, dans $P$.Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi -
Très juste Christophe....mais sur les tests "aléatoires" je ne faisais que répondre à une question posée. Je ne donne absolument pas cela comme argument de justesse.
Mais tu l'as compris je pense. -
Bonjour.
Voici un algorithme présenté en 1981, avec son analyse de complexité et ses performances sur machines d'époque (elles sont similaires à ce que présente Serge Burckel).
Bonne lecture.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Bon, que je ne lis même pas les articles courts sur un sujet, je vous laisse le soin de juger. Aucune envie (ni courage) de me plonger dans ces nombreuses pages. J'avoue avoir quand même lu l'abstract qui m'a très moyennement convaincu...bon, le mien n'est pas vraiment mieux.
Je répète que je vais, si j'ai le courage et le temps, tout détailler et approfondir un point qui me chagrine : le typage relatif des sommets qui sont à distance égale de la racine choisie : càd sur un même horizon de vue. -
Bonjour.
Puisqu'on en est à ce stade, je dois dire que ce qui m'a peu convaincu, c'est surtout ton annonce dans ton deuxième message sur les tests comparatifs avec la bibliothèque de maple, car ceux qui programment ce genre de bibliothèques se renseignent sur l'état de l'art et savent en tenir compte.
Cordialement.Cherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
J'ai écrit ça...pas comme argument de "vente" mais en complément pour dire que c'était programmé et testé.
-
Avec une estimation de complexité au doigt mouillé.
À ta décharge, c'est compliqué dans le cas d'espèce.
[Édit : Cfr le document que j'ai mis en lien et où une vraie analyse de complexité est faite.
Il est vrai que cela prend un peu de place, mais les avantages compensent largement cet inconvénient.
Je me permets juste un dernier conseil : il est nécessaire de faire au minimum un glossaire entre les termes que tu emploies et les termes couramment utilisés, c'est le minimum de recherche à faire.]
Bonne continuationCherche livres et objets du domaine mathématique :
Intégraphes, règles log et calculateurs électromécaniques.
-
Non, en fait l'algo est simple à estimer dans sa dernière version.
Mais je répète que je ne suis pas convaincu moi-même sur ces sommets de chaque horizon. Il y a de la verticalité (distances) et de l'horizontalité (sur les horizons). Mais cette horizontalité devient de la verticalité pour les sommets de cet horizon....suis-je clair ? Pour une image de cela, on peut penser aux scanners en médecine. Il y a des faisceaux dans diverses directions qui mesurent des densités et un algo va en déduire une image.
PS. J'ai bossé pour cet algo quand j'étais à Aubière Clermont Ferrand.
Bref...pour faire bien et clarifier, je vais bien définir le typage des sommets en tenant compte de cette verticalité et horizontalité en même temps. -
Voici mon idée pour le faire proprement.
1) Soit on fait des constructions inductives en considérant les graphes restreints à ces horizons successifs...mais là, je sens intuitivement que l'on risque de dépasser le polynomial.
2) Soit on fait les typages verticaux et ensuite les horizontaux en considérant un ordre sur les sommets de ces horizons. Oui mais quel ordre ? Et bien l'ordre (défini par des entiers) dans le typage vertical (la position du type dans la liste principale). Cela se construit pour le graphe G et pour le deuxième graphe H, il n'aura pas d'autre choix que de prendre le même ordre. L'invariance par isomorphisme est respectée. Vous voyez ? -
correctif.
Je dois encore réfléchir à la manière de définir le typage dans les horizons pour qu'il soit invariant, surtout de l'ordre choisi des sommets quand ils ont un même type vertical.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 8 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 25
+19 Invités