π
<-
Chat plein-écran
[^]

Des graphes pas comme les autres

Discussions scientifiques et scolaires

Des graphes pas comme les autres

Message non lude Bisam » 16 Nov 2017, 01:13

Je cherche un graphe bien particulier... mais je ne sais pas s'il en existe.

Pour être plus précis, pour chaque entier naturel
$mathjax$p$mathjax$
, je souhaiterais savoir s'il existe un graphe (non orienté, sans fuseau et sans boucle) ayant
$mathjax$n$mathjax$
sommets et
$mathjax$\frac{p\times n}{2}$mathjax$
arêtes tel que :
  • Chaque sommet est de degré
    $mathjax$p$mathjax$
    , c'est-à-dire qu'il possède exactement
    $mathjax$p$mathjax$
    voisins, ou encore qu'il y a exactement
    $mathjax$p$mathjax$
    arêtes issues de ce sommet,
  • Pour chaque sommet
    $mathjax$S$mathjax$
    , les
    $mathjax$n-p$mathjax$
    sommets qui ne sont pas des voisins directs de
    $mathjax$S$mathjax$
    sont à la distance 2 de
    $mathjax$S$mathjax$
    , c'est-à-dire qu'ils sont voisins de l'un de ses voisins directs. De plus, il n'y a qu'un seul chemin de longueur 2 qui permet de les atteindre.

Je sais prouver qu'un tel graphe possède nécessairement
$mathjax$p^2+1$mathjax$
sommets, autrement dit
$mathjax$n=p^2+1$mathjax$
.

Trouver un tel graphe est trivial pour
$mathjax$p=0$mathjax$
et
$mathjax$p=1$mathjax$
, et pas difficile pour
$mathjax$p=2$mathjax$
.
J'ai réussi à trouver un exemple pour
$mathjax$p=3$mathjax$
(je rajouterai une image plus tard).
Mais je ne sais pas s'il en existe pour
$mathjax$p≥4$mathjax$
.

Votre défi est donc de trouver un exemple pour
$mathjax$p=4$mathjax$
ou de prouver qu'il n'en existe pas.
Toutes les armes sont autorisées (mathématiques, informatique, papier/crayon, etc...)

Merci d'avance pour votre aide !
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Des graphes pas comme les autres

Message non lude Bisam » 17 Nov 2017, 23:55

Pour ceux qui préfèrent, on peut aussi traduire le problème en termes de matrices d'adjacence.
Cela revient à chercher des matrices
$mathjax$A$mathjax$
symétriques de taille
$mathjax$n=p^2+1$mathjax$
, ne contenant que des 0 et des 1, avec une diagonale nulle et vérifiant
$mathjax$A^2+A=(p-1)I_n +J$mathjax$
$mathjax$J$mathjax$
est la matrice de taille
$mathjax$n$mathjax$
ne contenant que des 1.

PS : J'ai corrigé dans le post précédent le nombre d'arêtes du graphe. Il y en a
$mathjax$\frac{p\times n}{2}$mathjax$
puisque chaque arête relie deux sommets...
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Des graphes pas comme les autres

Message non lude Bisam » 18 Nov 2017, 21:51

J'ai oublié de poster la photo annoncée (je l'ai un peu améliorée depuis...) et la matrice correspondante :
Code: Tout sélectionner
[[0, 1, 1, 1, 0, 0, 0, 0, 0, 0],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0],
[1, 0, 0, 0, 0, 0, 1, 1, 0, 0],
[1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
[0, 1, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1, 0, 0, 1, 0],
[0, 0, 0, 1, 1, 0, 0, 1, 0, 0],
[0, 0, 0, 1, 0, 1, 1, 0, 0, 0]]
Petersen.png

On reconnait désormais le (célèbre) graphe de Petersen.
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile

Re: Des graphes pas comme les autres

Message non lude Nemhardy » 19 Nov 2017, 02:40

Le problème est rigolo !

Le cas
$mathjax$p = 4$mathjax$
va bien se bruteforcer, on peut réduire le nombre de graphes à considérer à une petite centaine de millions, je pense qu'en faisant un peu attention en implémentant ça (typiquement on aura pas besoin de faire tout le produit matriciel
$mathjax$17×17$mathjax$
à chaque essai), ça reste envisageable sans trop de soucis. Je tenterai ça demain si on ne sait toujours pas d'ici là et que j'ai un peu de temps (pas garanti ça, mais bon… ^^).

