Matrice d'Edmonds

En théorie des graphes, la matrice d'Edmonds $A$ d'un graphe biparti équilibré $G=(U,V,E)$, c'est-à-dire tel que $\left|U\right|=\left|V\right|$ (où $U=\{u_1,\dots ,u_n\}$ et $V=\{v_1,\dots ,v_n\}$ sont les deux ensembles disjoints de ses sommets), est définie par :

$$A_{ij}=\{\begin{array}{cc}{x}_{ij},& (u_i,v_j)\in E\\ 0,& (u_i,v_j)\notin E\end{array}$$où $x_{ij}$ sont les indéterminées. Une application de la matrice d'Edmonds d'un graphe biparti est que le graphe admet un couplage parfait si et seulement si le polynôme $\det (A_{ij})$ en les $x_{ij}$ est non-identiquement nul. De plus, le nombre de couplage parfaits est égal au nombre de monômes dans le polynôme $\det (A)$ et est aussi égal au permanent de $A$. Enfin, le rang de $A$ est égal au nombre de couplages maximaux de $G$.

Le nom matrice d'Edmonds provient du mathématicien Jack Edmonds. Sa généralisation aux graphes non-bipartis est la matrice de Tutte. Modèle:Palette MatricesModèle:Portail