1
$\begingroup$

I have been given the following matching: $$ M =\{ \{a,3\}, \{b,1\},\{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$ in the bipartite graph: enter image description here The matching looks like: enter image description here

I applied the augmented path method to get the following 2 red edges, which we exchange for 1 green edge - that's a good deal! enter image description here Which gives a better matching of the form: $$ M' =\{ \{a,3\}, \{b,2\},\{c, 1\}, \{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$

enter image description here

How do I know whether or not this matching is maximal? normally one gets a minimum vertex cover as a dual property of a maximum matching, how would one apply this to the current problem?


Edit: I think my real question would be how do I find a minimum vertex cover to see if this matching is maximal (cardinality should be the same).

$\endgroup$
  • $\begingroup$ Do you know how to find a minimum vertex cover from a maximum matching? $\endgroup$ – Misha Lavrov Jan 15 at 19:26
  • $\begingroup$ König tells me that "If G is bipartite, the cardinality of the maximum matching is equal to the cardinality of the minimum vertex cover." I know that a vertex cover is a set of vertices that are adjacent to every single edge in the graph AND I know that the augmenting path method terminates to give me a maximum matching - I'm just kind of stuck right now because every path I continue to use just leads nowhere. $\endgroup$ – Wesley Strik Jan 15 at 19:53
  • $\begingroup$ So I know what a cover is, but I'm having trouble finding one. I think the answer to your question would be no. $\endgroup$ – Wesley Strik Jan 15 at 19:55
  • $\begingroup$ I know how to find a Hall set thought, but that's a slightly different variation of the problem. $\endgroup$ – Wesley Strik Jan 15 at 19:55
1
$\begingroup$

If you have a maximum matching, then you won't be able to find an augmenting path (of course) and the search for possible augmenting paths will produce a vertex cover.

For example, for your second matching (of size $8$) an augmenting path should:

  • start at one of the vertices $\{8,10\}$, which are not covered by the matching yet.
  • from there, go to one of their neighbors: $\{b, g, h\}$.
  • from there, take an edge of the matching, going to the corresponding vertex from $\{2,6,7\}$.
  • from there, go to one of their neighbors: of vertices we haven't seen yet, that's just $\{f\}$.
  • from there, take an edge of the matching, going to $\{5\}$.
  • from there, we're stuck, because no edges out of $5$ go to a new vertex we haven't seen before. There's no way to get to $e$ or $j$.

So this is a proof that there's no augmenting path. (Note: we could have done this search from the other direction, starting at the uncovered vertices $\{e,j\}$. Just checking one direction is enough, because any augmenting path would connect one of $\{8,10\}$ to one of $\{e,j\}$.)

We can use the search to find a minimum vertex cover, which is a more concise proof of optimality. Start with the vertices $\{b,f,g,h\}$, which cover all edges between vertices we've considered in our search. If we add in the vertices from the bottom part we haven't seen in our search - the vertices $\{1,3,4,9\}$ - then the resulting set $$ \{1, 3, 4, 9, b, f, g, h\} $$ is a vertex cover of the same size as the matching.

(In general, in a graph with bipartition $(A,B)$ if you start a search from the unmatched vertices on side $A$, and you don't find an augmenting path, you can find a minimum vertex cover by taking the vertices on side $B$ you do see, together with the vertices on side $A$ you don't see. There can't be an uncovered edge - which would go from a vertex on side $A$ you do see from a vertex on side $B$ you don't see - because then that vertex on side $B$ would become one of the ones you do explore.)

$\endgroup$
  • $\begingroup$ Thank you, this explained exactly what I did not understand, and this was precisely what I was doing when I got stuck, but I was missing the formal argument to make it a coherent whole- if that makes sense. $\endgroup$ – Wesley Strik Jan 15 at 22:07

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.