Formule sur les graphes — Les-mathematiques.net The most powerful custom community solution in the world

Formule sur les graphes

Bonjour
Je vous transmets un énoncé en espérant avoir votre aide. Je ne vois pas comment faire.

On considère un graphe k-régulier de n points tels que :
pour tout (i,j) distincts il existe un unique k tel que (i,k) et (j,k) soient en relation.
Montrer que n = k(k-1)+1.

Merci d'avance.
M65

Réponses

  • Salut
    Je comprends pas bien.
    Peux tu essayer d’être plus clair en parlant de sommets et d’arêtes.
  • Bonsoir,
    Il y a par exemple cet argument:
    Notons $A = (a_{i,j})_{1\leq i,j \leq n}$ la matrice d'adjacence du graphe, c'est à dire la matrice $n\times n$ définie par: $a_{i,j} = 1$ si $\{i,j\}$ est une arête du graphe et $a_{i,j}= 0$ sinon.
    $I$ est la matrice-unité d'ordre $n$, $E$ est la matrice $n\times n$ dont tous les coefficients sont égaux à $1$, et $X$ désigne le vecteur-colonne dont les $n$ coordonnées sont égales à $1$.
    Le fait que le graphe soit $k$-régulier entraine que $AX=kX$.
    La seconde information entraine que $A^2 = (k-1)I + E$ . (le coefficient $(i,j)$ de $A^2$ est le nombre de chemins de longueur $2$ menant de $i$ à $j$.)
    Ainsi: $k^2X=A^2X=(k-1)X+nX$ et cela entraine: $k^2 =k-1+n$.
    Amicalement.
  • Merci Lou16, mais peut-on y arriver par un argument de dénombrement, sans les matrices d'adjacence ?
    M65

    Babsgueye : le graphe possède n points de degré k et pour tout (i,j) distincts, il existe un unique p tel que i voisin de p et j voisin de p. Merci,
    M65
  • Re,

    Soient $\mathcal A$ l'ensemble des arêtes, $\mathcal S$ celui des sommets, $s$ un élément de $\mathcal S\:$ et $\:\mathcal E=\left\{(x,y)\in \mathcal S^2 \mid \{s,x\} \in \mathcal A \:\: \text{et}\:\:\{x,y\} \in \mathcal A\right\}$.
    La $k$-régularité du graphe entraine que $\text{Card}\:\mathcal E= k^2$.
    En distinguant le cas où $y=s$ de ceux où $y\neq s$, et en utilisant la seconde hypothèse, il vient: $\:\:\text{Card}\:\mathcal E = k +(n-1)$, puis l'égalité cherchée .
    Ce double décompte de $\text{Card}\: \mathcal E$ correspond en fait aux deux expressions de $A^2X$ apparaissant dans mon précédent message.
    A noter qu'il n'existe, me semble-t-il, qu'un seul graphe ayant la propriété décrite dans le message initial: le graphe complet $\mathcal K_3$, c'est à dire le triangle.

    Amicalement,
  • Salut
    Je sais pas @LOU16 pourquoi tu as reédité ton message précédent (ta première proposition de $\mathcal{E}$). Je la trouve plus rigoureuse que cette nouvelle définition. Je vois plus ici pourquoi $Card(\mathcal{E}) = k^2$.
    Par ailleurs je pense que la proposition est vraie aussi pour $k\neq 2$ (c'est seulement le cas $k = 1$ qui demande peut-être une précaution); c'est ce qu'on a démontré !

    La démonstration avec la matrice d'adjacence est très belle.

    Cordialement
  • Bonjour babsgueye,

    Je suis désolé, mais je suis au maximum de mes possibilités, et ne vois pas bien le manque de rigueur dans ce nouveau choix de $\mathcal E$, qui a l' avantage de montrer que la conclusion $k^2-k =n-1$ demeure vraie si on affaiblit légèrement les hypothèses en supposant que le graphe est $k-$régulier et qu'il existe seulement un sommet $s$ qui possède avec chacun des autres sommets un unique "voisin" commun.
    $\text{Card } \:\mathcal E = k^2$ car, pour fabriquer les couples $(x,y)$ de $\mathcal E$, il y a $k$ choix possibles pour $x$ (voisins de $s$) qui se combinent à $k$ choix possibles pour $y$ (voisins de $x$).
    D'autre part, selon moi, le seul graphe obéissant aux hypothèses énoncées dans le message initial correspond au cas où $k=2$ et $n=3$, c'est à dire $\mathcal K_3$ et je pense détenir une preuve correcte qu'il n'en existe pas d'autre. Si tu en connais un avec, par exemple, $k=3$ et $n=7$, n' hésite pas à me le décrire.
    Amicalement,
    PS. Afin d'illustrer l'efficacité que peut avoir l'algèbre linéaire dans certains problèmes de la théorie des graphes, voici une preuve du fait que le graphe "triangulaire" $\mathcal K_3\:(n=3,\:k=2)$ est le seul graphe obéissant aux hypothèses du message initial. En conservant les notations précédentes:
    $\R^n = \text{Vect}(X) \oplus\text{Ker }E\:\:$ et $\:A$ stabilise chacun des sous-espaces $\text{Vect}(X)$ et $\text{Ker}E$.
    Nous avons $AX =kX\:$ et d'autre part: $\:\forall Y \in \text{Ker}E,\:\: A^2Y =(k-1)Y$. Il s'ensuit que toutes les valeurs propres de $A$ sont contenues dans $\{k;\sqrt{k-1};-\sqrt{k-1}\}$. Soient $a,b,c$ les multiplicités respectives de ces valeurs propres. Alors:
    $a=1;\:\:\:b,c \in \N;\:\:\: 1+b+c=n;\:\:\: 0 =\text{Tr}A = k +(b-c)\sqrt{k-1}$. On déduit que: $2b = n-1-\dfrac k{\sqrt{k-1}}$ ce qui entraine que $\dfrac k{\sqrt{k-1}}\in \N$ puis que $k=2$.
  • LOU16 a écrit:
    $Card\;\mathcal{E}=k^2$ car, pour fabriquer les couples (x,y) de $\mathcal{E}$, il y a k choix possibles pour x (voisins de s) qui se combinent à k choix possibles pour y (voisins de s).

    Je pensais qu'il resterait $k - 1$ choix pour $y$ qui est déjà voisin de $x$.
    J'avais aussi compris que tout pair de sommets ne devait avoir qu'un seul voisin commun (je veux dire que c'est pas seulement un seul sommet qui vérifie cette hypothèse d'après l'énoncé)

    De toute façon, j'ai pas pu trouver le graphe que tu me demandes et je me rends compte que ici $n$ est impair et qu'un graphe d'ordre impair ne peut être $k$-régulier pour $0\lt k\lt n - 1$. Donc ta remarque est vraie.

    C'est le fait qu'on le sente pas dans la démonstration qui m'a un peu surpris.

    Merci.
  • Re,

    Pardon,
    Il y a en effet une coquille dans mon dernier message que je corrige: il faut lire $k$ choix possibles pour $y$ ,voisins de $x$ , et non de $s$;
    Avec mes excuses,
  • Y'a pas à s'excuser, on est ensemble.
    Enfin je préfère la démonstration avec la matrice d'adjacence.

    Amicalement.
  • Merci à tous les deux.
    Amicalement,
    M65.
  • Salut. J'ai dit que:
    [Un graphe d'ordre impair ne peut être $k$-régulier pour $0\lt k\lt n-1$]. Une grosse bourde de ma part !

    En fait si $N = 2n + 1$ est l'ordre d'un graphe, on peut avoir un graphe $k$-régulier, pour tout $k$ pair $\leq 2n$.... Je le démontre en partant du graphe complet d'ordre $N$
    .
    Du coup @LOU16, je ne suis plus tout à fait convaincu par ta démonstration utilisant l'algèbre linéaire (que je comprends pas encore bien) pour dire que la seule valeur de $k$ possible est $2$.
    Ce qui est sur, est que $k$ ne peut pas être impair (donc pour $k = 3$ : pas de solution).

    Je pense détenir un contre-exemple à ce que tu dis, en prenant $k = 4$ et donc $n = 13$ (je ne me suis pas trop fatigué à le trouver, mais je dessine mal les graphes; essaie de le voir !) si je comprends bien la question de @M65.

    Merci
  • Pardon @LOU16.
    En fait mon contre exemple suppose qu'il existe pour tout $(i, j)$ au plus un $k$ tel que $(i, k)$ et $(j, k)$ soit voisins.
    Je vais revoir ça quand j'aurais le temps (j'avais pas relu le 1er message de M65: excuse !).
  • Salut.
    @LOU16, je viens de comprendre tes messages précédents (suis pas encore au point en algèbre linéaire !).

    Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!