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.
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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
$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.
Quel mot ne connais tu pas ? A moins que tu aies besoin du mode d'emploi d'un dictionnaire ?
Cordialement,
Rescassol
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.
$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
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
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...
Et ces arbres correspondent à la définition 'arbre couvrant'.
Je n'arrive pas à comprendre la notion d'automorphisme d'un graphe, pourquoi sur l'exemple on peut échanger que u et v.
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$.
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.
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\}$.
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)$ ?
Mais comment montrer qu'il y a un échange entre $u$ et $v$ ? Pourquoi $s$ et $t$ ne sont pas échangés ?
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)$ ?
> 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
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 ?
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?
Bon sang, ouvre les yeux !!! Tu vois beaucoup de sommets de degré $5$ ?
Cordialement,
Rescassol
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.
C'est pour ça que tu as eu autant de difficultés à le résoudre :-D
Cordialement,
Rescassol