Edmondsonova matrika

Edmondsova matrika v teoriji grafov za uravnoteženi dvodelni graf z oznako $G(U,V,E)\,$, kjer sta $U=\{u_{1},u_{2},\dots ,u_{n}\}$ in $V=\{v_{1},v_{2},\dots ,v_{n}\}$ množici vozlišč
je enaka

$A_{ij}=\left\{{\begin{array}{ll}x_{ij}&(u_{i},v_{j})\in E\\0&(u_{i},v_{j})\notin E\end{array}}\right.$

kjer so

• $x_{ij}\,$ nedoločene vrednosti

Imenuje se po kanadskem matematiku Jacku Edmondsu (rojen 1934).

Ena izmed uporab Edmondsonove matrike za dvodelni graf je v tem, da graf omogoča polno ujemanje, če in samo, če polinom $\det(A_{ij}\,$ ni enak nič.

Tuttejeva matrika je posplošitev Edmondsonove matrike na nedvodelne grafe.