Dioïde

En mathématiques et en informatique, un dioïde est un semi-anneau dans lequel le préordre défini par l'addition est une relation d'ordre.

Définition

Soit D un ensemble muni d'un opérateur binaire $\oplus$, nommé addition, d'un opérateur binaire $\otimes$, nommé produit, et dans lequel sont spécifiés deux éléments distincts, notés 0 et 1.

On note ≤ le préordre défini par l'opérateur $\oplus$, c'est-à-dire que $a\le b\Leftrightarrow\exists c,~a\oplus c=b$.

On dit que $(D,\oplus,\otimes,0,1)$ est un dioïde si :

• $(D, \oplus, 0)$ est un monoïde commutatif ;
• $(D, \otimes, 1)$ est un monoïde ;
• $\otimes$ est distributif par rapport à $\oplus$ ;
• 0 est un élément absorbant pour $\otimes$, c'est-à-dire que $a \otimes 0 = 0 \otimes a = 0$ ;
• la relation ≤ est une relation d'ordre, c'est-à-dire que $a\leq b\wedge b\leq a\Rightarrow a=b$.

Si l'on omet le dernier point, la structure ainsi définie est un semi-anneau.

Le nom de dioïde provient du fait qu'il combine deux monoïdes, comme tout semi-anneau (en particulier tout anneau). Le dioïde et l'anneau sont tous deux des semi-anneaux, mais sont exclusifs l'un de l'autre.

Dioïde idempotent

Le dioïde idempotent est la classe de dioïde la plus utilisée. Elle se caractérise le fait que tout élément a est idempotent pour $\oplus$, c'est-à-dire que $a\oplus a=a$.

Par exemple, $([-\infty,+\infty[,\max,+,-\infty,0)$ est un dioïde idempotent.

Tout semi-anneau idempotent est un dioïde.

Démonstration

Si $a\le b$ alors il existe c tel que $a\oplus c=b$, d'où $b=a\oplus c=a\oplus a\oplus c=a\oplus b$.

De même, si $b\le a$ alors $a=b\oplus a$.

On conclut en utilisant la commutativité de $\oplus$.

Les semi-anneaux idempotents sont donc exactement les dioïdes idempotents.

Référence

Michel Gondran et Michel Minoux, Graphes, dioïdes et semi-anneaux, Paris, Tec & Doc, 2001 (ISBN 2-7430-0489-4)