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.

Текущая версия от 17:25, 22 ноября 2011

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

Given a chain [math]\displaystyle{ P = v_{0},v_{1},\ldots,v_{k} }[/math], [math]\displaystyle{ \,P }[/math] is alternating with respect to a matching [math]\displaystyle{ \,M }[/math] if each edge in [math]\displaystyle{ \,P }[/math] that does not belong to [math]\displaystyle{ \,M }[/math] is followed in [math]\displaystyle{ \,P }[/math] by an edge that belongs to [math]\displaystyle{ \,M }[/math], and vice versa. If [math]\displaystyle{ \,P }[/math] is alternating, the index [math]\displaystyle{ \,k }[/math] is odd, and [math]\displaystyle{ \,v_{0}, v_{k} \not \in V(M) }[/math], then [math]\displaystyle{ \,P }[/math] is augmenting with respect to [math]\displaystyle{ \,M }[/math]. A well known result due to Berge states that [math]\displaystyle{ \,M }[/math] is maximum if and only if [math]\displaystyle{ \,M }[/math] does not admit any augmenting chains.