Centrale Informatique optionnelle MP 2020

Thème de l'épreuve Un système de vote
Principaux outils utilisés programmation OCaml, graphes, logique
Mots clefs vote, préférence, Condorcet, Schulze, satisfiabilité

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Rapport du jury

(télécharger le PDF)
        

Énoncé obtenu par reconnaissance optique des caractères


Option informatique

T

MP
CONCOURS CENTRALE-SUPÉLEC 4 heures Calculatrice autorisée

2020

Un système de vote

Le seul langage de programmation autorisé dans cette épreuve est Caml.

Toutes les fonctions des modules Array et List, ainsi que les fonctions de la 
librairie standard (celles qui
s'écrivent sans nom de module, comme max ou incr ainsi que les opérateurs comme 
EUR) peuvent être librement
utilisées. Les candidats ne devront faire appel à aucun autre module.

En Caml, les matrices d'entiers sont représentées par des tableaux de tableaux, 
c'est-à-dire par le type int
array array. L'expression m.(i).(j) permet d'accéder au coefficient de la i-ème 
ligne et de la j-ième colonne
de la matrice m. Dans le texte, en dehors du code Caml, ce coefficient sera 
noté m{i, 5]. On rappelle les définitions
suivantes :

-- Array.make matrix : int -> int -> 'a -> 'a array array est telle que 
Array.make matrix n p v
renvoie une matrice de n lignes et p colonnes dont toutes les cases contiennent 
la valeur v ;

-- Array.length : 'a array -> int est telle que Array.length tab renvoie le 
nombre d'éléments du ta-
bleau tab. Si tab est une matrice, c'est le nombre de lignes de tab ;

-- min : la -> 'a -> 'a renvoie le minimum des deux valeurs en argument ;

-- max : la -> 'a -> 'a renvoie le maximum des deux valeurs en argument ;

-- l'opérateur @ concatène deux listes. Par exemple, [2; 0] @ [4; 2] renvoie 
[2; O0; 4; 2].

Dans ce problème, les graphes ont un ensemble de sommets de la forme 
{0,1,...,n--1} et sont orientés complets
et pondérés par des entiers : pour tout couple (i,j) de sommets distincts, il 
existe un arc de à à j de poids
M; EUR Z. Le graphe est représenté par sa matrice d'adjacence M = (mi; ;Joci 
jen-1 avec la convention que

