Tuttejeva matrika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

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[uredi | uredi kodo]