A matching in a graph means the selection of a set of edges that are pairwise non-adjacenct, i.e. they have no common incident vertices. A matching is maximal if it is not a proper subset of any other matching.
is.matching(graph, matching, types = NULL) is.maximal.matching(graph, matching, types = NULL) maximum.bipartite.matching(graph, types = NULL, weights = NULL, eps = .Machine$double.eps)
- The input graph. It might be directed, but edge directions will be ignored.
- Vertex types, if the graph is bipartite. By default they
are taken from the
vertex attribute, if present.
- A potential matching. An integer vector that gives the
pair in the matching for each vertex. For vertices without a pair,
- Potential edge weights. If the graph has an edge
, and this argument is
NULL, then the edge attribute is used automatically.
- A small real number used in equality tests in the weighted
bipartite matching algorithm. Two real numbers are considered
equal in the algorithm if their difference is smaller than
eps. This is required to avoid the accumulation of
is.matching checks a matching vector and verifies whether its
length matches the number of vertices in the given graph, its values
are between zero (inclusive) and the number of vertices (inclusive),
and whether there exists a corresponding edge in the graph for every
matched vertex pair. For bipartite graphs, it also verifies whether
the matched vertices are in different parts of the graph.
is.maximal.matching checks whether a matching is maximal.
A matching is maximal if and only if there exists no unmatched vertex
in a graph such that one of its neighbors is also unmatched.
maximum.bipartite.matching calculates a maximum matching in a
bipartite graph. A matching in a bipartite graph is a partial
assignment of vertices of the first kind to vertices of the second
kind such that each vertex of the first kind is matched to at most one
vertex of the second kind and vice versa, and matched vertices must be
connected by an edge in the graph. The size (or cardinality) of a
matching is the number of edges. A matching is a maximum matching if
there exists no other matching with larger cardinality. For weighted
graphs, a maximum matching is a matching whose edges have the largest
possible total weight among all possible matchings.
Maximum matchings in bipartite graphs are found by the push-relabel
algorithm with greedy initialization and a global relabeling after
every $n/2$ steps where $n$ is the number of vertices in the
is.maximal.matchingreturn a logical scalar.
maximum.bipartite.matchingreturns a list with components:
matching_size The size of the matching, i.e. the number of edges connecting the matched vertices. matching_weight The weights of the matching, if the graph was weighted. For unweighted graphs this is the same as the size of the matching. matching The matching itself. Numeric vertex id, or vertex names if the graph was named. Non-matched vertices are denoted by
- Maximal matching
- Maximum bipartite matching
g <- graph.formula( a-b-c-d-e-f ) m1 <- c("b", "a", "d", "c", "f", "e") # maximal matching m2 <- c("b", "a", "d", "c", NA, NA) # non-maximal matching m3 <- c("b", "c", "d", "c", NA, NA) # not a matching is.matching(g, m1) is.matching(g, m2) is.matching(g, m3) is.maximal.matching(g, m1) is.maximal.matching(g, m2) is.maximal.matching(g, m3) V(g)$type <- c(FALSE,TRUE) str(g, v=TRUE) maximum.bipartite.matching(g) g2 <- graph.formula( a-b-c-d-e-f-g ) V(g2)$type <- rep(c(FALSE,TRUE), length=vcount(g2)) str(g2, v=TRUE) maximum.bipartite.matching(g2)