Matrica Tutte

Në teorinë e grafeve, matrica Tutte A e një grafi $G=(V,E)$ është një matricë e përdorur për të përcaktuar ekzistencën e një përputhjeje të përsosur : domethënë, një grup skajesh që përplasen me secilin kulm saktësisht një herë.

Nëse bashkësia e kulmeve është $V=\{1,2,\dots ,n\}$ atëherë matrica Tutte ka përmasat n × n dhe po e shënojmë matrica A me hyrje

$A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{nëse}}\;(i,j)\in E{\mbox{ dhe }}i<j\\-x_{ji}\;\;{\mbox{nëse}}\;(i,j)\in E{\mbox{ dhe }}i>j\\0\;\;\;\;{\mbox{përndryshe}}\end{cases}}$

ku $x_{ij}$ janë të pacaktuara. Përcaktori i kësaj matrice anore-simetrike është atëherë një polinom (në ndryshoret $x_{ij}$, $i<j$ ).

Matrica Tutte është emërtuar sipas WT Tutte, dhe është një përgjithësim i matricës Edmonds për një graf dypalësh të baraspeshuar.