Matching (graph theory)

A matching in a graph is a set of edges that share no endpoints. It is maximal if no edge can be added, and maximum if it has the largest possible size.

Graph (discrete mathematics): A structure consisting of vertices and edges that connect pairs of vertices. A matching is defined by selecting edges from a graph.
Augmenting path: A path whose edges alternate between outside and inside a matching and whose endpoints are unmatched. Flipping its selected and unselected edges increases the matching's size.
Bipartite matching: A matching in a graph whose vertices are divided into two sets and whose edges cross between them. Many practical pairing problems have two distinct sides, such as workers and jobs.
Edge cover: A set of edges incident to every vertex in a graph. An edge cover must touch every vertex, while a matching forbids shared endpoints.
Vertex: A vertex is a point in a graph, also called a node. The no-shared-endpoints rule means each vertex belongs to at most one selected edge.
Alternating path: A path whose edges alternate between belonging to a matching and not belonging to it. Alternation describes the structure used to rearrange matched edges.
Assignment problem: An optimization problem that assigns agents to tasks while minimizing cost or maximizing benefit. Its one-to-one assignments are modeled by matchings, often with edge weights.
Vertex cover: A set of vertices containing at least one endpoint of every edge in a graph. It selects vertices to cover edges rather than selecting disjoint edges.
Edge (graph theory): An edge is a connection between two vertices in a graph. A matching is a subset of the graph's edges.
Symmetric difference: The elements belonging to exactly one of two sets. The difference between two matchings decomposes into paths and cycles that expose possible improvements.

Linked from 19 pages