Appariement (Mathématiques)

Appariement (mathématiques)

Pour les articles homonymes, voir Appariement.

En théorie des graphes, un appariement ou couplage d'un graphe (en anglais matching) est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun.

Définitions

Soit un graphe G = (S,A), l'appariement M est un ensemble d'arêtes non-adjacentes deux à deux. C'est à dire, M est l'ensemble des arêtes $(s_1,s_2)\in S$ telles que $\forall ((s_1,s_2), (s_3,s_4)) \in M^2$ avec $(s_1,s_2)\neq(s_3,s_4), \forall i,j \in \{1,2,3,4\}$, avec $i \neq j$, alors $s_i \neq s_j$.

Un appariement maximum est un appariement contenant le plus grand nombre possible d'arêtes. Un graphe peut posséder plusieurs appariements maximum.

Un appariement maximal est un appariement M du graphe tel que toute arête du graphe possède une intersection non vide avec au moins une arête de M. Il en découle la propriété suivante : soit un appariement maximal M, si une arête quelconque de A qui n'est pas dans M est ajoutée à M , alors M n'est plus un appariement de G.

Un appariement parfait ou appariement complet est un appariement M du graphe tel que tout sommet du graphe est incident à exactement une arête de M.

Propriétés

Un appariement maximum est aussi un appariement maximal.

Un appariement parfait est aussi un appariement maximal.

Ce document provient de « Appariement (math%C3%A9matiques) ».