Algèbre max-plus

Algèbre max-plus

Algèbre max-plus

Une algèbre max-plus est une algèbre sur les nombres réels munie des opération de maximum et d'addition.

Ainsi si on note \oplus l'opération maximum et \otimes l'addition, les opérations sont définies par:

A \bigoplus B = max(A,B)
A \bigotimes B := A + B

On peut alors vérifier que ces opération sur les réels vérifient bien celles exigé par la structure d'algèbre.

Cette algèbre est liée à l'algèbre des dioïdes

Application au calcul distances dans un graphe pour l'algèbre min-plus

On se place ici dans l'algèbre min-plus (l'opération max est remplacé par l'opération min).

On peut représenter un graphe à n sommets comme une matrice A = (ai,j) des distances entre chaque sommet: si le sommet i et lié avec le sommet j alors l'élément ai,j est égale au poids de l'arrête (i,j), si les sommets i et j ne sont pas reliées alors ai,j correspond à l'infini (on a ai,i = 0).

Ainsi la distance entre i et j en passant par au plus un sommet est: minkestunsommet(ai,k + ak,j)

Ceci correspond au produit matriciel dans l'algèbre min-plus. Ainsi pour calculer la longueur d'un plus court chemin d'un sommet à un autre dans le graphe il suffit de calculer la puissance n de A dans cette algèbre.


  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Alg%C3%A8bre max-plus ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algèbre max-plus de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Algebre max-plus — Algèbre max plus Une algèbre max plus est une algèbre sur les nombres réels munie des opération de maximum et d addition. Ainsi si on note l opération maximum et l addition, les opérations sont définies par: On peut alors vérifier que ces… …   Wikipédia en Français

  • Algèbre Max-plus — Une algèbre max plus est une algèbre sur les nombres réels munie des opération de maximum et d addition. Ainsi si on note l opération maximum et l addition, les opérations sont définies par: On peut alors vérifier que ces opération sur les réels… …   Wikipédia en Français

  • Algèbre min-plus — Algèbre max plus Une algèbre max plus est une algèbre sur les nombres réels munie des opération de maximum et d addition. Ainsi si on note l opération maximum et l addition, les opérations sont définies par: On peut alors vérifier que ces… …   Wikipédia en Français

  • Max plus — Algèbre max plus Une algèbre max plus est une algèbre sur les nombres réels munie des opération de maximum et d addition. Ainsi si on note l opération maximum et l addition, les opérations sont définies par: On peut alors vérifier que ces… …   Wikipédia en Français

  • Algèbre (homonymie) — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le mot « algèbre » vient de l arabe ’al ǧabr (« réduction »), désignant une technique de chirurgie des membres puis une technique de… …   Wikipédia en Français

  • Algebre de Boole (logique) — Algèbre de Boole (logique) Pour les articles homonymes, voir Algèbre de Boole. L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les… …   Wikipédia en Français

  • Algèbre De Boole (Logique) — Pour les articles homonymes, voir Algèbre de Boole. L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les variables logiques. Plus… …   Wikipédia en Français

  • Algèbre de boole (logique) — Pour les articles homonymes, voir Algèbre de Boole. L algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l électronique qui s intéresse aux opérations et aux fonctions sur les variables logiques. Plus… …   Wikipédia en Français

  • Plus haut facteur commun — Plus grand commun diviseur En arithmétique élémentaire, le plus grand commun diviseur, abrégé en général PGCD, de deux nombres entiers naturels est le plus grand entier naturel qui divise simultanément ces deux entiers. Par exemple le PGCD de 42… …   Wikipédia en Français

  • Algèbre involutive simple — En mathématiques, une algèbre involutive simple sur un corps commutatif est une algèbre involutive qui n admet par d idéaux stable par l involution autre que {0} et elle même. Les algèbres involutives simples centrales (en un sens à préciser plus …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”