Párosítás javító útja | mateking
 

Párosítás javító útja

Egy $G$ gráfban az $e_1, e_2, e_3, \dots , e_n$ élsorozat az $M$ párosítás javító útja, ha

1) a megadott élsorozat egy páratlan hosszú út $G$-ben

2) az élek felváltva elemi $M$-nek:

$ e_{2k} \in M$ és $e_{2k+1} \notin M $

3) az út kezdő és végpontja nem illeszkedik semelyik $M$-beli élre sem