Algèbre min-plus

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 \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 min-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 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

  • 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

  • Plus court chemin — Problèmes de cheminement Les problèmes de cheminement sont des problèmes classiques de la théorie des graphes. L objectif est de calculer une route entre des sommets d un graphe qui minimise ou maximise un certaine fonction économique. Le… …   Wikipédia en Français

Share the article and excerpts

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