Turnier graph

Question

A Turnier ist ein gerichteter Graph (Digraphen), erhalten durch eine Richtung für jede Kante in einem ungerichteten vollständigen Graphen zuzuweisen. Das heißt, es ist ein gerichteter Graph, bei dem jedes Paar von Scheitelpunkten durch eine einzelne gerichtete Kante verbunden ist.

Die Datenstruktur ist Adjazenzmatrix.

Was s einen Algorithmus zu finden, wenn der Graph ein Turnier Graph ist?

Answer 1

Es gibt n ^ 2 Einträge in der Adjazenzmatrix, und Sie müssen die Informationen, die in allen Einträgen ist das Problem zu lösen. (Sie müssen die 1en überprüfen, dass die richtigen Kanten vorhanden ist, und die 0en prüfen, ob die Hinterkanten sind nicht vorhanden.) So, da Sie mindestens N ^ 2 Einträge aus der Matrix zu lesen, das Gesamtproblem muss nehmen mindestens O (N ^ 2) Zeit.

In Bezug auf BFS-Suchversuche: Wenn Ihre Traversal O nimmt (n ^ 2) - das wird es, aufgrund der Notwendigkeit, Kanten in der Adjazenzmatrix zu sehen - dann spielt es keine Rolle, ob die Rückkantenprüfung konstant Zeit wird der Gesamtalgorithmus noch O (n ^ 2).

Ein weiterer Weg, um dieses Problem zu suchen: Da die Anzahl der Kanten, die die Anzahl von möglichen Paaren von Scheitelpunkten gleich ist, gibt es n * (n-1) / 2 Kanten sein, die O (n ^ 2) . Ihre traversal O (V + E), das somit ist O (n + n ^ 2), und somit ist O (n ^ 2).

Da die Best-Case-Zeit für diesen Algorithmus ist O (n ^ 2), dann kann man auch einfach eine Schleife durch die obere rechte Hälfte der Matrix (oberhalb den Diagonalen), und daß diese Einträge für jeden Scheck entweder a ) ist 1, oder b) ihre Transponierte entspricht 1.

Answer 2

Edit: verpassten den Teil, wo der Graph vollständig war

.

Wenn M Ihre Adjazenzmatrix ist, ist Mt die transponierte Matrix, ~M ist die Matrix mit allen „Bits“ invertiert und A^B ist das xor Stück für Stück zwischen den beiden Matrix.

Dann ist die Matrix ein Turnier iff:

~(M^Mt) = I

Answer 3

Hinzufügen zu tonfa Kommentar:

Kurz . Der Algorithmus "für jeden i ≠ j, prüfen Sie, dass genau ein von (i, j) zu sehen und (j, i) in Ihrem Diagramm ist" asymptotisch optimal

Weitere Einzelheiten: Zum Lesen nur in der Adjazenzmatrix wird Sie Ω nehmen (n ² ) Zeit. So gibt es keine Möglichkeit, dieses Problem in o zu lösen (n ² ) Zeit. Aber lassen Sie uns die Eingabe ignorieren.

Angenommen

, dass die Matrix bereits im Speicher. Um sicherzustellen, dass die ungerichtete Version Ihres Diagramms abgeschlossen ist, müssen Sie irgendwie die bestimmen, für jedes i ≠ j, wobei mindestens eine der Kanten (i, j) und (j, i) ist in Ihrem Diagramm. Wie Sie nur die Adjazenzgraph haben, bedeutet dies, Sie irgendwann Besuch für jeden i ≠ j mindestens einen von (i, j) oder (j, i) haben werden. Es gibt keine andere Art und Weise Vollständigkeit zu gewährleisten. Diese Überprüfung findet n (n + 1) / 2 = O (n ² ) Schritte.