Score d'un tournoi (invariant ?) — Les-mathematiques.net The most powerful custom community solution in the world

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.

Réponses

  • Si $a,b,c,d$ sont les 4 joueurs, il me semble que les deux tournois suivants ont le mème score $1,3,2,2 $ sans être isomorphes.
    \begin{align*}
    ba,~bc,~bd,~cb,~cd,~ db,~dc,~ ab,\\
    ba,~bc,~bd,~cb,~cd,~ db,~dc,~ ac\phantom{,}
    \end{align*}
  • Un tournois est un graphe asymétrique et complet, or ces deux graphes ne sont pas asymétriques puisque on a bc et cb, chacun est censé jouer une fois et une seule fois contre tous les autres, dans tes exemples b et c jouent deux parties l'un contre l'autre.
  • Bonjour,

    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.
  • Bon bref, un tournoi est une matrice antisymetrique a coeficients $\pm 1$ hors diagonale: suffisait de le dire...
  • Un peu dans le style de LOU16 mais en bien plus bourrin. Deux petites fonctions :
    [color=#000000]TournoiAleatoire := function(n)
      return Digraph < n |    {@ Random(Booleans()) select [i,j] else [j,i] : i in [1..j-1], j in [1..n] @} > ;
    end function ;
    
    Score := func < G | Sort([OutDegree(v) : v in VertexSet(G)]) > ;
    [/color]
    
    On tire un tournoi $G_0$ d'ordre $n=6$ au hasard :
    [color=#000000]> n := 6 ;                                                        
    > G0 := TournoiAleatoire(n) ;
    > G0 ;
    Digraph
    Vertex  Neighbours
    
    1       5 ;
    2       1 6 ;
    3       1 2 4 5 ;
    4       1 2 5 6 ;
    5       2 ;
    6       1 3 5 ;
    [/color]
    
    Bourrin, quand tu me tiens : je tire au hasard des tournois d'ordre $n$ et je retiens ceux de même score que $G_0$
    [color=#000000]> L := [] ;                                                       
    > time for dummy := 1 to 10^3 do
    time|for> G := TournoiAleatoire(n) ;
    time|for> if Score(G) eq Score(G0) then Append(~L, G) ; end if ;
    time|for> end for ;
    Time: 0.100
    > #L ;
    95
    [/color]
    
    Est ce que la récolte est bonne ?
    [color=#000000]> [IsIsomorphic(G0, G) : G in L] ;
    [ false, false, false, false, false, false, false, true, false, true, false, false, true, false, true, false, 
    true, true, false, false, false, false, true, false, false, true, false, false, false, false, false, false, 
    false, false, true, true, false, false, false, false, false, true, false, false, false, true, true, true, false,
    false, true, true, false, false, false, false, false, false, true, true, false, false, false, true, false, 
    false, false, false, true, false, true, false, true, false, false, true, false, true, true, true, false, true, 
    false, false, false, false, false, true, false, false, true, true, false, false, true ]
    [/color]
    

    Examinons les polynômes caractéristiques. Celui de $G_0$ :
    [color=#000000]> AdjG0 := AdjacencyMatrix(G0) ;
    > AdjG0 ;
    [0 0 0 0 1 0]
    [1 0 0 0 0 1]
    [1 1 0 1 1 0]
    [1 1 0 0 1 1]
    [0 1 0 0 0 0]
    [1 0 1 0 1 0]
    > Chi0<X> := CharacteristicPolynomial(AdjG0) ;
    > Chi0 ;
    X^6 - 4*X^3 - 3*X^2 - 2*X
    [/color]
    
    Et celui de $G$ : ils diffèrent
    [color=#000000]> G := L[1] ;                                                     
    > G ;
    Digraph
    Vertex  Neighbours
    
    1       2 3 4 6 ;
    2       5 ;
    3       2 ;
    4       2 3 ;
    5       1 3 4 ;
    6       2 3 4 5 ;
    
    > AdjG := AdjacencyMatrix(G) ;                                    
    > AdjG ;                                    
    [0 1 1 1 0 1]
    [0 0 0 0 1 0]
    [0 1 0 0 0 0]
    [0 1 1 0 0 0]
    [1 0 1 1 0 0]
    [0 1 1 1 1 0]
    > Chi<X> := CharacteristicPolynomial(AdjG) ;
    > Chi ;
    X^6 - 4*X^3 - 4*X^2 - 3*X - 1
    [/color]
    
  • J'ai 12 équipes, numérotées de 1 à 12

    - 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...
    Tu me dis, j'oublie. Tu m'enseignes, je me souviens. Tu m'impliques, j'apprends. Benjamin Franklin
  • @lesmathspointclaires
    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
    [color=#000000]> G1 := Digraph < 5 | [1,4],[1,5], [2,1],[2,3], [3,1], [4,2],[4,3], [5,2],[5,3],[5,4] > ;
    > G1 ;
    Digraph
    Vertex  Neighbours
    
    1       4 5 ;
    2       1 3 ;
    3       1 ;
    4       2 3 ;
    5       2 3 4 ;
    [/color]
    
    La bidouille en question
    [color=#000000]> G2 := G1 ;                                                                             
    > RemoveEdges(~G2, [[1,4],[4,3],[3,1]]) ;
    > AddEdges(~G2, {[4,1],[3,4],[1,3]}) ;
    > G2 ;
    Digraph
    Vertex  Neighbours
    
    1       3 5 ;
    2       1 3 ;
    3       4 ;
    4       1 2 ;
    5       2 3 4 ;
    [/color]
    
    Of course, conservation des scores (et des degrés entrants)
    [color=#000000]> Score(G1) ;                                                                            
    [ 1, 2, 2, 2, 3 ]
    > Score(G2) ;
    [ 1, 2, 2, 2, 3 ]
    > Sort([InDegree(v) : v in VertexSet(G1)]) ;
    [ 1, 2, 2, 2, 3 ]
    > Sort([InDegree(v) : v in VertexSet(G2)]) ;
    [ 1, 2, 2, 2, 3 ]
    [/color]
    
    Mais les 2 graphes ne sont pas isomorphes. Toujours le coup des polynômes caractéristiques.
    [color=#000000]> IsIsomorphic(G1, G2) ;
    false
    > A1 := AdjacencyMatrix(G1) ;                                                            
    > A1 ;
    [0 0 0 1 1]
    [1 0 1 0 0]
    [1 0 0 0 0]
    [0 1 1 0 0]
    [0 1 1 1 0]
    > A2 := AdjacencyMatrix(G2) ;
    > A2 ;
    [0 0 1 0 1]
    [1 0 1 0 0]
    [0 0 0 1 0]
    [1 1 0 0 0]
    [0 1 1 1 0]
    > CharacteristicPolynomial(A1) ;           
    X^5 - 4*X^2 - 4*X - 1
    > CharacteristicPolynomial(A2) ;                                                         
    X^5 - 4*X^2 - 3*X - 2
    [/color]
    
    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).88020
  • ouaouh merci Claude, et merci Lourran et LOU16!! je n ai lu pour l instant que la page extraite du livre qui il me semble répond à la question 2! je lis le reste plus en detail mais je ne pouvais miderer mon enthousiasme en attendant plus!
  • @lesmathspointclaires, @LOU16 C'est amusant les tournois, je trouve. Je crois comprendre que tester si deux tournois sont isomorphes, ce n'est pas de la tarte, cf par exemple http://pdfs.semanticscholar.org/7b7c/3f8ce71a7857a4f816b65592e6708e10be21.pdf et http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.7785&rep=rep1&type=pdf

    Ici deux tournois de même polynôme caractéristique mais de scores différents
    [color=#000000]> n := 5 ;
    > A1 := Matrix(n,n, [
    >     [ 0, 1, 0, 1, 1 ],
    >     [ 0, 0, 1, 1, 1 ],
    >     [ 1, 0, 0, 0, 1 ],
    >     [ 0, 0, 1, 0, 1 ],
    >     [ 0, 0, 0, 0, 0 ]]) ;
    > A2 := Matrix(n,n, [
    >     [ 0, 0, 0, 1, 0 ],
    >     [ 1, 0, 0, 0, 1 ],
    >     [ 1, 1, 0, 1, 1 ],
    >     [ 0, 1, 0, 0, 0 ],
    >     [ 1, 0, 0, 1, 0 ]]) ;
    > Chi1<X> := CharacteristicPolynomial(A1) ;   Chi2<X> := CharacteristicPolynomial(A2) ;
    > assert Chi1 eq Chi2 ;
    > Chi1 ;
    X^5 - 2*X^2 - X
    > G1 := Digraph < n | A1 > ;
    > G1 ;
    Digraph
    Vertex  Neighbours
    1       2 4 5 ;
    2       3 4 5 ;
    3       1 5 ;
    4       3 5 ;
    5       ;
    > G2 := Digraph < n | A2 > ;
    > G2 ;
    Digraph
    Vertex  Neighbours
    1       4 ;
    2       1 5 ;
    3       1 2 4 5 ;
    4       2 ;
    5       1 4 ;
    > Score(G1) ;
    [ 0, 2, 2, 3, 3 ]
    > Score(G2) ;
    [ 1, 1, 2, 2, 4 ]
    [/color]
    
    Deux tournois de même polynôme caractéristique, de même score mais non isomorphes
    [color=#000000]> n := 6 ;
    > A1 := Matrix(n,n, [
    >     [ 0, 1, 1, 0, 0, 1 ],
    >     [ 0, 0, 0, 1, 1, 1 ],
    >     [ 0, 1, 0, 0, 1, 1 ],
    >     [ 1, 0, 1, 0, 1, 0 ],
    >     [ 1, 0, 0, 0, 0, 0 ],
    >     [ 0, 0, 0, 1, 1, 0 ]]) ;
    > A2 := Matrix(n,n, [
    >     [ 0, 1, 0, 0, 1, 0 ],
    >     [ 0, 0, 1, 0, 1, 1 ],
    >     [ 1, 0, 0, 0, 0, 0 ],
    >     [ 1, 1, 1, 0, 0, 0 ],
    >     [ 0, 0, 1, 1, 0, 1 ],
    >     [ 1, 0, 1, 1, 0, 0 ]]) ;
    > Chi1<X> := CharacteristicPolynomial(A1) ;   Chi2<X> := CharacteristicPolynomial(A2) ;
    > assert Chi1 eq Chi2 ;
    > Chi1 ;
    X^6 - 7*X^3 - 9*X^2 - 7*X - 2
    > G1 := Digraph < n | A1 > ;
    > G1 ;
    Digraph
    Vertex  Neighbours
    1       2 3 6 ;
    2       4 5 6 ;
    3       2 5 6 ;
    4       1 3 5 ;
    5       1 ;
    6       4 5 ;
    > G2 := Digraph < n | A2 > ;
    > G2 ;
    Digraph
    Vertex  Neighbours
    1       2 5 ;
    2       3 5 6 ;
    3       1 ;
    4       1 2 3 ;
    5       3 4 6 ;
    6       1 3 4 ;
    > Score(G1) ;
    [ 1, 2, 3, 3, 3, 3 ]
    > Score(G2) ;
    [ 1, 2, 3, 3, 3, 3 ]
    > assert not IsIsomorphic(G1,G2) ;
    [/color]
    
    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).
  • Je crois que c'est un problème ouvert de savoir si on peut tester l'isomorphisme de deux tournois en un temps polynomial, il me semble que c'est equivalent à "graph iso"

    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)
  • Je vais parler d'un très joli problème relatif aux tournois... dans un nouveau sujet, c'est en fait son investigation qui est à l'origine de ma question ici...
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!