Score d'un tournoi (invariant ?)
Bonjour
Dans un tournoi, ce que j'appelle le score est le multiset des degrés sortant de chaque sommet. Je pense que deux tournois peuvent avoir le même score sans être isomorphes (les mêmes à permutation des sommets près)
Question 1, est-ce bien le cas ?
Question 2, si j'inverse les flèches d'un circuit et seulement celles-ci, je ne modifie pas le score, appelons cette opération ou une permutation des sommets, des "bidouilles",
Est-ce que la relation d’équivalence engendrée par les bidouilles est "avoir le même score" ?
Merci.
Dans un tournoi, ce que j'appelle le score est le multiset des degrés sortant de chaque sommet. Je pense que deux tournois peuvent avoir le même score sans être isomorphes (les mêmes à permutation des sommets près)
Question 1, est-ce bien le cas ?
Question 2, si j'inverse les flèches d'un circuit et seulement celles-ci, je ne modifie pas le score, appelons cette opération ou une permutation des sommets, des "bidouilles",
Est-ce que la relation d’équivalence engendrée par les bidouilles est "avoir le même score" ?
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
\begin{align*}
ba,~bc,~bd,~cb,~cd,~ db,~dc,~ ab,\\
ba,~bc,~bd,~cb,~cd,~ db,~dc,~ ac\phantom{,}
\end{align*}
J'ai bricolé cet exemple qui n'est sûrement pas le plus simple. Il s'agit de deux tournois dont la suite croissante des degrés sortants est $(1,1,2,3,4,4)$ et dont les matrices d'adjacence sont, avec ma convention $"-1=0"$:
$$ \begin{pmatrix} 0&1&1&0&1&1 \\0&0&1&1&1&1\\ 0&0&0&1&1&1\\1&0&0&0&1&0 \\0&0&0&0&0&1 \\0&0&0&1&0&0 \\ \end{pmatrix}\quad \text{et} \quad \begin{pmatrix} 0&1&0&1&1&1\\ 0&0&1&1&1&1 \\1&0&0&0&1&1 \\0&0&1&0&1&0 \\0&0&0&0&0&1\\ 0&0&0&1&0&0 \\ \end{pmatrix} $$
$$\xymatrix {&\bullet 1 \ar[r] \ar[ld] \ar[dd] \ar [rdd]& \bullet 2 \ar [lld] \ar[ldd] \ar[dd] \ar [rd]\\ \bullet 3 \ar[rrd] \ar[rrr] \ar[rd] &&& \bullet 4 \ar [llu] \ar [lld] \\ &\bullet 5 \ar [r]& \bullet 6\ar[ur] \\ } \quad \quad \xymatrix{ &\bullet 1 \ar[r] \ar [rrd] \ar[dd] \ar[rdd] & \bullet 2 \ar [lld] \ar[ldd] \ar[dd] \ar [rd] \\ \bullet 3 \ar[ru] \ar[rd] \ar[rrd] &&& \bullet 4 \ar[lll] \ar [lld] \\ & \bullet 5 \ar[r] & \bullet 6\ar [ru] \\ }$$
Ces deux tournois ne sont pas isomorphes:
Dans le premier tournoi, un arc est dirigé du sommet $3$ (unique sommet de degré sortant $3$) vers le sommet $4$ (unique sommet de degré sortant $2$), et ce n'est plus le cas dans le second tournoi.
Examinons les polynômes caractéristiques. Celui de $G_0$ : Et celui de $G$ : ils diffèrent
- Scénario 1, Je fais 2 groupes de 6 ; dans chaque groupe, toutes les équipes se rencontrent. Toutes les équipes ont fait 5 matches
- Scénario 2 : Je positionne les 12 équipes dans une grille 4 lignes x 3colonnes, chaque équipe rencontre les autres équipes de la même ligne (2 matches) puis les autres équipes de la même colonne (3 nouveaux matches)
Dans les 2 scénarios, toutes les équipes ont fait 5 matches. Mais les 2 graphes ne sont pas isomorphes (en particulier le 1er est non connexe)
Et comme la question 2 est une reformulation de la question 1...
Ici moins bourrin que mon DERNIER post, promis juré. Je vais réaliser sur le tournoi d'ordre 5 en haut à droite du truc attaché une bidouille (ta terminologie) sur le circuit $(1,4,3)$ c.a.d. une opération switching de type II, terminologie de Anstee (cf le pdf pointé de mon PREMIER post) http://www.les-mathematiques.net/phorum/read.php?34,1832448,1832520#msg-1832520 La bidouille en question Of course, conservation des scores (et des degrés entrants) Mais les 2 graphes ne sont pas isomorphes. Toujours le coup des polynômes caractéristiques. Le résultat que tu vises (le score est l'invariant caractéristique des bidouillages) constitue le corollaire 3.9 de Anstee. Sauf erreur de ma part (je vois assez souvent ce type de couverture sur ce noble forum et je me permets donc de l'utiliser).
Ici deux tournois de même polynôme caractéristique mais de scores différents Deux tournois de même polynôme caractéristique, de même score mais non isomorphes Pour voir qu'ils sont non isomorphes, je copie sur LOU16 : le degré sortant 1 est veuf. Dans $G_1$, il s'agit de $5_{G_1}$ avec un arc vers $1_{G_1}$ de degré sortant 3. Tandis que dans $G_2$, il s'agit de $3_{G_2} \to 1_{G_2}$ de degré sortant 2.
Bon, j'arrête de faire joujou (j'ai du boulot, que je dis).
Les tournois moi aussi m'amusent beaucoup, par exemple on peut associer à tout score une expression bien parenthésée meme si on autorise le score à ne pas être une liste croissante. On retire à ce score le vecteur (0,1,2,3,....,n) et je vous laisse deviner quelle expression bien parenthèsée on lui associe (expression en question étant un mot de trois lettre, ), ( et une troisième lettre pour séparer les parenthèses, par exemple x.
exemple (1,2,1,2) donne (x(x x) x)