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 is then the Tutte matrix is an n × n matrix A with entries
where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xij, 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. (This polynomial is not the Tutte polynomial of G.)
The Tutte matrix is named after W. T. Tutte, and is a generalisation of the Edmonds matrix for a balanced bipartite graph.
YouTube Encyclopedic
-
1/3Views:4066421 338
-
Lecture10 3-connected graphs (2/2) Tutte's wheel theorem #MAS477 Introduction to Graph Theory #KAIST
-
Math 432: Trees - Matrix-Tree Theorem (2 of 3)
-
Spectral Aspects of Symmetric Matrix Signings
Transcription
References
- R. Motwani, P. Raghavan (1995). Randomized Algorithms. Cambridge University Press. p. 167.
- Allen B. Tucker (2004). Computer Science Handbook. CRC Press. p. 12.19. ISBN 1-58488-360-X.
- W.T. Tutte (April 1947). "The factorization of linear graphs" (PDF). J. London Math. Soc. 22 (2): 107–111. doi:10.1112/jlms/s1-22.2.107. Retrieved 2008-06-15.
![](/s/i/modif.png)