Wie kann effizient festgestellt werden, ob eine bestimmte Leiter gültig ist?

In meinem örtlichen Squashclub gibt es eine Leiter, die wie folgt funktioniert.

Zu Beginn der Saison erstellen wir eine Tabelle mit dem Namen jedes Clubmitglieds in einer separaten Zeile.
Wir schreiben dann die Anzahl der gewonnenen Spiele und die Anzahl der gespielten Spiele neben jeden Namen (in der Form: Spieler gewinnt / Spiele).

Zu Beginn der Saison sieht die Tabelle also so aus:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Zwei beliebige Spieler können ein Match spielen, wobei ein Spieler gewinnt. Wenn der Spieler gewinnt, der dem unteren Ende des Tisches am nächsten ist, wird die Position der Spieler gewechselt. Wir wiederholen dann Schritt 2. und aktualisieren die Anzahl der Siege und Spiele neben jedem Spieler. Zum Beispiel, wenn Alice Billy schlägt, haben wir

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

Diese Spiele finden die ganze Saison über statt und führen schließlich dazu, dass die Spieler in der ungefähren Reihenfolge ihrer Stärke aufgelistet werden.

Leider geschieht die Aktualisierung auf eine eher zufällige Weise, so dass Fehler gemacht werden. Im Folgenden sind einige Beispiele für ungültige Tabellen aufgeführt, d. H. Tabellen, die nicht korrekt erstellt werden konnten, wenn die obigen Schritte für eine Startreihenfolge (wir haben die zu Beginn der Saison verwendete Reihenfolge vergessen) und die Reihenfolge der Übereinstimmungen und Ergebnisse befolgt wurden:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Wie können wir anhand einer Tabelle effizient feststellen, ob sie gültig ist? Wir könnten damit beginnen, Folgendes zu bemerken:

Die Reihenfolge der Namen spielt keine Rolle, da wir die ursprüngliche Startreihenfolge vergessen haben.
Die Gesamtzahl der Siege sollte die Hälfte der Anzahl der gespielten Spiele betragen. (Dies zeigt, dass das erste obige Beispiel ungültig ist.)
Angenommen, die Tabelle ist gültig. Dann gibt es eine Multigraph - eine grafische Darstellung mehrere Kanten Einlassen aber keine Schleifen - mit jedem Scheitelpunkt mit einem Spiel mit einem Spieler und jede Kante entsprechenden gespielt. Dann entspricht die Gesamtzahl der von jedem Spieler gespielten Spiele dem Grad des Scheitelpunkts des Spielers im Multigraph. Wenn also kein Multigraph mit den entsprechenden Scheitelpunkten vorhanden ist, muss die Tabelle ungültig sein. Beispielsweise gibt es keine Multigraphie mit einem Scheitelpunkt des ersten und dritten Grades, so dass das zweite Beispiel ungültig ist. [Wir können effizient prüfen, ob ein solcher Multigraph existiert.]

Wir haben also zwei Überprüfungen, mit denen wir beginnen können, dies lässt jedoch weiterhin ungültige Tabellen zu, wie beispielsweise das dritte Beispiel. Um zu sehen, dass diese Tabelle ungültig ist, können wir rückwärts arbeiten und alle möglichen Möglichkeiten ausschöpfen, wie die Tabelle entstanden sein könnte.

Ich habe mich gefragt, ob jemand an einen Polynomzeit-Algorithmus denken kann (in Bezug auf die Anzahl der Spieler und die Anzahl der Spiele), der dieses Entscheidungsproblem löst.

algorithms graphs Ben
quelle

Vielleicht gibt es einen Havel-Hakimi-Satz für gerichtete Multigraphen ...

Aryabhata

Warum kann das dritte Beispiel nicht möglich sein? Was ist, wenn Alice Bob besiegt, Carol Bob und Carol Daffyd. Dann hat Alice 1 von 1 Spielen gewonnen, Bob hat 0 von 2 Spielen gewonnen, Carol hat 2 von 2 Spielen gewonnen und Daffyd hat 0 von 1 Spielen gewonnen?

utdiscant

utdiscant: Wenn der niedrigere Spieler nach jedem Spiel gewinnt, werden die Spieler gewechselt. Um zu zeigen, dass das dritte Beispiel möglich ist, müssten Sie eine Startkonfiguration und eine Abfolge von Spielen angeben, dh mit einer Reihenfolge, die zur angegebenen Tabelle führt.

Ben

