Graph-Iso et Ordre-iso

lesmathspointclaires
lesmathspointclaires
dans Combinatoire et Graphes
Bonjour,

Dire si deux graphes sont isomorphes** en temps polynomial est un problème ouvert. Mais sait-on dire si deux ordres (évidement partiels) sur un ensemble fini, sont isomorphes** en temps polynomial


(**leur matrices d'adjacence sont alors permutativement semblables)

Merci

Réponses

  • babsgueye
    babsgueye
    Salut.
    Je tente un algorithme qui je pense permet de dire si deux graphes sont isomorphes en temps polynomial.

    J'ai deux graphes $G_1$ et $G_2$. Pour chaque graphes je déroule l'algorithme suivant.

    1) Je pends le (un s'il y en a plusieurs) sommet de plus haut degré avec tous ses voisins, qui constitue un ensemble ($E_1$) et je compte la somme des degrés des sommets dans $E_1$.
    2) Je prends parmi les sommets du graphe qui ne sont pas dans $E_1$, le (un s'il y en a plusieurs) sommet de plus haut degré avec tous ses voisins, qui constitue un ensemble ($E_2$) et je compte la somme des degrés des sommets dans $E_2$
    3) Je continue ce processus jusqu'à épuiser les sommets du graphe (Les $E_i$ forment un recouvrement de l'ensemble des sommets du graphe).
    Si les deux graphes sont isomorphes, alors ils auront autant d'ensembles $E_i$ et les ensembles $E_i$ de l'un des graphes et de l'autre auront deux à deux les mêmes sommes des degrés des sommets qu'ils contiennent.

    A vérifier svp !
    Cordialement
  • Math Coss
    Math Coss
    Cet algorithme ne peut pas répondre à la question. Ce que l'on veut, c'est pouvoir décider si oui ou non deux graphes sont isomorphes. Or, ce que tu proposes pourra au mieux, sous réserve de validité et de polynomialité, donner une réponse « non » de temps en temps quand deux graphes ne sont pas isomorphes.
  • babsgueye
    babsgueye
    Math Coss a écrit:
    ...donner une réponse « non » de temps en temps quand deux graphes ne sont pas isomorphes.

    Je ne comprends pas ici ce que tu veux dire. Veux-tu dire que parfois ça donne ''oui'' alors que les deux graphes ne sont pas isomorphes ?
  • Math Coss
    Math Coss
    Tout à fait. Si par exemple le graphe est régulier, tous les sommets sont dans $E_1$ et l'invariant que tu produis est le produit du nombre de sommets par leur degré commun. Cela ne suffit clairement pas à caractériser le graphe (deux exemples explicites ci-dessous) – mais au moins, c'est vite calculé.81314
  • babsgueye
    babsgueye
    @Math Coss
    Math Coss a écrit:
    ... tous les sommets sont dans $E_1$

    J'ai pas encore regardé avec les deux graphes que tu proposes ce qui se passe, mais je me pose la question à savoir est ce que tu as bien lu l'algorithme que je propose ? TOUS LES SOMMETS NE PEUVENT PAS ETRE DANS $E_1$ !
    Prends au moins le temps de comprendre ce que je dis (c'est du français facile) avant de le réfuter..
  • babsgueye
    babsgueye
    Je pense que tu voulais dire que pour les deux graphes $E_1$, $E_2$ et $E_3$ ont le même invariant dont je parle.

    C'est vrai, ces deux graphes ne sont pas isomorphes bien que... Merci Je vais essayer d'améliorer si possible.

    Amicalement.
  • babsgueye
    babsgueye
    Salut.
    babsgueye a écrit:
    ...et je compte la somme des degrés des sommets dans $E_1$.

    Plutôt que ça, je vais compter ''la somme des degrés des sommets dans $E_i$, moins le nombre d'arètes dans $E_i$''....
    Sinon je déroule la même chose.
  • Math Coss
    Math Coss
    Tu as raison, j'ai mal lu : j'ai calculé la somme des degrés des voisins sur l'ensemble des sommets de degré maximal au lieu d'en choisir un. Le fait de devoir choisir implique que seul compte l'ensemble des choses produites (somme des degrés ou nombre d'arêtes) et pas la liste ordonnée. (En particulier, ce n'est pas important de commencer par un sommet de degré maximal.)

    Ce n'est pas très clair s'il faut enlever les voisins du sommets considéré à chaque itération. Je suppose que non parce que s'il fallait les retirer, la liste produite dépendrait d'un choix arbitraire et le résultat n'aurait pas de raison d'être préservé par isomorphisme (en fait, il ne serait pas bien défini).

    Dans ces conditions, avec tous les graphes $3$-réguliers à $8$ sommets, le résultat du premier algorithme est [12,12,...].

    Les deux graphes suivants ne sont pas isomorphes : l'un contient un cycle de longueur $5$, l'autre est biparti donc les cycles sont de longueur paire. Mais le calcul que tu proposes donne me semble-t-il le même résultat : [3,3,3,3,3,3,3,3]. En effet, chaque sommet a trois voisins et il n'y a pas de triangles donc le sous-graphe formé par un sommet est ses voisins est « une étoile à trois branches ».81344
  • babsgueye
    babsgueye
    Math Coss a écrit:
    ...(En particulier, ce n'est pas important de commencer par un sommet de degré maximal.)

    C'est très possible, mais je pense que ça permet de minimiser le nombre des $E_i$ (pas encore bien regardé ça)
    Math Coss a écrit:
    ...Ce n'est pas très clair s'il faut enlever les voisins du sommets considéré à chaque itération

    Je ne sais pas exactement ce que tu vas faire quand tu les enlèves, mais toutefois il va falloir compter avec leurs liaisons avec les sommets extérieurs au sommets considérés,'s'il y en a, aux étapes suivantes.

    Je note que les deux graphes que tu proposes ici dans ton dernier message, ne sont pas isomorphes et ça se voit même avec la première méthode avant correction.

    L'application de cette première méthode à ces deux graphes est par exemple:

    Graphe 1

    - $E_1 =\; \{4, 1, 6, 0\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_2 = \;\{2, 7, 5, 0\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_3 = \;\{3, 0, 6, 5\}$ la somme des degrés correspondante est $4.3 = 12$
    La somme totale des degrés est donc $36$.
    Tous les choix de sommets principaux par cette méthode donnent trois ensembles $E_i$ et une somme totale des degrés égale à $36$.

    Graphe 2

    $\bullet$) Soit on a:
    - $E_1 =\;\{2, 6, 5, 3\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_1 =\;\{7, 0, 1, 4\}$ la somme des degrés correspondante est $4.3 = 12$
    La somme totale des degrés est donc $24$.
    $\bullet$) ou bien:
    - $E_1 =\;\{2, 6, 5, 3\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_2 =\;\{1, 5, 3, 7\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_3 =\;\{4, 6, 3, 7\}$ la somme des degrés correspondante est $4.3 = 12$
    - $E_4 =\;\{0, 6, 5, 7\}$ la somme des degrés correspondante est $4.3 = 12$
    la somme totale des degrés est donc $48$.
    Il n'y a que ces deux cas de figures possibles en termes de nombres d'ensembles et de somme totale des degrés.

    Alors ces deux deux graphes ne sont pas isomorphes (c'est juste par la méthode non validée et rectifiée)

    Avec la deuxième méthode (celle qui est maintenant retenue et inspirée par tes deux premiers graphes qui furent un contre-exemple), partout dans les algorithmes que j'ai décrits ci-haut, au lieu de $4.3 = 12$ on aura $4.3 - 3 = 9$ pour la somme des degrés.
    Et alors on en conclut que les deux graphes ne sont pas isomorphes.

    PS: En toute modestie, je te dis que, j'ai pas pu me procurer beaucoup d'exemples (assez compliqués) pour croire aprés vérifications à cette algorithme, et peut-être penser à une démonstration.
  • Math Coss
    Math Coss
    Voici quatre graphes $3$-réguliers à $10$ sommets pour lesquels on peut obtenir $(3,3,3)$ comme liste de nombre d'arêtes « si l'on s'y prend bien ». J'ai tiré au sort le sommet de degré maximal à chaque étape : c'est un problème parce que cela ne définit pas un invariant.

    Bien sûr, au lieu d'un des calculs possibles, on peut choisir de faire tous les calculs possibles mais là, l'algorithme ne se déroulera pas en temps polynomial.

    Enfin bref, on a une procédure mal définie, qui n'est appuyée ni par des exemples, ni par une (esquisse de) preuve, qui donne un invariant visiblement trop faible pour séparer les graphes.81356
  • babsgueye
    babsgueye
    Merci.
    Là je suis un peu pris. Je vais travailler sur ces graphes plus tard.
  • babsgueye
    babsgueye
    @Math Coss
    Je vois qu'il n'y a pas deux graphes isomorphes parmi ces quatre, bien que l'algorithme que je propose ne le vois pas pour $G2$ et $G3$ (je note les graphes de la gauche vers la droite).
    Il va falloir alors améliorer ce qui est proposé, je déroule alors l'algorithme suivant, en notant par rapport à tes remarques que le fait de choisir le sommet de plus haut degré à chaque itération minimise le nombre d'ensembles $E_i$.

    Si les deux graphes $G$ et $G'$ ont autant de sommets de même degré, on applique l'algorithme suivant sur chacun.

    1) On prend un sommet de plus haut degré avec ses voisins, qui constituent l'ensemble $E_1$ pour le graphe $G$ ($E'_1$ pour le graphe $G'$), on calcule $m_1$ ($m'_1$) qui est la somme des degrés des sommets dans $E_1$ ($E'_1$), moins le nombres d’arêtes liant les sommets dans $E_1$ ($E'_1$).
    2) On prend un sommet de plus haut degré parmi les sommets pas encore atteints, ayant le moins de voisins déjà atteints, et ses voisins qui constituent l'ensemble $E_2$, on calcule $m_2$ qui est la somme des degrés des sommets dans $E_2$, moins le nombres d’arêtes liant les sommets dans $E_2$.
    3) On continue ce processus jusqu'à recouvrir $G$ ($G'$).
    4) Si le nombre d'ensembles $E_i$ est égal au nombre d'ensembles $E'_j$ et les $m_i$ et les $m'_j$ deux à deux identiques (sinon les graphes ne sont pas isomorphes), on note les cardinaux des $(E_{i}\cap E_{j})_{i\neq j}$ et ceux des $(E'_{i}\cap E'_{j})_{i\neq j}$ et on vérifie s'ils sont deux à deux identiques ; si c'est le cas $G$ et $G'$ sont isomorphes, sinon ils le sont pas.

    J'espère pour chercher une esquisse de démonstration, que tu ne trouveras pas de contre-exemple pour ce dernier.
    Merci.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 1

etanche