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 ''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. (This polynomial is not the
Tutte polynomial of ''G''.)
The Tutte matrix is named after
W. T. Tutte
William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a majo ...
, and is a generalisation of the
Edmonds matrix In graph theory, the Edmonds matrix A of a balanced bipartite graph G = (U, V, E) with sets of vertices U = \ and V = \ is defined by
: A_ = \left\{ \begin{array}{ll}
x_{ij} & (u_i, v_j) \in E \\
0 & (u_i, v_j) \notin E
\end{array}\right.
...
for a balanced
bipartite graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
.
References
*
*
*
Algebraic graph theory
Matching (graph theory)
Matrices
{{combin-stub