Alternating chain: различия между версиями

'''Alternating chain''' --- альтернирующая цепь, чередующаяся цепь.  

Given a chain <math>P = v_{0},v_{1},\ldots,v_{k}</math>, <math>P</math> is '''alternating'''

with respect to a ''matching'' <math>M</math> if each edge in <math>P</math> that does not

belong to <math>M</math> is followed in <math>P</math> by an edge that belongs to <math>M</math>, and

vice versa. If <math>P</math> is alternating, the index <math>k</math> is odd, and <math>v_{0},

v_{k} \not \in V(M)</math>, then <math>P</math> is '''augmenting''' with respect to

<math>M</math>. A well known result due to Berge states that <math>M</math> is maximum if

and only if <math>M</math> does not admit any augmenting chains.