Tutte matrix
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-by-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.
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.
- v
- t
- e
- Alternant
- Anti-diagonal
- Anti-Hermitian
- Anti-symmetric
- Arrowhead
- Band
- Bidiagonal
- Bisymmetric
- Block-diagonal
- Block
- Block tridiagonal
- Boolean
- Cauchy
- Centrosymmetric
- Conference
- Complex Hadamard
- Copositive
- Diagonally dominant
- Diagonal
- Discrete Fourier Transform
- Elementary
- Equivalent
- Frobenius
- Generalized permutation
- Hadamard
- Hankel
- Hermitian
- Hessenberg
- Hollow
- Integer
- Logical
- Matrix unit
- Metzler
- Moore
- Nonnegative
- Pentadiagonal
- Permutation
- Persymmetric
- Polynomial
- Quaternionic
- Signature
- Skew-Hermitian
- Skew-symmetric
- Skyline
- Sparse
- Sylvester
- Symmetric
- Toeplitz
- Triangular
- Tridiagonal
- Vandermonde
- Walsh
- Z
- Adjugate
- Alternating sign
- Augmented
- Bézout
- Carleman
- Cartan
- Circulant
- Cofactor
- Commutation
- Confusion
- Coxeter
- Distance
- Duplication and elimination
- Euclidean distance
- Fundamental (linear differential equation)
- Generator
- Gram
- Hessian
- Householder
- Jacobian
- Moment
- Payoff
- Pick
- Random
- Rotation
- Seifert
- Shear
- Similarity
- Symplectic
- Totally positive
- Transformation
- Cabibbo–Kobayashi–Maskawa
- Density
- Fundamental (computer vision)
- Fuzzy associative
- Gamma
- Gell-Mann
- Hamiltonian
- Irregular
- Overlap
- S
- State transition
- Substitution
- Z (chemistry)
- Mathematics portal
- List of matrices
- Category:Matrices
This graph theory-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e
This article about matrices is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e