Alternating chain

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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