Vérifier si le classement gagnant-perdant d'une ligue est possible

Vous organisez une ligue de basket-ball 1 contre 1 avec un calendrier des matchs. À la fin de la ligue, chaque joueur doit déclarer son supposé record de victoires-défaites (il n'y a pas d'égalité), mais vous voulez vérifier si le classement proposé était réellement possible compte tenu du calendrier.

Par exemple: vous avez quatre joueurs (Alice + Bob + Carol + Dave) et votre programme est un simple tournoi à la ronde. Les classements déclarés [ A: 3-0 B: 1-2 C: 1-2 D: 1-2] et [ A: 2-1 B: 1-2 C: 1-2 D: 2-1] seraient possible, mais la position debout [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] ne le serait pas.

Supposons maintenant que le calendrier soit plutôt un match de 3 matchs entre Alice + Bob et Carol + Dave. La position déclarée [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] est maintenant possible, mais [ A: 3-0 B: 1-2 C: 1-2 D: 1- 2] ne le serait plus.

(L'horaire n'a pas besoin d'être symétrique de quelque manière que ce soit. Vous pourriez faire en sorte qu'Alice ne joue contre Bob que 10 fois, puis que Bob + Carol + Dave jouent 58 round robins les uns contre les autres.)

Problème : Étant donné un calendrier avec k participants et n matchs totaux, vérifiez efficacement si un classement gagnant-perdant proposé pourrait réellement se produire à partir de ce calendrier.

Le O ($2^n$), la méthode de la force brute est évidente, énumère tous les résultats possibles du jeu et vérifie s'ils correspondent au classement proposé. Et si k est petit, l'augmentation n n'ajoute pas beaucoup de complexité - il est très facile de vérifier le classement d'une ligue à deux, qu'ils jouent dix matchs ou dix milliards de matchs. Au-delà de cela, je n'ai pas beaucoup progressé dans la recherche d'une meilleure méthode et j'étais curieux de savoir si quelqu'un avait déjà vu un problème similaire auparavant.

Cela peut être modélisé comme un problème Max-Flow.

En tant qu'étape de prétraitement, assurez-vous que le nombre de parties est égal à la somme du nombre de victoires (sinon, vous savez que quelque chose ne va pas).

Laisser $G$ être un ensemble de sommets correspondant aux jeux joués, et $P$un ensemble de sommets correspondant aux joueurs. Laisser$s$ et $t$ désignent deux sommets supplémentaires (source et puits).

Maintenant pour chaque jeu $g\in G$ joué entre $p1\in P$ et $p2\in P$, ajoutez un bord de $s$ à $g$ avec capacité $1$ et bords de $g$ à $p1$ et $g$ à $p2$ aussi avec capacité $1$. Cela modélise le fait que le jeu peut donner un point à l'un ou l'autre joueur.

Alors pour chaque joueur $p\in P$ ajouter un bord de $p$ à $t$ avec une capacité égale au nombre de victoires déclaré pour le joueur $p$. Cela modélise le fait que ce joueur devrait gagner au plus ce nombre de parties.

Il est facile de voir d'ici que si les scores rapportés sont possibles, il y aura un flux saturant de $s$ à $t$et réciproquement. Il vous suffit donc de vérifier si le maximum$s,t$-le débit dans ce graphique est égal au nombre de parties jouées.

Alternativement, vous pouvez également avoir un graphique avec un sommet par partie et un nombre de sommets pour chaque joueur correspondant au nombre de victoires, les connecter de la même manière qu'auparavant et regarder si le nombre d'arêtes dans une correspondance maximale est égal à le nombre de jeux (mais c'est presque la même chose vraiment).