8000 style changes · cp-algorithms/cp-algorithms@c3aeb45 · GitHub
[go: up one dir, main page]

Skip to content
8000

Commit c3aeb45

Browse files
Oleksandr Kulkovadamant-pwn
authored andcommitted
style changes
1 parent 36de2cc commit c3aeb45

File tree

1 file changed

+6
-6
lines changed

1 file changed

+6
-6
lines changed

src/graph/kuhn_maximum_bipartite_matching.md

Lines changed: 6 additions & 6 deletions
< 8000 tr class="diff-line-row">
Original file line numberDiff line numberDiff line change
@@ -15,21 +15,21 @@ that no selected edge shares a vertex with any other selected edge.
1515
### Required Definitions
1616

1717
* 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**
2020
by this matching.
2121

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+
2226
* A **path** of length $k$ here means a *simple* path (i.e. not containing repeated vertices or edges) containing $k$ edges, unless specified otherwise.
2327

2428
* 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.
2529

2630
* 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.,
2731
they do not belong in the matching.
2832

29-
* A **maximal matching** is a matching M of a graph G that is not a subset of any other matching.
30-
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-
3333
* 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.
3434
That is, $A \oplus B = (A - B) \cup (B - A) = (A \cup B) - (A \cap B)$.
3535

0 commit comments

Comments
 (0)
0