aryabhata: Danke - ja, das wäre ein nützlicher Schritt. Leider klingt es ziemlich schwer ...

Ben

ein Vorschlag, dies zu studieren / zu lösen. spezifiziere es als SAT Problem. dann versuche es mit vielen zufälligen Fällen. Finden Sie heraus, ob es für einen Standardlöser schwierig ist. Wenn nicht, ist es möglicherweise eine eingeschränkte Teilmenge in P.

vzn

Antworten:

Dies ist keine vollständige Antwort. Ich gebe eine einfachere Erklärung des Problems und einige Bemerkungen.

Wir beginnen mit einem Diagramm, in dem die Eckpunkte mit . $[n]$

Wir haben eine Operation, die dem Diagramm eine gerichtete Kante von nach hinzufügt , und wenn werden die Beschriftungen gewechselt. $v$ $u$ $label(v)<label(u)$

Überprüfen Sie bei einem gerichteten Mehrfachgraphen mit Ecken und Kanten, ob er mit der obigen Operation erhalten werden kann. $G$ $n$ $e$

Es ist leicht zu erkennen, dass das Problem in : Ein Zertifikat ist eine (polynomial große) Folge von Operationen, die zu . $\mathsf{NP}$ $G$

Überwachung

Es scheint, dass wir ohne Verlust der Allgemeinheit davon ausgehen können, dass alle Kanten zum letzten Scheitelpunkt am Ende der Sequenz und alle Kanten zu Beginn der Sequenz hinzugefügt werden. Dies kann auf andere Eckpunkte verallgemeinert werden. Angenommen, wir haben alle Scheitelpunkte mit Beschriftungen entfernt, die größer als die . Alle Kanten zu werden am Ende der Sequenz und alle Kanten zu am Anfang der Sequenz hinzugefügt. $label(v)$ $v$ $v$

Ich denke, es sollte möglich sein, diese Beobachtung mit Havel-Hakimi zu kombinieren , um einen polynomialen Zeitalgorithmus zu erhalten.

Kaveh
quelle

Hallo. Vielen Dank. Würde es Ihnen etwas ausmachen, Ihre Beobachtung im Zusammenhang mit Leitern noch einmal zu formulieren? Ich glaube, es gibt ein Gegenbeispiel für ein Diagramm der Ordnung 3, aber vielleicht habe ich es falsch verstanden.

Ben

@ Ben, ich denke, es wäre das Folgende: Sie können davon ausgehen, dass die letzte Person auf der Leiter alle Spiele, die er zu Beginn des Turniers gewonnen hat, und alle Spiele, die er am Ende des Turniers verloren hat, gespielt hat . Lassen Sie mich wissen, ob es ein Gegenbeispiel dazu gibt, ich habe dies nicht sorgfältig geprüft.

Kaveh

Leider gibt es Leitern wie diese: A 2/2 B 0/1 C 0/1

Ben

@Ben, ich denke, das Beispiel stimmt mit dem überein, was ich geschrieben habe, dh es ist kein Gegenbeispiel zur Beobachtung.

Kaveh

Die Leiter ist gültig. Nehmen wir an, das letzte gespielte Spiel war ein Verlust für C. Vor dem letzten Spiel muss die Leiter dann so ausgesehen haben: C 0/0 B 0/1 A 1/1, aber diese Leiter ist ungültig. Daher können wir nicht davon ausgehen, dass das letzte Spiel eine Niederlage für C.

Ben war.

Ich habe das Problem nicht gelöst, aber ich habe teilweise Ergebnisse, deren Aussagen unten angegeben sind. Ich werde die Beweise aufschreiben, wenn jemand interessiert ist.

Vorschlag . Angenommen, die Leiter (1) enthält mehr als einen Spieler (2) enthält die gleiche Anzahl an Gewinnen und Verlusten. und (3) ist so, dass jeder Spieler mindestens ein Spiel gewonnen und mindestens ein Spiel verloren hat. Dann ist die Leiter gültig.

$W_i$ $i$ $L_i$ $i$ $R_i$

$L_i=0$

W_{i} \leq \sum_{k : R_{k} > R_{i}, W_{k} > 0} (L_{k} - 1)^{+} + \sum_{k : R_{k} < R_{i}} L_{k},

$W_i \le \sum_{k:R_k > R_i, W_k > 0} (L_k - 1)^+ + \sum_{k:R_k<R_i}L_k,$

L_{i}

$L_i$

W_{i} = 0

$W_i=0$

Ben
quelle