Rahul Sharma (Editor)

Tutte matrix

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

In graph theory, the Tutte matrix A of a graph G = (VE) 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 n elements then the Tutte matrix is an n × n matrix A with entries

A i j = { x i j if ( i , j ) E  and  i < j x j i if ( i , j ) E  and  i > j 0 otherwise

where the xij are indeterminates. The determinant of this skew-symmetric matrix is then a polynomial (in the variables xiji < 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

Tutte matrix Wikipedia


Similar Topics