Dulmage–Mendelsohn decomposition

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In graph theory, the Dulmage–Mendelsohn decomposition is a partition of the vertices of a bipartite graph into subsets, with the property that two adjacent vertices belong to the same subset if and only if they are paired with each other in a perfect matching of the graph. It is named after A. L. Dulmage and Nathan Mendelsohn, who published it in 1958.

The coarse decomposition[edit]

Let G = (U,V,E) be a bipartite graph, and let D be the set of vertices in G that are not matched in at least one maximum matching of G. Then D is necessarily an independent set, so G can be partitioned into three parts:

  • The vertices in DU and their neighbors
  • The vertices in DV and their neighbors
  • The remaining vertices

Every maximum matching in G consists of matchings in the first and second part that match all neighbors of D, together with a perfect matching of the remaining vertices.

The fine decomposition[edit]

The third set of vertices in the coarse decomposition (or all vertices in a graph with a perfect matching) may additionally be partitioned into subsets by the following steps:

  • Find a perfect matching of G.
  • Form a directed graph H whose vertices are the matched edges in G. For each unmatched edge (u,v) in G, add a directed edge in H from the matched edge of u to the matched edge of v.
  • Find the strongly connected components of the resulting graph.
  • For each component of H, form a subset of the Dulmage–Mendelsohn decomposition consisting of the vertices in G that are endpoints of edges in the component.

To see that this subdivision into subsets characterizes the edges that belong to perfect matchings, suppose that two vertices u and v in G belong to the same subset of the decomposition, but are not already matched by the initial perfect matching. Then there exists a strongly connected component in H containing edge uv. This edge must belong to a simple cycle in H (by the definition of strong connectivity) which necessarily corresponds to an alternating cycle in G (a cycle whose edges alternate between matched and unmatched edges). This alternating cycle may be used to modify the initial perfect matching to produce a new matching containing edge uv.

An edge uv of the graph G belongs to all perfect matchings of G, if and only if u and v are the only members of their set in the decomposition. Such an edge exists if and only if the matching preclusion number of the graph is one.

Applications[edit]

This decomposition has been used to partition meshes in finite element analysis, and to determine specified, underspecified and overspecified equations in systems of nonlinear equations.

References[edit]

External links[edit]

  • A good explanation of its application to systems of nonlinear equations is available in this paper: [1]
  • An open source implementation of the algorithm is available as a part of the sparse-matrix library: SPOOLES
  • Graph-theoretical aspects of constraint solving in the SST project: [2]