Namespaces
Variants
Actions

Tutte matrix

From Encyclopedia of Mathematics
Revision as of 07:09, 31 October 2016 by Richard Pinch (talk | contribs) (link)
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05C50 Secondary: 05C70 [MSN][ZBL]

In graph theory, the Tutte matrix $A$ of a graph $G = (V,E)$ is a matrix used to determine the existence of a perfect matching: that is, a set of edges which is incident with each vertex exactly once.

If the set of vertices $V$ has $2n$ elements then the Tutte matrix is a $2n \times 2n$ matrix $A$ with entries $$ A_{ij} = \begin{cases} x_{ij}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i<j\\ -x_{ji}\;\;\mbox{if}\;(i,j) \in E \mbox{ and } i>j\\ 0\;\;\;\;\mbox{otherwise} \end{cases} $$ where the $x_{ij}$ are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables $x_{ij}$, $i<j$): this coincides with the square of the pfaffian of the matrix $A$ and is non-zero (as a polynomial) if and only if a perfect matching exists. (It should be noted that this is not the Tutte polynomial of $G$.)

The Tutte matrix is a generalisation of the Edmonds matrix for a balanced bipartite graph.

References

  • Rajeev Motwani, Prabhakar Raghavan, "Randomized Algorithms", Cambridge University Press (1995) ISBN 978-0-521-47465-8 Zbl 0849.68039
  • Allen B. Tucker, "Computer Science Handbook", 2nd ed. CRC Press (2004) ISBN 158488360X
  • W.T. Tutte, "The factorization of linear graphs", J. London Math. Soc. 22 (1947) 107-111 DOI 10.1112/jlms/s1-22.2.107
How to Cite This Entry:
Tutte matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Tutte_matrix&oldid=39570