NO - Summary of Chapter 10

Nomenclature:

NOTE: In the drawings, the blue edges are the ones in the matching, while the orange ones are not.

• Matching: a subset $M$ of edges such that each node is incident (“touches”) at most 1 edge in $M$.
• Perfect matching: if the number of edges in $M^{\ast }$ is exactly half of all possible edges.
• Maximum cardinality matching: maximizes the number of edges in the $M^{\ast }$
• Weighted matching: maximizes the weights in the $M$
• Exposed node: no edge in $M$ is incident (“touches”) to this node.
• Alternating path: A path composed of alternating edges in the matching and ones that are not.
• Augmented path: An alternating path that starts and ends with two different exposed nodes.
• Matching augmentation: edge in the matching are exchanged with edges not in the matching, a matching augmentation is only valid if the number of edges in the matching increases aferword (otherwise is useless)
• Blossom: cycle with ($2k+1$) edges → $k$ edges will belong to the matching.
• Shrinking of a blossom:

---

Mathematical Formulation

• Variables: $b_{ij}$ : boolean, $1$ if $(i,j)$ belongs to $M^{\ast }$, $0$ otherwise.
  
• Objective function:

$$\max \sum _i\sum _j{b}_{ij}$$

• Constraints:

$$\sum _k{b}_{kj}+\sum _k{b}_{ik}\le 1$$

---

Edmonds’s Algorithm

Complexity: $O(n^{2}m)$ operations.

• $n$ : number of nodes
• $m$ : number of arcs