Database Reference
In-Depth Information
Figure 8.1
A bipartite graph
8.3.1
Matches and Perfect Matches
Suppose we are given a bipartite graph. A
matching
is a subset of the edges such that no
node is an end of two or more edges. A matching is said to be
perfect
if every node appears
in the matching. Note that a matching can only be perfect if the left and right sets are of
the same size. A matching that is as large as any other matching for the graph in question
is said to be
maximal
.
EXAMPLE
8.4 The set of edges {(1
, a
)
,
(2
, b
)
,
(3
, d
)} is a matching for the bipartite graph
of
Fig. 8.1
. Each member of the set is an edge of the bipartite graph, and no node appears
more than once. The set of edges
{(1
, c
)
,
(2
, b
)
,
(3
, d
)
,
(4
, a
)}
once. It is, in fact, the sole perfect matching for this graph, although some bipartite graphs
have more than one perfect matching. The matching of
Fig. 8.2
is also maximal, since every
perfect matching is maximal.
□
Figure 8.2
The only perfect matching for the graph of
Fig. 8.1
8.3.2
The Greedy Algorithm for Maximal Matching
Off-line algorithms for finding a maximal matching have been studied for decades, and one
can get very close to
O
(
n
2
) for an
n
-node graph. On-line algorithms for the problem have
also been studied, and it is this class of algorithms we shall consider here. In particular,
the greedy algorithm for maximal matching works as follows. We consider the edges in
whatever order they are given. When we consider (
x, y
), add this edge to the matching if
neither
x
nor
y
are ends of any edge selected for the matching so far. Otherwise, skip (
x, y
).
