Ordinal optimization: Difference between revisions

Revision as of 12:58, 30 September 2013

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_{i j} = {\begin{array}{ll} x_{i j} & (u_{i}, v_{j}) \in E \\ 0 & (u_{i}, v_{j}) \notin E \end{array}

where the x_ij are indeterminates. One application of the Edmonds matrix of a bipartite graph is that the graph admits a perfect matching if and only if the polynomial det(A_ij) in the x_ij is not identically zero. Furthermore, the number of perfect matchings is equal to the number of monomials in the polynomial det(A), and is also equal to the permanent of A.

The Edmonds matrix is named after Jack Edmonds. The Tutte matrix is a generalisation to non-bipartite graphs.

References

20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

Template:Combin-stub

@@ Line 1: / Line 1: @@
-The name of the author is Nestor. Meter reading is exactly where my primary income arrives from but soon I'll be on my personal. I've always cherished residing in Idaho. To perform handball is the thing she enjoys most of all.<br><br>my web site :: [http://beta.Westernstatesfireequipment.com/ActivityFeed/MyProfile/tabid/93/userId/1095/Default.aspx auto warranty]
+In [[graph theory]], the '''Edmonds matrix''' <math>A</math> of a balanced [[bipartite graph]] <math>G(U, V, E)</math> with [[Set (mathematics)|set]]s of vertices <math>U = \{u_1, u_2, \dots , u_n \}</math> and <math>V = \{v_1, v_2, \dots , v_n\}</math> is defined by
+:<math> A_{ij} = \left\{ \begin{array}{ll}
+   x_{ij} & (u_i, v_j) \in E \\
+& (u_i, v_j) \notin E
+ \end{array}\right.</math>
+where the ''x''<sub>ij</sub> are indeterminates.  One application of the Edmonds matrix of a bipartite graph is that the graph admits a [[perfect matching]] if and only if the polynomial det(''A''<sub>ij</sub>) in the ''x''<sub>ij</sub> is not identically zero. Furthermore, the number of perfect matchings is equal to the number of [[monomials]] in the polynomial det(''A''), and is also equal to the [[permanent]] of ''A''.
+The Edmonds matrix is named after [[Jack Edmonds]]. The [[Tutte matrix]] is a generalisation to non-bipartite graphs.
+==References==
+*{{cite book|author=R. Motwani, P. Raghavan |title=Randomized Algorithms |url=http://books.google.com/books/cambridge?id=QKVY4mDivBEC&pg=PR5&sig=8KZG5MvVdHKKRcLYdN91fGyIrBQ#PPA167,M1 |publisher=Cambridge University Press|year=1995|page=167}}
+*{{cite book|author=Allen B. Tucker|title=Computer Science Handbook|publisher=CRC Press|date=2004|isbn=1-58488-360-X|page=12.19}}
+{{combin-stub}}
+[[Category:Graph theory objects]]
+[[Category:Matrices]]

Ordinal optimization: Difference between revisions

Revision as of 12:58, 30 September 2013

References

Navigation menu

Search