You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/graph/kuhn_maximum_bipartite_matching.md
+6-6Lines changed: 6 additions & 6 deletions
Original file line number
Diff line number
Diff line change
<
8000
tr class="diff-line-row">
@@ -15,21 +15,21 @@ that no selected edge shares a vertex with any other selected edge.
15
15
### Required Definitions
16
16
17
17
* A **matching** $M$ is a set of pairwise non-adjacent edges of a graph (in other words, no more than one edge from the set should be incident to any vertex of the graph $M$).
18
-
The **cardinality** of a matching is the number of edges in it. The maximum (or largest) matching is a matching whose cardinality is maximum among all possible matchings
19
-
in a given graph. All those vertices that have an adjacent edge from the matching (i.e., which have degree exactly one in the subgraph formed by $M$) are called **saturated**
18
+
The **cardinality** of a matching is the number of edges in it.
19
+
All those vertices that have an adjacent edge from the matching (i.e., which have degree exactly one in the subgraph formed by $M$) are called **saturated**
20
20
by this matching.
21
21
22
+
* A **maximal matching** is a matching $M$ of a graph $G$ that is not a subset of any other matching.
23
+
24
+
* A **maximum matching** (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. Every maximum matching is a maximal matching.
25
+
22
26
* A **path** of length $k$ here means a *simple* path (i.e. not containing repeated vertices or edges) containing $k$ edges, unless specified otherwise.
23
27
24
28
* An **alternating path** (in a bipartite graph, with respect to some matching) is a path in which the edges alternately belong / do not belong to the matching.
25
29
26
30
* An **augmenting path** (in a bipartite graph, with respect to some matching) is an alternating path whose initial and final vertices are unsaturated, i.e.,
27
31
they do not belong in the matching.
28
32
29
-
* A **maximal matching** is a matching M of a graph G that is not a subset of any other matching.
30
-
5350
div>
31
-
* A **maximum matching** (also known as maximum-cardinality matching) is a matching that contains the largest possible number of edges. Every maximum matching is a maximal matching.
32
-
33
33
* The **symmetric difference** (also known as the **disjunctive union**) of sets $A$ and $B$, represented by $A \oplus B$, is the set of all elements that belong to exactly one of $A$ or $B$, but not to both.
34
34
That is, $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$.
0 commit comments