Matrice d'Edmonds

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

où ${\displaystyle 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 ${\displaystyle \det {(A_{ij})}}$ en les ${\displaystyle x_{ij}}$ est non-identiquement nul. De plus, le nombre de couplage parfaits est égal au nombre de monômes dans le polynôme ${\displaystyle \det {(A)}}$ et est aussi égal au permanent de ${\displaystyle A}$. Enfin, le rang de ${\displaystyle A}$ est égal au nombre de couplages maximaux de ${\displaystyle 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.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.