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}=\{\begin{array}{cc}{x}_{ij}& (u_i,v_j)\in E\\ 0& (u_i,v_j)\notin E\end{array}$

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. Predloga:Math-stub