m;; = 0 pour tout sommet à (il n'y a pas d'arc d'un sommet vers lui-même).

I Vote par préférence

Nous considérons une élection, à laquelle se présentent n candidats. Chaque 
électeur inscrit sur son bulletin
l'ensemble des candidats (tous les candidats sont classés), par ordre de 
préférence. L'ensemble des bulletins est
rassemblé dans une urne. Le nombre de votants est noté p, l'urne contient donc 
p bulletins.

Les trois types de données suivants sont utilisés pour représenter un vote :

-- type candidat = int ;; chaque candidat est désigné par un numéro de 0 à n--1;
-- type bulletin = candidat list ;; un bulletin de vote est une liste 
(ordonnée) de candidats ;
-- type urne = bulletin list ;; une urne est un ensemble de bulletins de vote.

Par exemple, s'il y a trois candidats et qu'un électeur préfère le candidat 2, 
puis le candidat 0 et enfin considère
que le candidat 1 est le moins souhaitable, son bulletin de vote sera [2; 0; 1].

Une fois le vote effectué, on compare les résultats de deux candidats 
particuliers à et j en comptant le nombre
de bulletins qui classent le candidat à avant le candidat j. On exprime le 
résultat de la comparaison entre les
candidats à et j en calculant la différence entre le nombre de bulletins de 
vote qui placent à avant j et le nombre
de ceux qui placent j avant ti.

IA --- Premier exemple

On considère une élection avec trois candidat et trois votants : n = 3, p -- 3. 
Les bulletins sont [2; 0; 1],
[2; 1; Olet [1; 2; 0]. La comparaison entre le candidat numéro 0 et le candidat 
numéro 1 donne --1 car le
candidat 0 est placé une fois avant le candidat 1 et deux fois après.

Q 1. Écrire une fonction duel : candidat -> candidat -> urne -> int, telle que 
duel i j u renvoie
la comparaison entre le candidat i et le candidat j à partir des bulletins 
contenus dans l'urne u.

On peut alors synthétiser le contenu d'une urne u en construisant le graphe de 
préférence des votants : ses
sommets correspondent aux candidats et l'arc du sommet i vers le sommet j est 
pondéré par la comparaison
entre le candidat i et le candidat j, c'est-à-dire la valeur de duel i j u.

La figure 1 donne le graphe de préférence obtenu à partir du vote de l'exemple 
1 ainsi que sa matrice d'adja-
cence M. Afin d'alléger le schéma, seuls les arcs avec un poids strictement 
positif sont représentés.

2020-03-09 18:45:48 Page 1/4 CHE
O --1 -3
M=|1 0 1
ll 9 3 1 0

Figure 1

I.B --- Deuxième exemple

On considère une élection avec trois candidats et 4 votants : n = 3, p = 4. À 
l'issue du vote, le contenu de l'urne
est [TO; 1; 2]; [1; 2; O0]; [0; 2; 1]; (0; 2; 111].

Q 2. Tracer le graphe de préférence de l'urne (en ne dessinant que les arcs 
ayant un poids strictement
positif) et donner sa matrice d'adjacence.

IC --- Construction du graphe de préférence

Q 3. Expliquer pourquoi la matrice d'adjacence d'un graphe de préférence est 
antisymétrique et pourquoi
tous ses coefficients non-diagonaux ont la même parité.

Étant donné une urne U, on note Mat(U) la matrice du graphe de préférence 
associée à cette urne.

Q 4. Écrire une fonction depouillement : int -> urne -> int array array qui 
prend en paramètres
le nombre de candidats n et une urne U et renvoie la matrice Mat(U).

ID --- Théorème de McGarvey

Le but de cette sous-partie est de démontrer le théorème de McGarvey : « Pour 
toute matrice antisymétrique à
coefficients pairs M, il existe une urne U telle que M = Mat(U). »

Soient ?, j et n trois entiers naturels tels que à < n, j  urne prenant en 
paramètre une matrice anti-
symétrique M de coefficients tous pairs et renvoyant une urne U telle que M = 
Mat(U).

Q 9. Estimer la complexité de la fonction megarvey en fonction de n, la taille 
de la matrice (c'est-à-dire le
nombre de candidats), et de q, le maximum des coefficients de la matrice.

II Recherche du vainqueur

L'objectif de cette partie est de déterminer le vainqueur, ou les vainqueurs ex 
aequo, d'un vote par préférence.

IT. À -- Vainqueur de Condorcet

On appelle vainqueur de Condorcet tout sommet tel que, dans le graphe de 
préférence, les arcs sortant de ce
sommet ont tous un poids positif ou nul. Ainsi, dans le premier exemple de la 
partie I, le candidat 2 est un
vainqueur de Condorcet.

Q 10. Expliquer pourquoi un vainqueur de Condorcet peut être qualifié de « 
vainqueur » de l'élection.
Q 11. Écrire une fonction condorcet : int array array -> candidat list prenant 
en paramètre la ma-
trice d'adjacence d'un graphe de préférence et renvoyant la liste des 
vainqueurs de Condorcet.

Q 12.  Ense plaçant dans le cas n = 8 et p = 3, construire une urne pour 
laquelle il n'existe pas de vainqueur
de Condorcet. Tracer le graphe de préférence correspondant.

II.B - Graphe intermédiaire de Schultze
À la fin du xx° siècle, Markus Schulze imagina une méthode permettant de 
déterminer un vainqueur à l'issue
de n'importe quel vote par préférence.

On appelle poids d'un chemin du graphe de préférence, le minimum des poids des 
arcs constituant ce chemin.
Ainsi, dans le premier exemple de la partie I, le poids du chemin 2 -- 0 -- 1 
est --1.

Le graphe intermédiaire de Schulze est un graphe orienté pondéré complet dont 
les sommets sont les candidats
et dont l'arc du sommet à vers le sommet j (distinct de à) est pondéré par le 
maximum des poids de tous les
chemins allant de à à 7 dans le graphe de préférence. Sa matrice d'adjacence 
est notée J.

2020-03-09 18:45:48 Page 2/4 FO) 8y-Nc-sA
Q 13. Pouriet j, candidats distincts, démontrer que 1{[i, j] est aussi le 
maximum des poids des chemins sans
boucle de ? à 7, c'est-à-dire des chemins ? = 49 -- 4, -- + -- 1, = 7 avec 
15,1,,...,2, deux à deux distincts.
Q 14.  Démontrer que min(Z{i, j|, 1[j,k]) < 1{[i, k] pour tout triplet (4, j,k) 
de sommets distincts.

Q 15. En adaptant l'algorithme de Floyd-Warshall, programmer une fonction 
intermediaire : int array
array -> int array array prenant en paramètre la matrice d'adjacence d'un 
graphe de préférence et ren-
voyant la matrice d'adjacence du graphe intermédiaire de Schulze correspondant.

Q 16. Estimez la complexité de la fonction intermediaire en fonction de n, le 
nombre de candidats.

Q 17.  Scrait-il pertinent d'utiliser l'algorithme de Dijkstra au lieu de 
l'algorithme de Floyd-Warshall ? Ar-
gumenter la réponse.

II.C --- Graphe de préférence de Schulze

Le graphe de préférence de Schulze est défini à partir du graphe intermédiaire 
de Schulze. Si Z est la matrice
d'adjacence du graphe intermédiaire de Schulze, alors la matrice d'adjacence $ 
du graphe de préférence de
Schulze est définie par S{i, j] = 1{i, 5] -- 1[j,i] pour tous entiers naturels 
à et j strictement inférieurs à n.

Q 18. Montrer que la matrice d'adjacence d'un graphe de préférence de Schulze 
est antisymétrique et que
tous ses coefficients sont pairs.

Q 19. Écrire une fonction graphe _schulze : int array array -> int array array 
qui prend en para-
mètre un graphe intermédiaire de Schulze et qui renvoie le graphe de préférence 
de Schulze correspondant.

IT.D -- Vainqueur de Schulze
Un vainqueur de Schulze est un vainqueur de Condorcet dans le graphe de 
préférence de Schulze.

Q 20. Écrire une fonction schulze : int -> urne -> candidat list qui prend en 
paramètres le nombre
de candidats et un ensemble de bulletins de vote et renvoie la liste des 
vainqueurs de Schulze.

Q 21.  Estimer la complexité de la fonction schulze en fonction du nombre de 
candidats n et du nombre de
votants p.

À partir d'un graphe de préférence de Schulze représenté par la matrice S, on 
définit la relation R$ entre les
candidats comme suit : à R4 j si et seulement S{i, j] est strictement positif.
Q 22. Montrer que la relation À$ est transitive, c'est-à-dire que pour tous 
candidats 2, 7 et k, sit Rs et
JR k alors ? Rç k.
Si I désigne la matrice d'adjacence du graphe intermédiaire, on pourra 
distinguer les cas JZ{i, j] < 1{j,k] et
Ifi, 5 > 1j, k|.
Q 23. Montrer que quelle que soit l'urne non vide considérée, il existe 
toujours au moins un vainqueur de
Schulze.

III Satisfiabilité d'une formule de logique propositionnelle

Étant donné une variable propositionnelle +, on appelle littéral, les formules 
x et -x (--x est la négation de x).
On appelle clause une disjonction de littéraux, par exemple x V --y V z est une 
clause (V signifie « ou »).

On appelle conjonction de clauses, une formule qui est la conjonction entre 
plusieurs clauses. Par exemple
(x V y V 2) A (x V --y) cest une conjonction de clauses (A signifie « et »).

On appelle interprétation une fonction qui à chaque variable propositionnelle 
associe une valeur de vérité (vrai
ou faux).

On dit qu'une conjonction de clauses est satisfiable s'il existe une 
interprétation qui la rend vraie, c'est-à-dire
qui rend vrai toutes ses clauses, autrement dit qui rend vrai au moins un 
littéral de chacune de ses clauses.

Le problème SAT consiste à déterminer si une conjonction de clauses est 
satisfable :

Entrées : Une conjonction de clauses @.
Sortie : Un booléen. Vrai si & est satisfñable. Faux sinon.

Q 24. Montrer qu'il est possible de résoudre le problème SAT avec une 
complexité en O(2"m) où n est le
nombres de variables distinctes et m le nombre de littéraux de l'entrée 
(comptés avec leurs répétitions).

On considère un vote par préférence pour lequel on a réparti les candidats en 
trois groupes :
-- un candidat c, appelé champion :
-- un ensemble À de candidats dits automatiques ;

-- un ensemble B de candidats optionnels.

2020-03-09 18:45:48 Page 3/4 FO) 8y-Nc-sA
Le problème appelé CONTROL-ADD-ALT consiste à déterminer s'il est possible 
d'éliminer un certain nombre
de candidats optionnels de façon à ce que c soit un vainqueur de Schulze de 
l'élection :

Entrées : Le candidat c. L'ensemble À. L'ensemble B. Le graphe de préférence G 
du vote sur l'ensemble des
candidats {c} U À U B. Un budget k EUR N.

Sortie : Un booléen. Vrai, s'il est possible de choisir k candidats distincts 
b,,...,b,; dans B tels que c est un
vainqueur de Schulze de l'élection en considérant uniquement l'ensemble de 
candidats {c} U À U {b,,...,b,}.
Faux sinon.

Pour obtenir le graphe de préférence de l'élection avec l'ensemble de candidats 
{c} U A U {b,,..,b;}, on prend
le graphe de préférence sur l'ensemble des candidats {c} U À U B et on supprime 
les candidats de B qui n'ont
pas été choisis (ainsi que les arrêtes entrantes et sortantes de ces candidats).

On appelle instance de CONTROL-ADD-ALT une entrée du problème CONTROL-ADD-ALT 
et instance de
SAT une entrée du problème SAT.

On considère l'algorithme « Transformation d'une formule en élection » qui, 
étant donné une instance de SAT
(c'est-à-dire une conjonction de clauses), construit une instance de 
CONTROL-ADD-ALT :

Entrées : Une conjonction de clauses
Sortie : Un candidat c (le champion), un ensemble de candidats automatiques À, 
un ensemble de candidats
optionnels B, un budget k, un graphe de préférence G sur l'ensemble de 
candidats {c} U AU B
V+
pour tout x variable propositionnelle apparaissant dans 4 faire
de dA(xV -x)
fin pour
Créer un nouveau candidat EUR
Créer un graphe G avec un seul sommet EUR
Ati, B«(
pour tout ci clause de Y faire
Créer un nouveau candidat a,, associé à cl et l'ajouter à G et à À
Ajouter à G un arc de poids +4 de à, vers c et un arc de poids --4 en sens 
inverse.
fin pour
pour tout x variable propositionnelle apparaissant dans Y faire
Créer un nouveau candidat b,, associé au littéral x et l'ajouter à G et à B
Créer un nouveau candidat b_.. associé au littéral --x et l'ajouter à G et à B
Ajouter à G deux arcs de poids +6 de c vers b, et vers b_. puis ajouter deux 
arcs de poids --6 en sens
inverse.
fin pour
pour tout couple (li, cl) avec li un littéral de + et cl une clause de Y 
contenant le littéral li faire
Ajouter à G un arc de poids +6 de b,; vers à, et un arc de poids --6 en sens 
inverse.
fin pour
Compléter le graphe G& avec des arrêtes de poids nul pour le rendre complet.
k «le nombre de variables propositionelles qui apparaissent dans w.
renvoyer c, À, B, G, k.

Q 25. Donner le graphe de préférence créé à partir de la formule (x V x) A (x V 
-x). Est-il possible de choisir
k = 1 candidat parmi x et --x de sorte que c gagne ?

Q 26. Montrer que si on peut choisir k candidats optionnels de sorte à faire 
gagner le champion, alors, pour
toute variable propositionnelle x, on a choisi x ou --x mais on n'a pas choisit 
x et --x.

Q 27. Justifier que & est satisfiable si et seulement si l'instance de 
CONTROL-ADD-ALT créée par cet
algorithme à partir de & donne une réponse positive.

On dit qu'un algorithme est en temps polynomial en un paramètre m, si la 
complexité de cet algorithme est
majorée par un polynôme en m.

Conjecture. Il n'existe pas d'algorithme en temps polynomial en nombre de 
littéraux de l'entrée qui résout

SAT.

Q 28. Montrer que, si la conjecture précédente est vraie, alors il n'existe pas 
d'algorithme en temps polyno-
mial en nombre de candidats qui résout CONTROL-ADD-ALT.

ee erFINee.e

2020-03-09 18:45:48 Page 4/4 FO) 8y-Nc-sA

Extrait du corrigé obtenu par reconnaissance optique des caractères



Centrale Informatique optionnelle MP 2020
Corrigé
Ce corrigé est proposé par William Aufort (professeur en CPGE) ; il a été relu
par Vincent Puyhaubert (professeur en CPGE) et Benjamin Monmege 
(enseignantchercheur à l'université).

Ce sujet porte sur les systèmes de vote dans lesquels l'électeur classe les 
candidats
sur son bulletin par ordre de préférence. On peut alors modéliser l'ensemble 
des votes
par une matrice traduisant, pour chaque couple de candidats, les préférences des
électeurs. Les systèmes de vote par préférence diffèrent selon le mode de 
désignation
du ou des vainqueurs de l'élection.
· La partie I permet de se familiariser avec les notions de vote et de graphe
par préférence à travers deux exemples. On y démontre également le théorème
de McGarvey, stipulant que toute matrice de préférence dont les coefficients
sont pairs correspond aux résultats d'un dépouillement. La preuve proposée est
constructive et donne également lieu à des questions de programmation.
· La partie suivante porte sur deux modes de désignation du ou des vainqueurs
d'un vote par préférence. On y étudie rapidement la méthode de Condorcet,
consistant à comparer les candidats deux par deux pour déclarer vainqueur celui 
qui est préféré à tous les autres, s'il existe. Cette méthode ne garantit hélas
pas la présence d'un vainqueur. Le reste de la partie, qui constitue le coeur
du problème, est consacré à la méthode de Schulze, qui est adaptée de 
l'algorithme de Floyd-Warshall au programme de l'option informatique. On prouve
notamment que cette méthode assure la désignation d'un vainqueur.
· Enfin, la partie III étudie un problème de décision (relativement éloigné des
deux premières parties) faisant intervenir la notion de vainqueur de Schulze.
On y démontre notamment que le problème étudié est au moins aussi difficile
que le problème de satisfiabilité d'une formule logique. Cette dernière partie 
de
logique ne peut être convenablement abordée qu'après une bonne compréhension 
des notions introduites dans la partie précédente.
L'énoncé comporte 28 questions de difficulté globalement croissante. Seul un 
quart
des questions nécessitent de programmer en OCaml, et la plupart d'entre elles 
sont
abordables. Certains passages sont en revanche plus délicats et nécessitent une 
bonne
compréhension, notamment la description de la méthode de Schulze ou encore de
l'algorithme étudié dans la partie III. Ce sujet permet de bien s'entraîner sur 
les
graphes, dans leurs aspects tant algorithmiques que théoriques.

Indications
Partie I
1 On peut commencer par écrire une fonction examinant un bulletin donné et 
renvoyant 1 ou -1 selon le candidat classé en premier parmi i et j.
3 Pour la parité des coefficients non diagonaux, utiliser le nombre total p de 
bulletins
dans l'urne.
5 Considérer par exemple le bulletin
bi,j,n = [ i, j, 0, 1, . . . , i - 1, i + 1, . . . , j - 1, j + 1, . . . , n - 
1 ]
et construire le second bulletin de sorte que l'urne obtenue soit associée à 
Ei,j,n .
6 On doit obtenir M3 = M1 + M2 .
7 Écrire M sous la forme d'une combinaison linéaire des matrices Ei,j,n , puis 
utiliser
les questions 5 et 6.
8 Ne pas hésiter à décomposer le code en plusieurs fonctions. Commencer par
exemple par écrire une fonction implémentant la construction effectuée à la 
question 5. La fonction List.rev pourra être utile à cet effet.
9 Le code précédent étant composé de plusieurs fonctions, il est nécessaire de 
commencer par étudier la complexité des fonctions auxiliaires. Attention à la 
complexité de l'opérateur @ en OCaml.
Partie II
11 Pour décider si un sommet donné est un vainqueur de Condorcet, il suffit 
d'examiner une seule ligne de la matrice.
13 Considérer un chemin  comportant une boucle et démontrer qu'en retirant cette
boucle on obtient un chemin de poids supérieur ou égal au poids de .
14 Introduire deux chemins, de i à k et de k à j, de poids respectifs I[i, k] 
et I[k, j],
puis construire à l'aide de ces chemins un chemin de i à j.
15 Adapter la relation de récurrence de l'algorithme de Floyd-Warshall, ainsi 
que les
conditions pour appliquer cette relation.
17 Comparer pour les deux algorithmes le contexte d'utilisation et la 
complexité.
18 Pour la parité des coefficients, justifier que ceux de la matrice I 
apparaissent tous
nécessairement dans M.
22 Dans le cas où I[i, j] 6 I[j, k], utiliser le résultat de la question 14 
appliqué à I[j, i],
puis à I[i, k]. Le cas I[i, j] > I[j, k] se traite de façon similaire.
23 En raisonnant par l'absurde, construire une suite d'entiers naturels (ik )kN 
strictement inférieurs à n telle que S[ik , ik+1 ] < 0 pour tout k  N.
Partie III
25 Les rôles de x et ¬x sont symétriques. Dans le cas où le candidat bx a été 
choisi,
calculer le coefficient S[c, a2 ] dans la matrice de préférence de Schulze.
26 S'il existe une variable x pour laquelle les sommets bx et b¬x ont été 
choisis,
justifier que pour une autre variable y, ni by ni b¬y n'ont été choisis.
27 Procéder par double implication. Pour le sens direct, il faut choisir quels 
sommets
sélectionner en fonction de l'interprétation de la formule. Pour le calcul de 
I, on se
limitera à la ligne et la colonne correspondant au champion c.
28 Justifier que l'algorithme de transformation de formule en élection 
s'exécute en
temps polynomial.

I. Vote par préférence
1 Commençons par écrire une fonction traite_bulletin qui compare les candidats 
i et j sur un bulletin donné, et renvoie 1 ou -1 en fonction du candidat classé
en premier parmi i et j. Pour cela, on parcourt récursivement la liste associée 
jusqu'à
trouver pour la première fois l'entier i ou l'entier j.
let rec traite_bulletin i j b = match b with
| [] -> failwith "i et j absents du bulletin"
| x::q -> if x = i then 1
else if x = j then -1
else traite_bulletin i j q;;

Une erreur classique consiste à utiliser directement les noms de variable
i et j dans les motifs du filtrage :
| i::q -> 1
| j::q -> -1
| x::q -> traite_bulletin i j q
En effet, on ne peut utiliser dans les filtrages en OCaml que des constructeurs
(comme :: sur les listes), des constantes, mais pas des valeurs calculées.
Le résultat de cette fonction est incorrect si i = j. Ce cas, où il n'y a pas
réellement de candidats à comparer, intervient pourtant dans la construction
de la matrice d'adjacence à la question 4. Cette situation sera gérée dans la
fonction duel directement.
Le résultat de la comparaison des deux candidats s'obtient alors en additionnant
les résultats des appels à la fonction traite_bulletin sur chaque bulletin de 
l'urne.
let
|
|
|

rec duel i j u = match u with
_ when i = j -> 0 (* voir remarque precedente *)
[] -> 0
b::q -> (traite_bulletin i j b) + (duel i j q);;

2 Soit M = (mij )06i,j62 la matrice d'adjacence du graphe de préférence de 
l'urne.
Considérons par exemple les candidats 0 et 2 : un seul bulletin (le deuxième) 
classe 2
avant 0, tandis que les trois autres classent 0 avant 2. On obtient alors m0,2 
= 3-1 = 2
et m2,0 = 1 - 3 = -2. En poursuivant de la même manière pour les autres couples
de candidats, on en déduit que

0
M = -2
-2

2 2
0 0
0 0

En ne représentant que les arcs ayant un poids strictement positif, le graphe de
préférence associé à cette urne est le suivant.

1

2

0

2

2

3 Soit U une urne, et soit M = (mi,j )06i,j6n-1 la matrice d'adjacence de son
graphe de préférence, où n désigne le nombre de candidats. Pour tout couple (i, 
j)
de candidats, notons di,j le nombre de bulletins qui placent i avant j. Pour 
tout
candidat i, on a par convention mi,i = 0. De plus, pour tout couple (i, j) de 
candidats
distincts, on obtient par définition de la matrice M
mi,j = di,j - dj,i = -(dj,i - di,j ) = -mj,i
ce qui prouve que
La matrice d'adjacence d'un graphe de préférence est antisymétrique.
Par ailleurs, si p désigne le nombre de bulletins dans l'urne, on a dj,i = p - 
di,j
pour tout couple (i, j) de candidats distincts. Dès lors, on obtient avec la 
même
hypothèse mi,j = di,j - (p - di,j ) = 2di,j - p. L'entier 2di,j étant pair, la 
parité du
coefficient mi,j est donc indépendante de i et j. Autrement dit,
Les coefficients non diagonaux d'une matrice d'adjacence d'un graphe de 
préférence ont tous la même parité.
On a montré plus précisément que cette parité correspond à la parité du
nombre p de bulletins dans l'urne.
4 Commençons par créer une matrice nulle, puis utilisons la fonction duel de la
question 1 pour calculer ses coefficients. On obtient la fonction suivante.
let depouillement n u =
let mat = Array.make_matrix n n 0 in
for i = 0 to (n-1) do
for j = 0 to (n-1) do
mat.(i).(j) <- duel i j u
done
done;
mat;;
5 Supposons que i < j sans perte de généralité. Définissons les deux listes 
ordonnées
bi,j,n = [ i, j, 0, 1, . . . , i - 1, i + 1, . . . , j - 1, j + 1, . . . , n - 
1 ]
et
b0i,j,n = [n - 1, . . . , j + 1, j - 1, . . . , i + 1, i - 1, . . . , 1, 0, i, 
j]
Tous les entiers entre 0 et n - 1 sont classés et ce sont les seuls. Dès lors, 
les
 deux
listes précédentes définissent deux bulletins, et on définit Ui,j,n = bi,j,n , 
b0i,j,n l'urne
contenant ces deux bulletins. On pose enfin M = Mat (Ui,j,n ) la matrice 
d'adjacence
du graphe de préférence associé à Ui,j,n .
Démontrons à présent que M = Ei,j,n . Ces deux matrices étant antisymétriques,
il suffit de montrer que leurs coefficients d'indices (k, `) vérifiant k < ` 
sont égaux
deux à deux. Si k = i et ` = j, alors les deux bulletins placent i avant j, 
donc mi,j = 2
et mj,i = -2, correspondant aux seuls coefficients non nuls de la matrice 
Ei,j,n . Il reste
à montrer que tous les autres coefficients sont nuls. Il y a trois cas :
· Si k  {i, j} et ` 
/ {i, j}, alors bi,j,n place k avant ` et b0i,j,n place ` avant k,
donc mk,` = 0.
· De même, si `  {i, j} et k 
/ {i, j}, bi,j,n place ` avant k et b0i,j,n place k avant `,
d'où mk,` = 0.
· Si k 
/ {i, j} et ` 
/ {i, j}, bi,j,n place k avant ` (les candidats différents de i
et j sont placés dans l'ordre croissant) et b0i,j,n place ` avant k (les 
candidats
différents de i et j sont placés dans l'ordre décroissant), soit mk,` = 0.