2
$\begingroup$

I am reading "Data Structures and Algorithms" by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman.

The key observation is that $M$ is a maximal matching if and only if there is no augmenting path relative to $M$. This observation is the basis of our maximal matching algorithm.

Suppose $M$ and $N$ are matchings with $|M| < |N|$. ( $|M|$ denotes the number of edges in $M$.) To see that $M \oplus N$ contains an augmenting path relative to $M$ consider the graph $G^{'} = (V, M \oplus N)$. Since $M$ and $N$ are both matchings, each vertex of $V$ is an endpoint of at most one edge from $M$ and an endpoint of at most one edge from $N$. Thus each connected component of $G^{'}$ forms a simple path (possibly a cycle) with edges alternating between $M$ and $N$. Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$.
...

I cannot understand the above proof of a proposition about maximum matching. (By the way, I don't know why the authors use the word maximal instead of maximum.)

The authors wrote "Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$.".

I think this is not correct.

I think the following is correct:

"Each path that is not a cycle is either an augmenting path relative to $M$ or an augmenting path relative to $N$ depending on whether it has more edges from $N$ or from $M$ or an even length simple path with edges alternating between $M$ and $N$ .".

Am I wrong or right?

$\endgroup$
2
$\begingroup$

I think you are right: there could also be paths with the same number of edges in each, which are not augmenting paths. However, the fact that $|M|<|N|$ still means that there is at least one path with more edges from $N$ than from $M$ (cycles must have the same number of each) and hence there is an augmenting path for $M$.

Incidentally, the normal distinction between "maximum matching" and "maximal matching" is that a "maximum matching" is one of the largest possible size, whereas a "maximal matching" is one that can't be extended by adding an edge. In this sense, however, they are using the wrong word since they are clearly talking about maximum matchings.

$\endgroup$
  • $\begingroup$ Thank you very much, Especially Lime. $\endgroup$ – tchappy ha Nov 13 '18 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.