0
$\begingroup$

I'm reading about Berge's theorem on matching, but I think I misunderstood the theorem and definitions somehow, because I cannot make sense of the example below. In this example I've marked the matching in pink, and the alternating path in green. This is the only alternating path involving the matching that I could find, and it's clearly not an augmenting path.

enter image description here

I've realized that there is a bigger matching that could be obtained by taking out edge 3 and adding in edges 1 and 2. But since 1325679 is not an alternating path, shouldn't that possibility not be considered by the theorem?

=============================================

Here are the relevant theorem and definitions:

enter image description here

enter image description here

$\endgroup$
2
$\begingroup$

132 is an augmenting path.

It is not required that an augmenting path must contain all the edges that are in your matching so far.

(In fact it doesn't have to contain any edge that is in your matching so far -- say, if you have path graph with four vertices $a-b-c-d$ and start by matching $a$ to $b$, the augmenting path you need to match the other two nodes will consist of the edge $cd$ only).

$\endgroup$
  • $\begingroup$ I see. That's what I was suspecting: the definitions and theorem apply the criteria to each portion of the matching, not just the whole thing. I assume it's the same with alternating paths? $\endgroup$ – ensbana Aug 29 '18 at 10:24
  • 1
    $\begingroup$ @ensbana: I don't understand that comment. The definitions and theorem apply exactly as written. $\endgroup$ – hmakholm left over Monica Aug 29 '18 at 10:25
  • $\begingroup$ The definition of M-alternating path is "a path that alternates between edges in M and edges not in M". Am I right to think that it is not required that this path contains all edges of the matching? $\endgroup$ – ensbana Aug 29 '18 at 22:08
  • 1
    $\begingroup$ @ensbana: Since the definition you quote does not mention any such requirement, it is not required. $\endgroup$ – hmakholm left over Monica Aug 29 '18 at 22:10

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.