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{array}{c}{x}_{ij}\text{nëse}(i,j)\in E\text{ dhe }i<j\\ -x_{ji}\text{nëse}(i,j)\in E\text{ dhe }i>j\\ 0\text{përndryshe}\end{array}$

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.