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 {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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

برعاية العتبة العباسية المقدسة.. جمعية العميد تفتح باب المشاركة في مؤتمر فتاوى الدفاع المقدسة العلمي السابع

قسم التطوير يواصل تقديم دورة أخلاقيات المهنة ضمن البرنامج التأهيلي لمنتسبي العتبة العباسية المقدسة

قسم الشؤون الفكرية يُهدي عددًا من إصداراته الثقافية لمكتبة السيدة زينب (عليها السلام) في النجف

العتبة العباسية المقدسة تشارك في الاجتماع الأول للجنة الوطنية الدائمة لتعزيز ذاكرة الألم في العراق

المزيد

الآخبار الصحية

حالة صحية شائعة قد تُخفي "إنذارا مبكرا" للإصابة بالسرطان !

"أوميغا 3" صديق القلب.. هل يربك سكر الدم؟

بدائل لليمون.. 8 إضافات للماء تعزز فوائده الصحية

دراسة: محاولة متعمدة لنشر الإنفلونزا تنتهي بـ"مفاجأة"

المزيد

الآخبار التكنلوجية

سلامة الأطفال: سبع قواعد ذهبية للركوب الآمن بالسيارة

توقع خطير لماسك: الروبوتات ستتفوق على البشر من حيث العدد

دراسة تكشف عاملا غير متوقع يرتبط بزيادة خطر الإصابة بالتوحد

"ميتا" توقف وصول المراهقين إلى شخصيات الذكاء الاصطناعي ؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength