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 |U|=|V| (où U={u1,…,un} et V={v1,…,vn} sont les deux ensembles disjoints de ses sommets), est définie par :

Aij={xij,(ui,vj)∈E0,(ui,vj)∉Eoù xij 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⁡(Aij) en les xij 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.