Matchings
Learn to identify different types of matchings within graphs, including maximum and perfect matchings. Understand how maximum matchings apply to bipartite graphs for practical uses such as assigning resources to tasks. This lesson helps clarify key terms and concepts essential for solving matching problems in graph theory.
We'll cover the following...
We'll cover the following...
Matchings and related terminology
A matching of an undirected graph is any collection of its edges that have no end-vertex in common. In other words, each edge in uniquely pairs or matches two vertices. We refer to the number of edges in a matching as the size of the matching .
If a vertex appears as an end-vertex of an edge in ...