Max-Plus-Algebra
Eine Max-Plus-Algebra ist ein mathematisches Objekt, das vergleichbar ist mit einer Algebra über den reellen Zahlen, wobei jedoch die Körper-Operationen ersetzt werden: die Addition durch das Bilden des Maximums, die Multiplikation durch die gewöhnliche Addition. Geometrie über der Max-Plus-Algebra wird als tropische Geometrie bezeichnet. Daher wird die Max-Plus-Algebra auch als tropischer Semiring bezeichnet.
In der Planungstheorie, etwa bei der Behandlung von Petri-Netzen, erlaubt die Theorie der Max-Plus-Algebren den Einsatz geeigneter Methoden aus der linearen Algebra.
Das Optimieren eines Fahrplans kann beispielsweise auf diesem Wege als Eigenwertproblem aufgefasst werden.

Ebenso wie der Begriff Algebra sowohl eine mathematische Struktur als auch ein mathematisches Teilgebiet bezeichnet, versteht man unter Max-Plus-Algebra manchmal auch das mathematische Teilgebiet, das sich mit den besagten Strukturen beschäftigt.

Definition 
Eine Max-Plus-Algebra ist ein Halbring , auf dem ein idempotenter kommutativer Halbkörper mit Nullelement  vermöge einer Multiplikation  operiert. (Zum Vergleich: Eine Algebra ist ein Ring, auf dem ein Körper operiert)

Im Einzelnen bedeutet dies, dass die nachfolgend aufgezählten Axiome erfüllt sind, jeweils für alle  und .

Halbring 
 
 
 
 
 
Gemäß 1. und 2. ist  kommutative Halbgruppe, gemäß 3. ist  Halbgruppe, 4. und 5. sind die Distributivgesetze.

Idempotenter kommutativer Halbkörper 
 
 
 
 
 
 
 
 Falls , so gibt es ein  mit 
 
 
Gemäß 1.–5. ist  Halbring, gemäß 6. und 7. sind  und  jeweils neutrale Elemente der Verknüpfungen. Zusammen mit der Existenz multiplikativ inverser Elemente gemäß 8. ist daher  Halbkörper, der gemäß 9. (multiplikativ) kommutativ und gemäß 10. (additiv) idempotent ist.

Operation 
 
 
 
 
 
Die Operation  soll also in naheliegender Weise verträglich mit den Verknüpfungen auf  bzw.  sein.

Beispiele 
Im Folgenden werden der besseren Lesbarkeit halber die Indizes an den Verknüpfungen weggelassen, da jeweils aus dem Kontext klar ist, welche der Verknüpfungen gemeint sein muss. Die Umkreisungen der Operatoren dagegen sind erforderlich, um eine Verwechselung mit der gewöhnlichen Addition bzw. Multiplikation zu vermeiden.

Das wichtigste Beispiel für einen idempotenten kommutativen Halbkörper wird mit  bezeichnet und hat als zugrunde liegende Menge  sowie die Verknüpfungen
  (speziell )
  (speziell ).
Das neutrale Element bezüglich  ist dabei , das bezüglich  ist 0.
Diese Verwendung der Operationen Maximum und Addition motiviert auch die Bezeichnung Max-Plus-Algebra.
Ein weiterer wichtiger idempotenter kommutativen Halbkörper ist , er wird zum Teil als Min-Plus-Algebra bezeichnet.
Die folgenden Beispiele von Max-Plus-Algebren sind durchweg Max-Plus-Algebren über :
  selbst ist eine Max-Plus-Algebra.
 Die Menge  aller Abbildungen von einer festen Menge  nach  mit punktweiser Maximumbildung und Addition und Skalaroperation.
 Auf der Menge  aller Abbildungen  kann man die erforderlichen Operationen wie folgt definieren:
 (punktweise Maximumbildung)
 (so genannte Supremumfaltung)

 Allerdings ist  unter der Supremumsfaltung nicht abgeschlossen. Durch den Übergang zu geeigneten Teilmengen davon, beispielsweise zur Menge der nach oben beschränkten Abbildungen, erhält man jedoch eine Max-Plus-Algebra. Man beachte, dass diese Struktur sich vom Spezialfall  des vorhergehenden Beispiels unterscheidet.
 Die Menge  aller -Matrizen mit Einträgen in , wobei Addition und Multiplikation von Matrizen nach den üblichen Formeln, in denen jedoch  und  durch  und  ersetzt sind, berechnet werden. Wie die gewöhnliche Matrixmultiplikation ist auch  nicht kommutativ.

Literatur

Weblinks 
 amadeus.inria.fr

Algebra