En gros l'idée c'est que les conditions, et en particulier l'unicité du chemin de longueur
$mathjax$2$mathjax$
si deux sommets ne sont pas voisins, donnent une forme assez bien définie au graphe, en particulier elles imposent au moins
$mathjax$2p(p-1)+1$mathjax$
arêtes si je ne me trompe pas. Asymptotiquement sur les
$mathjax$\frac{p^3+p}{2}$mathjax$
, ça ne fait pas beaucoup, mais pour les petit cas, ça permet de bien réduire le nombre de graphes à considérer si on veut faire une analyse exhaustive.

En attendant, si il y a des paris à lancer, j'ai envie de croire qu'il n'y a pas de tel graphe pour
$mathjax$p=4$mathjax$
. :p

Après, la solution du bruteforce ne reste pas hyper élégante, et ne résoudra que le cas
$mathjax$p=4$mathjax$
; j'y ai un peu réfléchi, j'ai peut-être quelques pistes pour un argument combinatoire, mais pour l'instant il faut que je réfléchisse et dorme un peu dessus.

Je sais que ce genre de problème d'existence de graphe n'est pas toujours facile, ça me rappelle un peu celui de l'existence d'un plan projectif d'ordre
$mathjax$p$mathjax$
, qui peut se traduire en problème d'existence de graphe. On sait y répondre pour
$mathjax$p$mathjax$
puissance d'un nombre premier et pour les autres
$mathjax$p$mathjax$
, on n'a la réponse que pour
$mathjax$p\leq10$mathjax$
, et le cas
$mathjax$p = 10$mathjax$
vient d'une recherche exhaustive… Espérons qu'on ait plus de chance ici !

Edit : En fait ça y est, je pense avoir une preuve "jolie" (en tout cas plus jolie que de la recherche exhaustive !) de non existence de tels graphes pour p>=4, j'écris ça dans la journée. :)
Je maintiens le portage d'Eigenmath pour les Casio monochromes, n'hésitez pas à y jeter un œil si ça vous intéresse ! :p
Avatar de l’utilisateur
NemhardyPremium
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 48%
 
Messages: 45
Inscription: 28 Déc 2014, 22:06
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Des graphes pas comme les autres

Message non lude Nemhardy » 19 Nov 2017, 13:59

En fait je me suis rendu compte que mon idée de preuve reposait sur l'argument
$mathjax$8+1 < 9$mathjax$
, c'était pas hyper satisfaisant… ^^ Donc pour l'instant je n'ai pas de preuve jolie en fait.

En revanche, on peut baisser le nombre de graphes à considérer pour le cas
$mathjax$p = 4$mathjax$
à de l'ordre de 400, donc j'ai pu faire une recherche exhaustive sans trop de raffinement (i.e. Python et produit matriciel naïf pour tester les solutions), et n'en ai pas trouvé.

Je détaille ici comment je pense qu'on peut réduire le nombre de cas, en cherchant des conditions nécessaires sur la forme d'un tel graphe.

Supposons qu'on ait un tel graphe.

On prend
$mathjax$s_0$mathjax$
un sommet.
On sait que
$mathjax$s_0$mathjax$
a
$mathjax$4$mathjax$
voisins. On note
$mathjax$N = \{s_1, s_2, s_3, s_4\}$mathjax$
l'ensemble de ses voisins.
Les autres sommets
$mathjax$s_5, …, s_{16}$mathjax$
doivent être à distance
$mathjax$2$mathjax$
de
$mathjax$s_0$mathjax$
, donc chacun est nécessairement voisins d'au moins un sommet de
$mathjax$N$mathjax$
. De plus ils sont voisins chacun d'au plus un sommet de
$mathjax$N$mathjax$
, sinon si on en a un relié à deux sommets de
$mathjax$N$mathjax$
, on obtient deux chemins de longueur 2 dudit sommet à
$mathjax$s_0$mathjax$
.

Le graphe a donc nécessairement cette forme (avec encore des arêtes en plus bien sûr ! ^^) :
Show/Hide spoilerAfficher/Masquer le spoiler
Image


