Tuttejeva matrika

Tuttejeva matrika v teoriji grafov za graf $G=(V,E)\,$ je matrika, s pomočjo katere določamo obstoj popolnega ujemanja. Popolno ujemanje pomeni, da je podmnožica povezav, takšna, da ima vsako vozlišče samo eno povezavo, ki vstopa ali izstopa.

Tuttejeva matrika je nesimetrična (antisimetrična) tako, da so elementi nad glavno diagonalo pozitivni.

Če ima množica vozlišč $V\,$ natanko $n\,$, elementov potem je Tuttejeva matrika kvadratna matrika $n\times n\,$, z elementi

$A_{ij}={\begin{cases}x_{ij}\;\;{\mbox{kadar je}}\;(i,j)\in E{\mbox{ in }}i<j\\-x_{ji}\;\;{\mbox{kadar je}}\;(i,j)\in E{\mbox{ in }}i>j\\0\;\;\;\;{\mbox{v ostalih primerih}}\end{cases}}$.

Determinanta te matrike je polinom, ki je enak kvadratu Pfaffove determinante (pfafiana) matrike $A\,$, ki je neničelen samo, če in samo, če obstoja popolno ujemanje. Pripomniti je potrebno, da to niso Tuttejevi polinomi matrike $G\,$.

Imenuje se po angleško-kanadskem kriptologu in matematiku Williamu Thomasu Tutteju (1917 – 2002).

Tuttejeva matrika je posplošitev Edmondsonove matrike za uravnoteženi bipartitni graf.

Zunanje povezave

• Tuttejeva matrika na MathWorld (angleško)
• Ujemanje v ravninskih grafih Arhivirano 2015-12-07 na Wayback Machine. (angleško)