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 "V" has 2"n" elements then the Tutte matrix is a 2"n" × 2"n" matrix A with entries

: $A_{ij} = egin{cases} x_{ij};;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

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

Tutte matrix — noun A matrix used to determine whether all of the edges of a graph can be traversed without visiting a vertex more than once … Wiktionary
Tutte polynomial — This article is about the Tutte polynomial of a graph. For the Tutte polynomial of a matroid, see Matroid. The polynomial x4 + x3 + x2y is the Tutte polynomial of the Bull graph. The red line shows the intersection with the plane … Wikipedia
Edmonds matrix — In graph theory, the Edmonds matrix A of a balanced bipartite graph G(U, V, E) with sets of vertices U = {u 1, u 2, dots , u n } and V = {v 1, v 2, dots , v n} is defined by : A {ij} = left{ egin{array}{ll} x {ij} (u i, v j) in E 0 (u i, v j)… … Wikipedia
Knoten-Kanten-Matrix — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… … Deutsch Wikipedia
Schwartz-Zippel lemma and testing polynomial identities — Polynomial identity testing is the problem of determining whether a given multivariate polynomial is the0 polynomial or identically equal to 0. The input to the problem is an n variable polynomial over a fieldF. It can occur in the following… … Wikipedia
List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie … Wikipedia
Computing the permanent — In mathematics, the computation of the permanent of a matrix is a problem that is believed to be more complex than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined… … Wikipedia
Matroid — In combinatorics, a branch of mathematics, a matroid ( /ˈmeɪ … Wikipedia
Matching (Graphentheorie) — Die Theorie um das Finden von Matchings in Graphen ist in der diskreten Mathematik ein umfangreiches Teilgebiet, das in die Graphentheorie eingeordnet wird. Folgende Situation wird dabei betrachtet: Gegeben eine Menge von Dingen und zu diesen… … Deutsch Wikipedia
Kirchhoff's theorem — In the mathematical field of graph theory Kirchhoff s theorem or Kirchhoff s matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph. It is a generalization of Cayley s formula which provides… … Wikipedia

Academic Dictionaries and Encyclopedias

Tutte matrix

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Tutte matrix

Look at other dictionaries:

Share the article and excerpts

Direct link