Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Alternating chain''' --- альтернирующая цепь, чередующаяся цепь. Given a chain <math>P = v_{0},v_{1...)
 
Нет описания правки
 
Строка 1: Строка 1:
'''Alternating chain''' --- альтернирующая цепь, чередующаяся цепь.  
'''Alternating chain''' — ''[[альтернирующая цепь]], [[чередующаяся цепь]].''


Given a chain <math>P = v_{0},v_{1},\ldots,v_{k}</math>, <math>P</math> is '''alternating'''
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
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
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},
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
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
<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.
and only if <math>\,M</math> does not admit any augmenting chains.