Matchings in graphs: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 27: Line 27:


'''Statement:'''
'''Statement:'''
Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>C</math> a blossom. Further, let <math>G'=(V',E')</math> be  the undirected graph resulting from shrinking <math>C</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is a comnforming augmenting path in <math>G</math> with respect to <math>M</math> if, and only if, there is an augmenting path in <math>G'</math> with respect to <math>M'</math> that contains <math>v_C</math>.
Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>C</math> a blossom. Further, let <math>G'=(V',E')</math> be  the undirected graph resulting from shrinking <math>C</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is a conforming augmenting path in <math>G</math> with respect to <math>M</math> if, and only if, there is an augmenting path in <math>G'</math> with respect to <math>M'</math> that contains <math>u_C</math>.


'''Proof:'''
'''Proof:'''
First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>C</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>v_C</math>.
First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>C</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>u_C</math>.


So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>v_C</math>. Then <math>p</math> contains the stem of <math>c</math> because this is the only matched edge incident to <math>v_C</math>. Let <math>v</math> be the node of <math>C</math> incident to the stem and let <math>w</math> be the node on <math>p</math> that is farthest away from <math>v</math> on <math>p</math> among all nodes of <math>p</math> that also belong to <math>C</math>. Exactly one of the two subpaths of <math>C</math> from <math>v</math> to <math>w</math> yields an conforming augmenting path by concatenation with the two subpaths of <math>p</math> from the end nodes of <math>p</math> up to <marth>v</math> and <math>w</math>, respectively.
So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>u_C</math>. Then <math>p</math> contains the stem of <math>c</math> because this is the only matched edge incident to <math>u_C</math>. Let <math>v</math> be the node of <math>C</math> incident to the stem and let <math>w</math> be the node on <math>p</math> that is farthest away from <math>v</math> on <math>p</math> among all nodes of <math>p</math> that also belong to <math>C</math>. Exactly one of the two subpaths of <math>C</math> from <math>v</math> to <math>w</math> yields an conforming augmenting path by concatenation with the two subpaths of <math>p</math> from the end nodes of <math>p</math> up to <marth>v</math> and <math>w</math>, respectively.

Revision as of 19:15, 21 November 2014

Matchings

  1. Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A matching in [math]\displaystyle{ G }[/math] is a set [math]\displaystyle{ M\subseteq E }[/math] of edges such that no two edges in [math]\displaystyle{ M }[/math] are incident.
  2. A node [math]\displaystyle{ v\in V }[/math] is matched with respect to a matching [math]\displaystyle{ M }[/math] if it is incident to a member of [math]\displaystyle{ M }[/math]; otherwise, [math]\displaystyle{ v }[/math] is called free or exposed.
  3. A matching is called perfect if there is no exposed node.

Remark: A perfect matching [math]\displaystyle{ M }[/math] is only possible if [math]\displaystyle{ |V| }[/math] is even. Then [math]\displaystyle{ M }[/math] is perfect if, and only if, [math]\displaystyle{ |M|=|V|/2 }[/math].

Alternating and augmenting paths

  1. A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called alternating with respect to some matching [math]\displaystyle{ M }[/math] if, for any two subsequent edges on [math]\displaystyle{ p }[/math], exactly one of them belongs to [math]\displaystyle{ M }[/math]. In other words, the edges in [math]\displaystyle{ M }[/math] and the edges not in [math]\displaystyle{ M }[/math] appear strictly alternatingly on [math]\displaystyle{ p }[/math].
  2. A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called augmenting with respect to some matching [math]\displaystyle{ M }[/math] if [math]\displaystyle{ p }[/math] is alternating and both of its end nodes are exposed.
  3. Augmenting a matching [math]\displaystyle{ M }[/math] along an augmenting path [math]\displaystyle{ p }[/math] means increasing the size of [math]\displaystyle{ M }[/math] by one as follows:
    1. Each edge of [math]\displaystyle{ p }[/math] that was in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is removed from [math]\displaystyle{ M }[/math].
    2. Each edge of [math]\displaystyle{ p }[/math] that was not in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is inserted in [math]\displaystyle{ M }[/math].

Blossoms

Definitions:

  1. A blossom is a cycle [math]\displaystyle{ C }[/math] of odd length in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|C|/2\rfloor }[/math] edges on [math]\displaystyle{ C }[/math] are matched and the remaining node on [math]\displaystyle{ C }[/math] is matched as well (by an edge not on [math]\displaystyle{ C }[/math], in fact, which is called the stem of the blossom).
  2. Shrinking a blossom [math]\displaystyle{ C }[/math] means:
    1. Insert a new node [math]\displaystyle{ u_C }[/math] in [math]\displaystyle{ V }[/math].
    2. For each edge [math]\displaystyle{ \{v,w\} }[/math] such that [math]\displaystyle{ v }[/math] is on [math]\displaystyle{ C }[/math] and [math]\displaystyle{ w }[/math] is not: Replace [math]\displaystyle{ \{v,w\} }[/math] by a new edge [math]\displaystyle{ \{v_C,w\} }[/math].
    3. Remove all nodes and edges on [math]\displaystyle{ C }[/math].
  3. An augmenting path [math]\displaystyle{ p }[/math] conforms to [math]\displaystyle{ C }[/math] if [math]\displaystyle{ p }[/math] contains the stem.

Statement: Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph, [math]\displaystyle{ M }[/math] a matching in [math]\displaystyle{ G }[/math], and [math]\displaystyle{ C }[/math] a blossom. Further, let [math]\displaystyle{ G'=(V',E') }[/math] be the undirected graph resulting from shrinking [math]\displaystyle{ C }[/math], and let [math]\displaystyle{ M' }[/math] be the restriction of [math]\displaystyle{ M }[/math] to [math]\displaystyle{ G' }[/math]. There is a conforming augmenting path in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ M }[/math] if, and only if, there is an augmenting path in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M' }[/math] that contains [math]\displaystyle{ u_C }[/math].

Proof: First suppose there is a conforming augmenting path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ M }[/math]. According to either possible orientation of [math]\displaystyle{ p }[/math], let [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] denote the first and the last node of [math]\displaystyle{ p }[/math]. Moreover, let [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] denote the first and the last node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ C }[/math] (possibly [math]\displaystyle{ v=w }[/math]). The concatenation of the subpaths of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] and from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ t }[/math] is an augmenting path in [math]\displaystyle{ G' }[/math], and this path contains [math]\displaystyle{ u_C }[/math].

So, consider the case that there is an augmenting path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M' }[/math], and that [math]\displaystyle{ p }[/math] contains [math]\displaystyle{ u_C }[/math]. Then [math]\displaystyle{ p }[/math] contains the stem of [math]\displaystyle{ c }[/math] because this is the only matched edge incident to [math]\displaystyle{ u_C }[/math]. Let [math]\displaystyle{ v }[/math] be the node of [math]\displaystyle{ C }[/math] incident to the stem and let [math]\displaystyle{ w }[/math] be the node on [math]\displaystyle{ p }[/math] that is farthest away from [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] among all nodes of [math]\displaystyle{ p }[/math] that also belong to [math]\displaystyle{ C }[/math]. Exactly one of the two subpaths of [math]\displaystyle{ C }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] yields an conforming augmenting path by concatenation with the two subpaths of [math]\displaystyle{ p }[/math] from the end nodes of [math]\displaystyle{ p }[/math] up to <marth>v</math> and [math]\displaystyle{ w }[/math], respectively.