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\vert U\right\vert =\left\vert V\right\vert$ (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{cases}x_{ij},&(u_{i},v_{j})\in E\\0,&(u_{i},v_{j})\notin E\end{cases}}$$

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.