Tuttejeva matrika

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

Tuttejeva matrika v teoriji grafov za graf 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šč natanko , elementov potem je Tuttejeva matrika kvadratna matrika , z elementi

.

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

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]