Score d'un tournoi (invariant ?)

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.

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]

@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).

@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).