Matrica Tutte

Në teorinë e grafeve, matrica Tutte A e një grafi  ë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ë  atëherë matrica Tutte ka përmasat n × n dhe po e shënojmë matrica A me hyrje



ku  janë të pacaktuara. Përcaktori i kësaj matrice anore-simetrike është atëherë një polinom (në ndryshoret ,  ).

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.

Kategoria:Algjebër abstrakte