Problème du second voisinage - Page 3 — Les-mathematiques.net The most powerful custom community solution in the world

Problème du second voisinage

13»

Réponses

  • Je pense avoir trouvé un contre-exemple, mais j'arrive pas à le poster ?
  • Salut.
    @serge burckel je pense que tu dois améliorer un peu ton code. Je constate avec le graphe que je vois comme contre-exemple, qu'il renvoie d'abord un message d'erreur, le programme avec le graphe, avant d'être prêt à répondre.
    Encore merci.
  • Excuse @serge, je pense que j'avais fait une erreur dans la saisie. Le graphe ne marche pas en tant que contre-exemple. Je crois maintenant que la conjecture est vraie.
    Je pense savoir montrer que tout graphe orienté simple contenant un cycle contient un sommet solution. Il suffit alors de savoir prouver que tout graphe dont tout sommet est de degré minimal 1, contient un cycle.
    Merci.
  • Salut.
    J'ai concocté un nouveau graphe que je pense être un contre-exemple. Mais @serge burckel, ton programme m'envoie un message d'erreur avant de dire qu'il n'y a pas de solution. Cela m'est déjà arrivé pour un graphe qui ne marchait pas. Du coup, je suis en train de chercher l'erreur (de saisie je crois), mais je n'arrive pas à le trouver. Qu'en penses-tu ?
  • Modifié (1 Jan)
    Je n'arrive toujours pas à vérifier mon contre-exemple qui est un graphe à 55 sommets. Je pense que ton programme est un peu trop lourd pour des graphes d'une cinquantaine de sommets...
    Je voudrais connaitre par ailleurs le code LATEX pour dessiner ''un arc'' (arête orienté), comme ça, je pourrais envoyer le graphe schématisé que j'ai construit. Merci d'avance.
  • Modifié (2 Jan)
    @serge buckel, je n'arrive pas à vérifier mon graphe avec le code Maple que tu as envoyé, peut-être pour les raisons citées ci-haut. Donc comme d'habitude j'ai compté à partir d'un graphe schématisé.
    Je propose comme contre-exemple un graphe d'ordre $55$ dont les sommets notés de $1$ à $55$ sont liés par les arcs suivants (voir fichier joint).
    J'espère ne pas avoir fait d'erreur de saisie.
    D'après mon comptage,
    - les sommets $1, 2, 3,  4, 19, 20, 21, 22, 37, 38, 39, 40$ ont chacun $20$ voisins et $19$ second voisins. 
    - les sommets $5, 6, 23, 24, 41, 42$ ont chacun $25$ voisins et $24$ second voisins.
    - les sommets $7, 8, 9,  10,  11, 12, 25, 26, 27,  28, 29, 30, 43, 44, 45, 46, 47, 48$ ont chacun $24$ voisins et $23$ second voisins.
    - les sommets $13, 14, 15, 16, 17, 18, 31, 32, 33, 34, 35, 36, 49, 50, 51, 52, 53, 54$ ont chacun $22$ voisins et $21$ second voisins.
    - le sommet $55$ a $36$ voisins et $18$ second voisins.
    Bonne vérification et merci.
    [Préférer joindre un fichier à insérer 56 lignes dans un message. AD]
  • Modifié (2 Jan)
    Merci AD pour la remarque.
    Zut ! j'ai vu que j'ai mal compté encore une fois.
  • Salut.
    Encore une fois, je pense avoir trouvé un contre-exemple (voir fichier tex pour une vérification).

    PS : Tu n'es plus très pressé de vérifier pour moi @serge buckel, pourquoi ? Je ne sais pas pourquoi mais je n'y arrive pas avec ton programme pour des graphes d'ordre relativement grand.

    Merci d'avance.
  • Pardon, j'ai oublié le fichier dans le message précédent. Il s'agit d'un graphe d'ordre 100.
  • Il y a une erreur de saisi dans le fichier ci-haut envoyé. le sommet 60 a été répété. Voila le fichier corrigé. Si quelqu'un peut vérifier avec le code d'@serge buckel , ce sera gentil. C'est peut-être tout simplement, un problème de puissance de calcul de mon PC.
    Merci.
  • Modifié (16 Jan)
    Je vais, (peut-être ça peut servir), un peu expliquer la méthode utilisée pour trouver ce contre-exemple.
    Comme je l'avais fait dans une des tentatives de démonstration, je fais une partition de l'ensemble des sommets du graphe initial $G = (V, E)$, par des sous ensembles formés chacun de l'ensemble des sommets ayant les mêmes voisins (je les prends sans correspondance entre eux).
    Par la suite je peux considérer un graphe $G' = (V', E')$ obtenu à partir de $G$ avec un plus petit nombre de ''sommets'' et d'arcs, parce que les arcs vont aller de sous-ensembles de sommets de $V$ ne correspondant pas entre eux , en sous-ensembles de sommets de $V$ ne correspondant pas entre eux (les éléments de $V'$ sont composés de ces sous-ensembles de sommets).
    Il devient ainsi assez facile de travailler avec la matrice d'adjacence de $G'$. Les sommets de $G'$ ont des poids donnant les véritables nombres de sommets (les sommets de $G$) dans chacun d'entre eux.
    Ici $|V| = 100$ et on peut poser $|V'| = \{a, b, c, d, e, f, g, h, i, j, k, l, m\}$, et ainsi $|V'| = 13$. Les poids sont donnés par :
    $a\to 9, b\to 1, c\to 15, d\to 5, e\to 9, f\to 1, g\to 15, h\to 5, i\to 9, j\to 1, k\to 15, l\to 5, m\to 10$.
    Dans la matrice d'adjacence $A'$ de $G'$ qui est une matrice $13\times 13$ ($(a, b, c, d, e, f, g, h, i, j, k, l, m)\times (a, b, c, d, e, f, g, h, i, j, k, l, m)$), l'élément $A'_{[i,j]}$ est $1$ si le sommet $j$ est un voisin du sommet $i$, $0$ sinon.
    La matrice d'adjacence de $G'$ est la suivante.
    $A' = \begin{pmatrix}
    0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}$
    Il est relativement aisé de compter avec cette présentation et j'attends quelque vérification de votre part.
    Moi j'ai compté avec le graphe schématisé de $G'$, et j'ai vu les résultats suivants :
    - les sommets dans $a, e$ et $i$ ont 47 voisins et 44 second voisins,
    - les sommets dans $b, f$ et $j$ ont 51 voisins et 48 second voisins,
     - les sommets dans $c, g$ et $k$ ont 43 voisins et 41 second voisins,
    - les sommets dans $d, h$ et $l$ ont 48 voisins et 47 second voisins, - 
    - les sommets dans $m$ ont 45 voisins et 42 second voisins.
    Si je n'ai pas fait d'erreur de comptage, ce graphe est bien un contre-exemple à la conjecture.
  • Modifié (16 Jan)
    @AD pourquoi la matrice reste en mode tex ?
    [C'est corrigé. AD]
  • Merci @AD.
    Désolé, il y a encore une erreur : le graphe comporte les arêtes $[a, g]$ et $[g, a]$.
    J'invite à chercher un contre-exemple (c'est amusant), mais je commence à me sentir un peu seul.
    Bienvenue...
  • @babsgueye le graphe que tu as posté ICI ne respecte pas les contraintes données par serge. En effet tu as [1,41] et [41,1] dans ton fichier... un cycle de longueur 2 quoi.

    PS. si tu apprenais un peu de Python tu pourrais vérifier tout ça par toi-même.
  • Modifié (18 Jan)
    Tiens je te file un code pour vérifier si tes graphes contiennent des cycles de longueur 2 comme ça tu pourras faire joujou longtemps avant de revenir... :mrgreen:

    Sur cette page tu insères le code suivant dans la partie gauche : 

    import numpy as np
    
    T=[[1,10],[1,11],[1,12],[1,13]] #insérer tous les sommets ici entre les crochets
    
    A=np.zeros((np.amax(T),np.amax(T)), dtype=int)
    
    for c in T:
        A[c[0]-1,c[1]-1]=1
    
    def is_valid(A):
        d = A.shape
        if d[0]!= d[1]:
            print("Erreur : la matrice d'adjacence n'est pas carrée")
            return
    
        for i in range(d[0]):
            for j in range(d[1]):
                if A[i,j] == 1 and A[j,i] ==1:
                    print(f"Erreur : cycle de longueur 2 trouvé {(i+1,j+1)} et {(j+1,i+1)}")
                    return
        print("C'est valide")
    
    is_valid(A)
    puis tu exécutes les étapes suivantes : 

    1) cliquer sur "Run"
    2) lire le message d'erreur indiquant le cycle de longueur 2 présent dans le graphe (tu en auras toujours un ne t'en fait pas... 🤣)
    3) corriger le graphe
    4) revenir au point 1)
  • Merci @raoul.S, je vais télécharger Python. Mais me mettre maintenant à vraiment apprendre la programmation, j'ai un peu de mal. Peut-être que l'envie me viendra un jour.
  • Modifié (16 Mar)
    Salut.
    Après avoir tenté en vain de trouver un contre-exemple à la conjecture, je suis revenu à essayer de prouver sa véracité.
    Ma méthode est de montrer que s'il existait un graphe $G$ d'ordre $n\in\,\mathbb{N}^*$, ne vérifiant pas la conjecture (c'est-à-dire tel que $\forall s\in G,\,G_{1}(s)\gt G_{2}(s)$, où $G_{1}(s)$ désigne le nombre de voisins de $s$ et $G_{2}(s)$ le nombre de second voisins de $s$ dans $G$), alors il existe un graphe $G'$, sous graphe de $G$, d'ordre $n - 1$ ne vérifiant pas la conjecture. Pour cela, on raisonne comme suit.

    Supposons qu'il existe un graphe $G$ d'ordre $n\in\,\mathbb{N}^*$ avec $n\gt 6$, tel que $\forall s\in G,\,G_{1}(s)\gt G_{2}(s)$.
    Soit $x_{1}\in\,G$, on a que $\forall x$ précédent de $x_{1}$ (c'est-à-dire que $x_{1}$ est voisin de $x$), $x_{1}$ a un voisin qui n'est pas voisin de $x$, et alors si on enlève le sommet $x_{1}$ de $G$, on obtient un graphe $G'$ d'ordre $n - 1$, sous graphe de $G$ tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
    Sinon $\exists\, x_{2}$ précédent de $x_{1}$ tel que tous les voisins de $x_{1}$, sont des voisins de $x_{2}$. Tenons alors le raisonnement précédent sur $x_{2}$, à savoir :
    $\forall x$ précédent de $x_{2}$, $x_{2}$ a un voisin qui n'est pas voisin de $x$, et alors si on enlève le sommet $x_{2}$ de $G$, on obtient un graphe $G'$ d'ordre $n - 1$, sous graphe de $G$ tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
    Sinon $\exists\, x_{3}$ précédent de $x_{2}$ tel que tous les voisins de $x_{2}$, sont des voisins de $x_{3}$ (Retenons que $x_{1}$ et tous ses voisins sont alors voisins de $x_{3}$).
    Ce processus s'arrête à un certain $x_{i},\, (1\lt i\lt n)$, alors il existe $G'$ sous graphe de $G$ d'ordre $n - 1$, tel que $\forall s\in G',\,G'_{1}(s)\gt G'_{2}(s)$. C'est dire qu'on a alors un graphe $G'$ d'ordre $n - 1$ ne vérifiant pas la conjecture.
    Sinon $\exists\, x_{n}\in\,G$ tel que tous les sommets de $G$ sont des voisins de $x_{n}$. Mais alors, si on enlève $x_{n}$, chacun des sommets $s$ de $G$ restants sera tel que $G'_{1}(s)\gt G'_{2}(s)$, car $x_{n}$ n'était ni voisin, ni second voisin d'aucun de ces sommets restants de $G$.

    On a donc montrer que s'il existait un graphe qui ne vérifie pas la conjecture, il existerait toujours un graphe plus petit qui ne vérifie pas la conjecture. De proche en proche, il existerait alors un graphe d'ordre inférieur à $6$ qui ne vérifierait pas la conjecture ;.ce qui est absurde, parce qu'il a été démontré, qu'un contre-exemple à la conjecture serait d'ordre supérieur à $6$.
    Cqfd.
  • J'aime bien cette démonstration. Elle est similaire à la méthode de descente, souvent utilisée en théorie des nombres.
  • Un petit coup d'épingle dans une démonstration gonflable et l'homme qui y jouit, en général, devient triste. Mais toi, tu n'es jamais triste: Tu la rustines et c'est reparti. Je t'économise une rustine.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!