# Dictionary Definition

matching adj

2 intentionally matched; "curtains and walls were
color coordinated" [syn: coordinated]

# User Contributed Dictionary

## English

### Pronunciation

- /ˈmætʃɪŋ/

#### Translations

the same as another; sharing the same design

- German: zusammenpassend

### Verb

matching### Noun

- In the context of "graph theory": A set of independent edges in a given graph, i.e. a set of edges which do not intersect: so-called because pairs of vertices are "matched" to each other one-to-one.

#### Related terms

# Extensive Definition

- ''This article is about mathematical matchings. For other senses of this word, see matching (disambiguation).

In the mathematical discipline of
graph
theory a matching or edge independent set in a graph
is a set of edges without common vertices.
It may also be an entire graph consisting of edges without common
vertices.

## Definition

Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex.We say that a vertex is matched if it is incident
to an edge in the matching. Otherwise the vertex is
unmatched.

A maximal matching is a matching M of a graph G
with the property that if any edge not in M is added to M, it is no
longer a matching, that is, M is maximal if it is not a proper
subset of any other matching in graph G. In other words, a matching
M of a graph G is maximal if every edge in G has a non-empty
intersection with at least one edge in M.

A maximum matching is a matching that contains
the largest possible number of edges. There may be many maximum
matchings. The matching number of a graph is the size of a maximum
matching. Note that every maximum matching must be maximal, but not
every maximal matching must be maximum.

A perfect matching is a matching which covers all
vertices of the graph. That is, every vertex of the graph is
incident
to exactly one edge of the matching. Every perfect matching is
maximum and hence maximal. In some literature, the term complete
matching is used.

Given a matching M,

- an alternating path is a path in which the edges belong alternatively to the matching and not to the matching.
- an augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.

One can prove that a matching is maximum if and
only if it does not have any augmenting path.

## Matchings in bipartite graphs

Matching problems are often concerned with bipartite graphs. Finding a maximum bipartite matching (often called a maximum cardinality bipartite matching) in a bipartite graph G=(V=(X,Y),E) is perhaps the simplest problem. The augmenting path algorithm finds it by finding an augmenting path from each x \in X to Y and adding it to the matching if it exists. As each path can be found in O(E) time, the running time is O(V E). This solution is equivalent to adding a super source s with edges to all vertices in X, and a super sink t with edges from all vertices in Y, and finding a maximal flow from s to t. All edges with flow from X to Y then constitute a maximum matching. An improvement over this is the Hopcroft-Karp algorithm, which runs in O(\sqrt E) time.In a weighted
bipartite graph, each edge has an associated value. A maximum
weighted bipartite matching

In 1971, Haruo Hosoya
defined topological
index (a graph
invariant) as the total number of matchings of a graph plus 1.
The Hosoya index is often used in computer chemistry investigations
for organic compounds.

## Properties

- For a graph G with n vertices having no isolated vertex the matching number + edge covering number = n
- A graph with n vertices and a perfect matching has a matching number of n/2.

## See also

## References

## Additional reading

## External links

A graph library with Hopcroft-Karp and Push-Relabel based maximum cardinality matching implementationmatching in Czech: Párování grafu

matching in German: Paarung
(Graphentheorie)

matching in Spanish: Matching

matching in French: Appariement
(mathématiques)

matching in Korean: 매칭

matching in Hebrew: שידוך (תורת הגרפים)

matching in Japanese: マッチング (グラフ理論)

matching in Polish: Skojarzenie (teoria
grafów)

# Synonyms, Antonyms and Related Words

Olympic games, Olympics, allegory, analogous, analogy, balancing, bout, chromatic, cold, colorific, coloring, comparable, comparative
anatomy, comparative degree, comparative grammar, comparative
judgment, comparative linguistics, comparative literature,
comparative method, compare, comparing, comparison, complementary, concours, confrontation, confrontment, contest, contrast, contrastiveness,
cool, correlation, correspondent, corresponding, derby, dichromatic, distinction, distinctiveness,
duplicate, encounter, engagement, equivalent, fight, game, games, glowing, go, gymkhana, harmonious, homologous, identical, joust, like, likening, many-colored,
match, medley, meet, meeting, metaphor, monochromatic, monochrome, monochromic, motley, of a kind, of a piece, of
a size, opposing,
opposition, parallel, paralleling, parallelism, parti-colored,
pigmentary, polychromatic, prismatic, proportion, rainbow, rally, relation, rencontre, simile, similitude, spectral, test, tilt, tinctorial, tingent, toning, tournament, tourney, trial, trope of comparison,
twin, variegated, warm, weighing