Arbre couvrant — Les-mathematiques.net The most powerful custom community solution in the world

Arbre couvrant

Bonjour,

Je n'arrive pas à comprendre la notion d'arbre couvrant. J'ai compris la connexité, on doit toujours pouvoir relier 2 points. Mais pas l'arbre couvrant.99738
99740

Réponses

  • Je viens de lire Wikipédia.
    Un arbre couvrant, c'est un arbre, qui connecte tous les sommets du graphe.
    Et un arbre, c'est quoi ? c'est un graphe , non-orienté, acyclique et connexe.

    Un graphe c'est quoi ? non-orienté, c'est quoi ; acyclique, c'est quoi ; connexe, c'est quoi ?

    Chaque mot est précis... quel mot n'est pas clair ?
  • En fait la définition donnée était pas celle de wikipédia mais :

    $A$ sont les arêtes et $S$ les sommets/
    On appelle arbre un graphe connexe dont dont le nombre d'arêtes est égal au nombre de sommets moins un. Si $\Gamma=(S,A)$ est un graphe connexe, on appelle arbre couvrant $\Gamma$ un arbre de la forme $(S,B)$ avec $B \subset A$.


    Je ne comprends pas cette définition.
  • Bonjour,

    Quel mot ne connais tu pas ? A moins que tu aies besoin du mode d'emploi d'un dictionnaire ?

    Cordialement,

    Rescassol
  • Lourran : sujet

    J'essaie de comprendre le langage mathématique mais je n'y parviens pas. Je souhaite traiter uniquement les questions de compréhension du texte qui ne nécessitent aucun bagage mathématique.
  • Un arbre de la forme $(S,B)$ avec $B \subset A$ je ne comprends pas ce que ça veut dire.
  • Bonjour,

    $A$ est l'ensemble des arêtes du graphe initial et $B \subset A$ signifie que $B$ est une partie des arêtes du graphe initial. Qu'est ce qui n'est pas clair ?

    Cordialement,

    Rescassol
  • Merci j'essaie de les faire.
  • Le nombre d'arêtes est-il égal au nombre de sommets moins un ?
  • Merci je viens de me rendre compte de mon erreur :-X
  • Voici ce que j'ai trouvé.99760
    f.png 306.9K
  • Je ne comprends pas ce que sont 5 et 6.
  • Ah non j'ai fait des erreurs les sommets ne bougent pas d'après la définition.
  • Bonjour,

    Il manque ceux contenant la diagonale.
    D'autre part les numéros 5 et 6 sont incompréhensibles..
    On doit voir quelles arêtes de $A$ tu choisis pour construire $B$.

    Cordoialement,

    Rescassol
  • Ceux de 1 à 4 sont tous ceux qui n'ont pas l'arête en diagonale.
    Il ne te reste plus qu'à trouver ceux qui ont cette diagonale. C'est facile : il te suffit de prendre la diagonale et deux autres arêtes...
  • Parmi les arbres, il y a les arbres en forme de Y : en tout 4 sommets, et un des sommets est relié directement aux 3 autres. (le dessin d'un arbre avec 1 tronc et 2 branches en fait !)

    Et ces arbres correspondent à la définition 'arbre couvrant'.
  • J'ai réussi j'en trouve 8.

    Je n'arrive pas à comprendre la notion d'automorphisme d'un graphe, pourquoi sur l'exemple on peut échanger que u et v.99768
    1.png 120.5K
  • Tu voulais dire $v$ et $w$, sans doute.

    Un automorphisme de graphe envoie une arête sur une arête, un chemin sur un chemin de même longueur, il préserve la valence (le nombre d'arêtes incidentes), etc.

    Voici un argument (trivial) pour la valence : soit $\sigma$ un automorphisme d'un graphe $\Gamma$ ; soit $s$ un sommet et soit $V_s=\{t_1,\dots,t_v\}$ l'ensemble des sommets liés à $s$ par une arête de $\Gamma$ (ainsi la valence de $s$ est $v$). Alors l'ensemble des sommets liés à $\sigma(s)$ est $\{\sigma(t_1),\dots,\sigma(t_v)\}$. En effet, si $u$ est un sommet, il existe $t$ tel que $t=\sigma(u)$ donc $\{\sigma(s),u\}$ est une arête ssi $\{\sigma(s),\sigma(t)\}$ en est une ssi $\{s,t\}$ en est une ssi $t$ est l'un des $t_i$. Par conséquent, la valence de $\sigma(s)$ est encore $v$ (les $\sigma(t_i)$ sont tous distincts).

    Dans l'exemple, soit $\sigma$ un automorphisme du graphe.
    D'abord, il fixe $u$ parce que c'est le seul point de valence $3$.
    Ensuite, un automorphisme $\sigma$ fixe $s$ parce que c'est l'unique point différent de $u$ tel qu'il existe un sommet $x$ tel que $\{u,x\}$ et $\{x,s\}$ sont des arêtes : un automorphisme envoie nécessairement $s$ sur un point $\ne u$ (pourquoi ?) tel que $\{\sigma(u),\sigma(t)\}=\{u,\sigma(t)\}$ et $\{\sigma(t),\sigma(u)\}$ sont des arêtes, si bien que $\sigma(s)=s$ par la caractérisation précédente ($x=\sigma(t)$).
    Enfin, $\sigma(t)=t$ car c'est l'unique point relié à $s$, qui est fixe : $\{\sigma(s),\sigma(t)\}=\{s,\sigma(t)\}$ est une arête et $\{s,t\}$ est l'unique arête qui contient $s$.
    Ainsi, un automorphisme de graphe ne peut qu'échanger $v$ et $w$.
  • Oula c'est trop compliqué pour moi je suis perdu.

    Je voulais juste comprendre ce que veux dire la définition avec les permutations en langage pour les nuls sans théorie. Car je sais que la théorie des automorphismes de graphe n'est pas de mon niveau. Je voulais juste comprendre la définition sur un graphe simple.
  • Peux-tu écrire les quatre arêtes du graphe ?
  • Dans le rapport du jury, ils ont dit qu'aucun candidat n'a réussi la moindre question dans cette partie sur les groupes d'automorphismes.

    Math Coss désolé mais mon cerveau est incapable de comprendre des choses aussi difficiles.
    Si j'arrive à avoir un concours, c'est en réussissant les questions faciles et des questions de difficulté moyenne. Il y a des choses hors de ma portée.

    Oui $\{s,t\}$ , $\{t,u \}$ , $\{u,v\}$ , $\{u,w\}$.
  • Soit $\sigma$ un automorphisme de ce graphe, alors $\{\sigma(s),\sigma(t)\}$, $\{\sigma(t),\sigma(u)\}$, $\{\sigma(u),\sigma(v)\}$ et $\{\sigma(u),\sigma(w)\}$ sont les mêmes
    quatre arêtes que celles que tu viens de donner.
    Quel est le seul sommet qui appartient à trois arêtes ? Que peut-on en déduire concernant $\sigma(u)$ ?
  • Ah oui astucieux. $\sigma(u)$ apparaît 3 fois, donc $\sigma(u)=u$.

    Mais comment montrer qu'il y a un échange entre $u$ et $v$ ? Pourquoi $s$ et $t$ ne sont pas échangés ?
  • Math Coss a déjà tout expliqué, mais continuons quand même.
    La seule arête qui ne contient pas $u$ est donc $\{s,t\}=\{\sigma(s),\sigma(t)\}$. Donc $\sigma$ fixe $s$ et $t$ ou échange les deux sommets (pour l'instant).
    Quelle est la seule arête qui contient un $u$ et qui a un sommet commun à cette arête ?
    Que peut-on en déduire concernant $\sigma(t)$ ? Par conséquent quel sommet est $\sigma(s)$ ?
  • Bonjour,

    > Ah oui astucieux. $\sigma(u)$ apparaît 3 fois.donc .$\sigma(u)=u$

    Encore une fois, ce n'est pas astucieux, on n'a pas le choix, il faut faire ça, ce doit être évident.
    Tout se fait en comptant les occurrences des sommets dans les arêtes, c'est à dire en raisonnant sur le degré des sommets.
    C'est un peu comme un sudoku.

    Cordialement,

    Rescassol
  • Je n'ai pas réussi à comprendre le message de Math Coss un peu trop technique.

    Mais j'ai enfin compris. Après $\{s,t\} = \{ \sigma(s),\sigma(t) \}$ donc c'est l'arrête $\{t,u\}$. Donc $\sigma(t)=t$

    J'ai une autre question. Je n'arrive pas à faire cette question.

    Je dirais 6 choix pour $x_0$ mais après 5 choix pour $x_1$ non ?99808
    gr.png 69.3K
  • N'importe quoi

    Si tu pars d'un élément $x_0 = s_i$, tu as 3 possibilités pour $x_1$, puis combien pour $x_2$? puis combien pour $x_3$
    Conclusion?
  • Bonjour,

    Bon sang, ouvre les yeux !!! Tu vois beaucoup de sommets de degré $5$ ?

    Cordialement,

    Rescassol
  • Merci en effet je n'avais pas pensé au fait que de chaque sommet, partent 3 arêtes.

    Donc 6 choix pour $x_0$ puis 3 choix pour $x_1$ puis 2 choix par $x_2$ car on ne peut pas revenir en arrière et enfin 2 choix pour $x_0$.

    Ce qui donne $6 \times 3 \times 2 \times 2 =72$ choix possibles.

    Intéressant cet exercice. On peut le donner a des lycéens.
  • Bonjour
    OShine a écrit:
    Intéressant cet exercice. On peut le donner a des lycéens.

    C'est pour ça que tu as eu autant de difficultés à le résoudre :-D

    Cordialement,

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