Finding a single ground state in the E-A spin glass is the same problem as finding a minimal matching of a graph. Here are two small reports summarizing the bipartite and general matching problems.

Bipartite Matching

Bipartite Matching refers to a graph where there are two types of nodes. Nodes of type A will only have edges to nodes of type B and vice versa. Finding a matching means that every node of type A is linked to one and only one node of type B, and vice-versa. A simple example of this would be a historical marriage problem, where one attempts to match each woman (node of type A) with one and only one man (node of type B). Having a bipartite graph makes this matching problem much simpler, as discussed in the notes (ps).

General Matching

A general matching problem occurs when there is only one type of node. The matching problem is still that each node has one and only one edge or connection to another node. An example of this might be pairing up for a field trip, where each person on the trip has to have one and only one partner. This problem is substantially more difficult than the bipartite matching problem, as discussed in the notes (ps).