Edmondsonova matrika

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

${\displaystyle 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

• ${\displaystyle 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 ${\displaystyle \det(A_{ij}\,}$ ni enak nič.

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

Ta matematični članek je škrbina. Pomagajte Wikipediji in ga razširite.

• p
• p
• u