On a de plus saturé le degré de
$mathjax$s_0$mathjax$
et des sommets de
$mathjax$N$mathjax$
. Les arêtes supplémentaires impliqueront donc uniquement des sommets de
$mathjax$s_5$mathjax$
à
$mathjax$s_{16}$mathjax$
(on note
$mathjax$S$mathjax$
l'ensemble de ces sommets, et pour
$mathjax$i\in\{0,1,2,3\}, S_i = \{s_{3i+5}, s_{3i+6}, s_{3i+7}\}$mathjax$


Maintenant pour avancer on passe à quelques arguments de type «Sudoku» (c'est un peu le même genre de raisonnement je trouve ^^) :

$mathjax$s_5$mathjax$
doit être en particulier à distance 2 des sommets
$mathjax$s_2, s_3, s_4$mathjax$
. Comme ceux-ci sont saturés, tout comme
$mathjax$s_0$mathjax$
, on doit passer par des sommets voisins de
$mathjax$s_2, s_3, s_4$mathjax$
:
$mathjax$s_5$mathjax$
doit avoir au moins un voisin dans
$mathjax$S_1$mathjax$
, un dans
$mathjax$S_2$mathjax$
et un dans
$mathjax$S_3$mathjax$
. Sans perte de généralité, on arrive à avoir ces trois nouvelles arêtes :
Show/Hide spoilerAfficher/Masquer le spoiler
Image


→ En raisonnant de même avec
$mathjax$s_6$mathjax$
et
$mathjax$s_7$mathjax$
, avec le fait que deux sommets de
$mathjax$S_0$mathjax$
ne peuvent pas être voisins d'un même sommet de
$mathjax$S_i$mathjax$
pour
$mathjax$i\geq1$mathjax$
(sinon ça nous donne deux chemins de longueur 2 du voisin commun vers
$mathjax$s_1$mathjax$
) on a nécessairement cette forme :
Show/Hide spoilerAfficher/Masquer le spoiler
Image


Il nous reste donc
$mathjax$9$mathjax$
arêtes à placer, impliquant uniquement des sommets de
$mathjax$S_1 \cup S_2 \cup S_3$mathjax$
car on vient de saturer les sommets de
$mathjax$S_0$mathjax$
.

$mathjax$s_8, s_9$mathjax$
et
$mathjax$s_10$mathjax$
doivent être à distance 2 de
$mathjax$s_3$mathjax$
. On doit ajouter pour chacun une arête le reliant à un sommet de
$mathjax$S_2$mathjax$
. De plus on ne doit pas relier deux sommets de la même couleur (sur le coloriage ci-dessus), sinon ça nous donnerait un chemin de longueur 2 et un chemin de longueur 1 vers le sommet de
$mathjax$S_0$mathjax$
dont est issue la couleur, ce qui est proscrit par l'identité matricielle. On a donc deux possibilités pour placer ces trois arêtes, où deux est le nombre de permutations de
$mathjax$\{1,2,3\}$mathjax$
sans point fixe.
——→ Soit on a
$mathjax$\{s_8,s_{12}\}, \{s_9,s_{13}\}, \{s_{10},s_{11}\}$mathjax$
à ajouter aux arêtes.
——→ Soit on a
$mathjax$\{s_8,s_{13}\}, \{s_9,s_{11}\}, \{s_{10},s_{12}\}$mathjax$
à ajouter aux arêtes.
Pour chacun de ces choix, on a le choix dual à faire pour mettre les sommets de
$mathjax$S_1$mathjax$
à distance 2 de
$mathjax$s_4$mathjax$
(i.e. on choisira l'association qui correspond à l'autre permutation des couleurs), donc, par symétrie, ce choix n'est pas vraiment important. Sans perte de généralité, on a maintenant la forme (en violet et jaune sont les arêtes que l'on vient de rajouter, ça commence à être un peu le bazar je sais…) :

Show/Hide spoilerAfficher/Masquer le spoiler
Image


On vient de plus de saturer les sommets de
$mathjax$S_1$mathjax$
. Il reste 3 arêtes à placer impliquant les sommets de
$mathjax$S_2 \cup S_3$mathjax$
.

C'est à partir de là que j'ai lancé la recherche exhaustive et n'ai rien trouvé.

Le risque est que j'ai me sois grossièrement planté quelque part dans l'établissement de ces conditions nécessaires, mais je pense que c'est assez propre déjà.

Je publierai le programme qui fait la recherche une fois que je l'aurai un peu nettoyé si tu veux le vérifier, pour l'instant il doit être assez peu lisible. ^^

Je pense qu'en y réfléchissant un peu plus on peut comprendre pourquoi ça coince sur ce cas à la main une fois qu'on a une forme bien définie du graphe, et ça pourrait donner la piste pour montrer le cas général.
Je maintiens le portage d'Eigenmath pour les Casio monochromes, n'hésitez pas à y jeter un œil si ça vous intéresse ! :p
Avatar de l’utilisateur
NemhardyPremium
Niveau 8: ER (Espèce Rare: nerd)
Niveau 8: ER (Espèce Rare: nerd)
Prochain niv.: 48%
 
Messages: 45
Inscription: 28 Déc 2014, 22:06
Genre: Non spécifié
Calculatrice(s):
MyCalcs profile

Re: Des graphes pas comme les autres

Message non lude Bisam » 19 Nov 2017, 14:15

La méthode est propre et correcte.
Le début est même exactement ce que j'avais fait pour éliminer le cas p=4, finalement.

On m'a finalement donné la réponse... Elle est surprenante !
Pour ceux qui veulent continuer à chercher, je la mets en spoiler.
Show/Hide spoilerAfficher/Masquer le spoiler
Il n'y a pas de solution lorsque
$mathjax$p\notin \{0,1,2,3,7,57\}$mathjax$
.
Il y a une unique solution à isomorphisme près lorsque
$mathjax$p\in \{0,1,2,3,7\}$mathjax$
.
On ne sait pas encore s'il existe une solution pour
$mathjax$p=57$mathjax$
.
C'est le théorème d'Hoffman-Singleton.


Je rajoute aussi les différents codes Python que j'ai utilisés dans ma recherche :
Show/Hide spoilerAfficher/Masquer le spoiler
Code: Tout sélectionner
## ## Importations

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import random as rd

## ## Recherche de solutions


def matrice(positions, n):
    mat = np.zeros((n, n), dtype=int)
    for (l, c) in positions:
        mat[l, c] = 1
    return np.matrix(mat)
   
def aretes(mat):
    n = len(mat)
    l = []
    for i in range(n):
        for j in range(i):
            if mat[i, j]:
                l.extend([(i, j), (j, i)])
    return l

## Recherche récursive quasi exhaustive avec des matrices

@timeit
def solutions(p, stopAtFirst=False):
    if p == 0:
        m = [[0]]
        print(m)
        return m if stopAtFirst else [m]
   
    n = p*p + 1
    I = np.eye(n)
    J = np.ones((n, n)) + (p-1)*I
    sols = []

    def find_position(positions, l, c):
        """Cherche une position de 1 à ajouter à une configuration, au-delà de la
        ligne l et de la colonne c afin qu'elle conserve les propriétés requises"""
       
        if stopAtFirst and (len(sols) > 0):
            return True
       
        if len(positions) == p*n: # on a placé tous les chiffres 1
            m = matrice(positions, n)
            if np.all(m*m + m == J):
                sols.append(m)
                print(m)
                return True
            return False
     
        # on compte le nombre de 1 déjà placés sur la ligne l avant la colonne c
        before_count = sum(1 for (i, j) in positions if i == l and j <= c)
       
        if before_count < p and c+1 < n:
            # on peut en ajouter 1 sur la même ligne
            new = (l, c+1)
        elif before_count == p:
            # on ne peut plus en rajouter
            for k in range(l):
                # on vérifie la compatibilité de cette ligne avec les précédentes
                d = sum(1 for i in range(n) if (k, i) in positions and (l, i) in positions)
                if (k, l) in positions:
                    d += 1
                if d != 1:
                    return False
            # on peut en ajouter 1 sur la ligne suivante
            new = (l+1, max(p-1, l+2))
        else:
            # on est au bout de la ligne et il manque des 1
            return False
       
        # on exécute récursivement avec et sans la nouvelle position
        (l, c) = new
        a = find_position(positions + [new, (c, l)], l, c)
        b = find_position(positions, l, c)
        return a or b

    # on initialise avec une sous-matrice solution du cas précédent
    if stopAtFirst:
        initials = aretes(solutions(p-1, True))
        find_position(initials, 0, p-1)
        return sols[0]
    else:
        for sol in solutions(p-1):
            initials = aretes(sol)
            find_position(initials, 0, p-1)
        return sols

## Affichage des graphes

def graphe_from_adj(mat):
    n = len(mat)
    g = nx.Graph()
    g.add_nodes_from(range(n))
    g.add_edges_from(aretes(mat))
    return g

def montre(mat):
    nx.draw_circular(graphe_from_adj(mat), with_labels=True)
    plt.show()
   
## Recherche itérative gloutonne sur des graphes

@timeit
def solution(p):
    n = p*p + 1
    G = nx.Graph()
    G.add_nodes_from(range(n))
   
    for noeud in range(n):
        #print(noeud)
        voisin = noeud+1
        while len(G[noeud]) < p and voisin < n:
            # voisin peut encore accepter une arête
            if len(G[voisin]) < p:
                # il n'y a pas d'arete entre noeud et voisin
                if voisin not in G[noeud]:
                    # une arete entre noeud et voisin ne crée pas de 3-cycle
                    if all(d not in G[voisin] for d in G[noeud]):
                        # ni de 4-cycle
                        if all(c not in G[d] for c in G[noeud] for d in G[voisin]):
                            G.add_edge(noeud, voisin)
            voisin += 1
        if len(G[noeud]) < p:
            print("plus de place")
   
    mat = nx.adjacency_matrix(G).todense()
   
    plt.close()
    nx.draw_circular(G, with_labels=True)
    plt.show()
   
    return mat

## Recherche récursive complète sur des graphes

@timeit
def solution_rec(p, draw=False):
    n = p*p + 1
    G = nx.Graph()
    G.add_nodes_from(range(n))
    sol = []
   
    def test_edge(G, from_vertex, to_vertex):
        # from_vertex et to_vertex peuvent encore accepter une arête
        if len(G[from_vertex]) < p and len(G[to_vertex]) < p:
            # il n'y a pas d'arete entre from_vertex et to_vertex
            if to_vertex not in G[from_vertex]:
                # une arete entre from_vertex et to_vertex ne crée pas de 3-cycle
                if all(d not in G[to_vertex] for d in G[from_vertex]):
                    # ni de 4-cycle
                    if all(c not in G[d] for c in G[from_vertex] for d in G[to_vertex]):
                        return True
        return False


    def exists_sol(G, from_vertex, to_vertex=None):
        if from_vertex >= n:
            sol.append(nx.adjacency_matrix(G).todense())
            if draw and p==3:
                nx.draw_shell(G, with_labels=True, nlist=[[0,4,2,1,6], [3,8,7,5,9]])
            return True
       
        if len(G[from_vertex]) == p:
            return exists_sol(G, from_vertex+1)
       
        if to_vertex is None:
            to_vertex = from_vertex+1
       
        if to_vertex >= n:
            return False
       
        if test_edge(G, from_vertex, to_vertex):
            G.add_edge(from_vertex, to_vertex)
            if exists_sol(G, from_vertex, to_vertex+1):
                return True
            else:
                G.remove_edge(from_vertex, to_vertex)
        return exists_sol(G, from_vertex, to_vertex+1)
   
    noeud = 0
    voisin = 1
    while noeud < n and any(not G[v] for v in range(n)):
        # on peut remplir avec la première arête qui convient
        # tant qu'il y a un noeud qui n'a pas d'arête
        if test_edge(G, noeud, voisin):
            #print((noeud, voisin))
            G.add_edge(noeud, voisin)
        voisin += 1
        if voisin == n:
            noeud += 1
            voisin = noeud+1
   
    #print("fin de l'itératif")
    if noeud < n:
        exists_sol(G, 0)
   
    return sol
Avatar de l’utilisateur
BisamAdmin
Niveau 15: CC (Chevalier des Calculatrices)
Niveau 15: CC (Chevalier des Calculatrices)
Prochain niv.: 69.5%
 
Messages: 5665
Inscription: 11 Mar 2008, 00:00
Localisation: Lyon
Genre: Homme
Calculatrice(s):
MyCalcs profile


Retourner vers Maths, physique, informatique et autre...

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 9 invités

-
Rechercher
-
Social TI-Planet
-
Sujets à la une
Comparaisons des meilleurs prix pour acheter sa calculatrice !
Aidez la communauté à documenter les révisions matérielles en listant vos calculatrices graphiques !
Phi NumWorks jailbreak
123
-
Faire un don / Premium
Pour plus de concours, de lots, de tests, nous aider à payer le serveur et les domaines...
Faire un don
Découvrez les avantages d'un compte donateur !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !


Partenaires et pub
Notre partenaire Jarrety Calculatrices à acheter chez Calcuso
-
Stats.
1101 utilisateurs:
>1079 invités
>17 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Autres sites intéressants
Texas Instruments Education
Global | France
 (English / Français)
Banque de programmes TI
ticalc.org
 (English)
La communauté TI-82
tout82.free.fr
 (Français)