Prüfen, ob die Gewinn-Verlust-Wertung einer Liga möglich ist

Sie veranstalten eine 1-gegen-1-Basketballliga mit einem Spielplan. Am Ende der Liga muss jeder Spieler seinen vermeintlichen Gewinn-Verlust-Rekord melden (es gibt keine Unentschieden), aber Sie möchten überprüfen, ob die vorgeschlagene Platzierung angesichts des Zeitplans tatsächlich möglich war.

Zum Beispiel: Sie haben vier Spieler (Alice + Bob + Carol + Dave) und Ihr Zeitplan ist ein einfaches Round Robin. Die gemeldeten Tabellen [ A: 3-0 B: 1-2 C: 1-2 D: 1-2] und [ A: 2-1 B: 1-2 C: 1-2 D: 2-1] wären möglich, aber das Stehen [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] wäre nicht.

Nehmen wir nun an, der Zeitplan ist stattdessen ein 3-Spiele-Kopf-an-Kopf-Spiel zwischen Alice + Bob und Carol + Dave. Das gemeldete Stehen [ A: 3-0 B: 0-3 C: 0-3 D: 3-0] ist jetzt möglich, aber [ A: 3-0 B: 1-2 C: 1-2 D: 1- 2] wäre nicht mehr.

(Der Zeitplan muss in keiner Weise symmetrisch sein. Sie könnten Alice nur 10 Mal gegen Bob spielen lassen und dann Bob + Carol + Dave 58 Round Robin gegeneinander spielen lassen.)

Problem : Überprüfen Sie bei einem Zeitplan mit k Teilnehmern und n Gesamtspielen effizient, ob aus diesem Zeitplan tatsächlich eine vorgeschlagene Gewinn-Verlust-Wertung hervorgehen könnte.

Die O ( ) Brute-Force-Methode ist offensichtlich. Zählen Sie alle möglichen Spielergebnisse auf und prüfen Sie, ob sie mit der vorgeschlagenen Wertung übereinstimmen. Und wenn k klein ist, erhöht n nicht viel Komplexität - es ist sehr einfach, die Rangliste einer Zwei-Personen-Liga zu überprüfen, unabhängig davon, ob sie zehn oder zehn Milliarden Spiele spielt. Darüber hinaus habe ich bei der Suche nach einer besseren Methode nicht viel Fortschritte gemacht und war neugierig, ob jemand zuvor ein ähnliches Problem gesehen hat.$2^n$

Dies kann als Max-Flow-Problem modelliert werden.

Stellen Sie als Vorverarbeitungsschritt sicher, dass die Anzahl der Spiele der Summe der Anzahl der Siege entspricht (wenn nicht, wissen Sie, dass etwas nicht stimmt).

Sei eine Menge von Eckpunkten, die den gespielten Spielen entsprechen, und eine Menge von Eckpunkten, die den Spielern entsprechen. Lassen und bezeichnen zwei weitere Ecken (Quelle und Senke).$G$$P$$s$$t$

Fügen Sie nun für jedes Spiel das zwischen und wird, eine Kante von nach mit Kapazität und Kanten von nach und nach auch mit Kapazität . Dies modelliert die Tatsache, dass das Spiel jedem Spieler einen Punkt geben kann.$g\in G$$p1\in P$$p2\in P$$s$$g$$1$$g$$p1$$g$$p2$$1$

Fügen Sie dann für jeden Spieler eine Kante von nach Kapazität der gemeldeten Anzahl von Gewinnen für Spieler . Dies modelliert die Tatsache, dass dieser Spieler höchstens diese Anzahl von Spielen gewinnen sollte.$p\in P$$p$$t$$p$

Von hier aus ist leicht zu erkennen, dass, wenn die gemeldeten Bewertungen möglich sind, ein sättigender Fluss von nach und wechselseitig auftritt. Sie müssen also nur überprüfen, ob der maximale Fluss in diesem Diagramm der Anzahl der gespielten Spiele entspricht.$s$$t$$s,t$

Alternativ können Sie auch ein Diagramm mit einem Scheitelpunkt pro Spiel und einer Anzahl von Scheitelpunkten für jeden Spieler erstellen, die der Anzahl der Siege entsprechen. Verbinden Sie diese auf die gleiche Weise wie zuvor und prüfen Sie, ob die Anzahl der Kanten in einer maximalen Übereinstimmung gleich ist die Anzahl der Spiele (aber das ist fast das gleiche wirklich).