290
21 Matrices aléatoires
sont les valeurs distinctes prises par ces indices, et on note t leur nombre. Les
arêtes, du multi-graphe orienté sont les liaisons (i k , i k+1 ) avec 1 k r − 1.
Elles peuvent avoir une multiplicité et sont orientées. De plus ce multi-graphe
orienté est cyclique de longueur r + 1. Si on note t le nombre de sommets
distincts, on dit qu’il s’agit d’un multi-graphe orienté G(r, t). Deux multigraphes orientés G(r, t) sont équivalents lorsque qu’on peut passer de l’un à
l’autre en permutant les indices. Des multi-graphes orientés G(r, t) équivalents
donnent la même valeur à E(M i1i2 · · · M irir+1 ), notée E(M G ). Il y a
n(n − 1) · · · (n − t + 1)
multi-graphes orientés G(r, t) dans chaque classe d’équivalence (nombre d’arrangements de t objets parmi n). Chaque classe d’équivalence contient un
représentant pour lequel les t valeurs distinctes prises par les indices i 1 , . . . , i r
sont successivement 1, . . . , t. Afin de calculer les contributions, on distingue
trois types de multi-graphes orientés G(r, t) détaillés ci-après. Le type est
constant sur chaque classe (c’est une propriété de la classe).
1
2
3
Fig. 21.2. Multi-graphe orienté associé à E(M12M21M13M31). On a r = 4, t = 3,
i1 = i3 = 1, i2 = 2, i4 = 3. Les arêtes successives sont 12, 21, 13, 31. Chaque arête
présente, ainsi que l’arête de sens opposé, ne l’est qu’une fois. Le graphe non orienté
squelette est l’arbre 2 ↔ 1 ↔ 3. Ce multi-graphe orienté est donc de type 1.
— type 1 : ceux pour qui chaque arête présente, ainsi que l’arête de
sens opposé, ne l’est qu’une fois, et le graphe non orienté squelette
obtenu en effaçant les orientations et les multiplicités des arêtes est
un arbre (c’est-à-dire qu’il n’a pas de cycles). C’est le cas par exemple
de E(M 12 M 21 M 13 M 31 ) = E(M
2
12 )E(M
2
13 ) = 1, voir figure 21.2. Un
exemple plus long est donné par la figure 21.3 ;
— type 2 : ceux pour qui une arête au moins n’apparaît qu’une seule
fois et l’arête de sens opposé n’apparaît pas, comme par exemple
E(M 12 M 23 M 31 ) = E(M 12 )E(M 23 )E(M 31 ) = 0, voir figure 21.3 ;
— type 3 : ceux qui ne sont ni de type 1 ni de type 2. C’est le cas par
exemple de E(M 12 M 21 M 12 M 21 ) = E(M
4
12 ) > 0 car l’arête 12 (ainsi
que l’arête 21) apparaît exactement deux fois. Un autre exemple est
donné par E(M 12 M 21 M 13 M 32 M 23 M 31 ) = E(M
2
12 )E(M
2
13 )E(M
2
23 ) = 1,
car le graphe non orienté squelette associé est le cycle 1 ↔ 2 ↔ 3 ↔ 1.
Ces deux exemples sont illustrés par la figure 21.3.
21 Matrices aléatoires
sont les valeurs distinctes prises par ces indices, et on note t leur nombre. Les
arêtes, du multi-graphe orienté sont les liaisons (i k , i k+1 ) avec 1 k r − 1.
Elles peuvent avoir une multiplicité et sont orientées. De plus ce multi-graphe
orienté est cyclique de longueur r + 1. Si on note t le nombre de sommets
distincts, on dit qu’il s’agit d’un multi-graphe orienté G(r, t). Deux multigraphes orientés G(r, t) sont équivalents lorsque qu’on peut passer de l’un à
l’autre en permutant les indices. Des multi-graphes orientés G(r, t) équivalents
donnent la même valeur à E(M i1i2 · · · M irir+1 ), notée E(M G ). Il y a
n(n − 1) · · · (n − t + 1)
multi-graphes orientés G(r, t) dans chaque classe d’équivalence (nombre d’arrangements de t objets parmi n). Chaque classe d’équivalence contient un
représentant pour lequel les t valeurs distinctes prises par les indices i 1 , . . . , i r
sont successivement 1, . . . , t. Afin de calculer les contributions, on distingue
trois types de multi-graphes orientés G(r, t) détaillés ci-après. Le type est
constant sur chaque classe (c’est une propriété de la classe).
1
2
3
Fig. 21.2. Multi-graphe orienté associé à E(M12M21M13M31). On a r = 4, t = 3,
i1 = i3 = 1, i2 = 2, i4 = 3. Les arêtes successives sont 12, 21, 13, 31. Chaque arête
présente, ainsi que l’arête de sens opposé, ne l’est qu’une fois. Le graphe non orienté
squelette est l’arbre 2 ↔ 1 ↔ 3. Ce multi-graphe orienté est donc de type 1.
— type 1 : ceux pour qui chaque arête présente, ainsi que l’arête de
sens opposé, ne l’est qu’une fois, et le graphe non orienté squelette
obtenu en effaçant les orientations et les multiplicités des arêtes est
un arbre (c’est-à-dire qu’il n’a pas de cycles). C’est le cas par exemple
de E(M 12 M 21 M 13 M 31 ) = E(M
2
12 )E(M
2
13 ) = 1, voir figure 21.2. Un
exemple plus long est donné par la figure 21.3 ;
— type 2 : ceux pour qui une arête au moins n’apparaît qu’une seule
fois et l’arête de sens opposé n’apparaît pas, comme par exemple
E(M 12 M 23 M 31 ) = E(M 12 )E(M 23 )E(M 31 ) = 0, voir figure 21.3 ;
— type 3 : ceux qui ne sont ni de type 1 ni de type 2. C’est le cas par
exemple de E(M 12 M 21 M 12 M 21 ) = E(M
4
12 ) > 0 car l’arête 12 (ainsi
que l’arête 21) apparaît exactement deux fois. Un autre exemple est
donné par E(M 12 M 21 M 13 M 32 M 23 M 31 ) = E(M
2
12 )E(M
2
13 )E(M
2
23 ) = 1,
car le graphe non orienté squelette associé est le cycle 1 ↔ 2 ↔ 3 ↔ 1.
Ces deux exemples sont illustrés par la figure 21.3.