Augmenting Path
المؤلف:
Ford, L. R. and Fulkerson, D. R
المصدر:
Flows in Networks. Princeton, NJ: Princeton University Press, 1962.
الجزء والصفحة:
...
8-5-2022
1963
Augmenting Path
A path constructed by repeatedly finding a path of positive capacity from a source to a sink and then adding it to the flow (Skiena 1990, p. 237).
An augmenting path for a matching 
is a path with an odd number of edges 
, 
, ..., 
such that 
and 
. The symmetric difference of 
with ![<span style=]()
{e_i}" src="https://mathworld.wolfram.com/images/equations/AugmentingPath/Inline8.svg" style="height:22px; width:25px" />yields a matching having one more edge than 
. Augmenting paths are used in the blossom algorithm and Hungarian maximum matching algorithm for finding graph maximum matchings.
REFERENCES
Ford, L. R. and Fulkerson, D. R. Flows in Networks. Princeton, NJ: Princeton University Press, 1962.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
