In der Informatik ist Reihe von Monge oder Monge matrices, mathematische Gegenstände, die für ihren Entdecker, den französischen Mathematiker Gaspard Monge genannt sind.

Wie man

sagt, ist eine m-by-n Matrix eine Reihe von Monge wenn, für ganzes das

:

man erhält

:

So, wann auch immer wir zwei Reihen und zwei Säulen einer Reihe von Monge aufpicken (2 × 2 Submatrix), und denken die vier Elemente an den Kreuzungspunkten, der Summe des ober verlassenen und sinken richtige Elemente (über die Hauptdiagonale) ist weniger als oder gleich der Summe der tiefer verlassenen und ober-richtigen Elemente (über die Antidiagonale).

Diese Matrix ist eine Reihe von Monge:

:\begin {bmatrix }\

10 & 17 & 13 & 28 & 23 \\

17 & 22 & 16 & 29 & 23 \\

24 & 28 & 22 & 34 & 24 \\

11 & 13 & 6 & 17 & 7 \\

45 & 44 & 32 & 37 & 23 \\

36 & 33 & 19 & 21 & 6 \\

75 & 66 & 51 & 53 & 34 \end {bmatrix} </Mathematik>

Nehmen Sie zum Beispiel die Kreuzung von Reihen 2 und 4 mit Spalten 1 und 5.

Die vier Elemente sind:

:\begin {bmatrix }\

17 & 23 \\

11 & 7 \end {bmatrix} </Mathematik>

: 17 + 7 = 24

: 23 + 11 = 34

Die Summe der ober verlassenen und niedrigeren richtigen Elemente ist weniger als oder gleich der Summe der tiefer verlassenen und ober-richtigen Elemente.

Eigenschaften

• Die obengenannte Definition ist zur Behauptung gleichwertig

:A-Matrix ist eine Reihe von Monge wenn und nur wenn für alle

• Jede erzeugte Subreihe durch das Auswählen bestimmter Reihen und Säulen von einer ursprünglichen Reihe von Monge wird selbst eine Reihe von Monge sein.
• Jede geradlinige Kombination mit nichtnegativen Koeffizienten der Reihe von Monge ist selbst eine Reihe von Monge.
• Ein interessantes Eigentum der Reihe von Monge besteht darin, dass, wenn Sie mit einem Kreis das leftmost Minimum jeder Reihe kennzeichnen, Sie entdecken werden, dass Ihre Kreise nach unten nach rechts marschieren; das heißt, wenn, dann für alle
• Der Begriff der schwachen Reihe von Monge ist vorgeschlagen worden; eine schwache Reihe von Monge ist ein Quadrat n-by-n Matrix, die das Eigentum von Monge nur für alle befriedigt

Anwendungen

• Ein Quadrat Matrix von Monge, die auch über seine Hauptdiagonale symmetrisch ist, wird eine Matrix von Supnick (nach Fred Supnick) genannt; diese Art der Matrix hat Anwendungen auf das Handelsreisender-Problem (nämlich, dass das Problem leichte Lösungen zulässt, wenn die Entfernungsmatrix als eine Matrix von Supnick geschrieben werden kann). Bemerken Sie, dass jede geradlinige Kombination von Supnick matrices selbst eine Matrix von Supnick ist.

Bibliografie

• 'Einige Probleme um Handlungsreisender, Dartscheiben, und Euromünzen durch Vladimir G. Deineko und Gerhard J. Woeginger, sind in der Meldung der europäischen Vereinigung für die Theoretische Informatik (EATCS), Nummer 90, Oktober 2006, ISSN 0252-9742, Seite 44 erschienen. Sieh Online-Ausgabe (PDF).