خوارزمية هوبكروفت-كارب

هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت وكارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف.HOPCROFT, John E. et KARP, Richard M. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 1973, vol. 2, no 4, p. 225-231.

إن هذه المشكلة تحظى باهتمام عملي كبير، تم طرحها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق  وما يعرف بمشكلة تخصيص المهام في الأنظمة متعددة الروبوتات (أو أ سراب الروبوتات).

 مصطلحات خوارزمية هوبكروفت كارب 

رأس على حافة تنتمي إلى الإقتران M يقال رأس مشبع في M

رأس على حافة لا تنتمي إلى M يقال رأس حر بالنسبة إلى M

الاقتران الأقصى هو اقتران يحتوي على أكبر عدد ممكن من الحواف في (G(U,V,E

اقتران كامل في بيان ليس بالضرورة ثنائي متكون من 2N رأس، هو اقتران يتكون من N حواف
مسار M-متناوب في (G(U,V,E هو مسار تنتمي حوافه بالتناوب إلى اقتران (M ⊆ E(G و إلى المجموعته التكميلية E(G)-M

مسار M-متزايد هو مسار M-متناوب  كلا طرفيه حران

يحتوي هذا المسار على حافة واحدة في E(G)-M إضافة إلى حواف M

الخوارزمية تعتمد على نظرية بيرج (1957)BERGE, Claude. Two theorems in graph theory. Proceedings of the National Academy of Sciences of the United States of America, 1957, vol. 43, no 9, p. 842.
الاقتران M هو الاقتران الأقصى إذا وفقط إذا كان (G(U,V,E لا يحتوي على مسار M-متزايد

 خوارزمية هوبكروفت كارب (1973) 

التهيئة M ← φ
علامة φ هنا تعني المجموعة الفارغة

طالما (G(U،V،E لديه مسار M متزايد Pi

ابحث عن أكبر مجموعة من أقصر المسارات M-متزايدة {P1 ، P2 ، ... ، Pmax} التي تكون رؤوسها متمايزة
M ← M ⊖ P1 ⊖ P2 ⊖ ... ⊖ Pmax
تهاية طالما
هنا العلانة ⊖ تدل على الفرق المتناظر أو الاختلاف الحصري للمجموعات
 اِنغراز الإجراء الأساسي من أجل برمجة الخوارزمية 
تصغير
في كل خطوة أو تكرار، عملية البحث عن أكبر مجموعة من أقصر مسارات Mi-متزايدة بدون رؤوس مشتركة ترتكز على اقتران موجود Mi-1.
 وجّه (G(U,V,E بحيث تكون حواف M في اتجاه vi→ui و حواف E(G)-M في الاتجاه المعاكس ui → vi. يصبح هكذا (G(U,V,E بيانا موجها غير حلقي
 استخرج البيان الفرعي الذي تتوافق فيه الطرق الموجهة من رأس ui حر إلى رأس vi حر واحدة تلو الأخرى مع أقصر مسارات M-متزايدة، لذلك يجب :

تعليم البيان الفرعي حسب طبقات من الرؤوس ....، L0 ،L1 ، L2 ، تنتمي الطبقات الزوجية إلى U ، والطبقات الفردية إلى V. تحتوي L0 على رؤوس ui حرة، المستوى الأخير Lt هو أدنى مستوى يحتوي على رؤوس vi حرة
يجب إلغاء حواف ui→vj) E(G)-M) النازلة إلى مستوى أدنى
في الممارسة العملية، يمكن أن يؤدي تخصيص لخوارزمية BFS كل هذه الإجراءات في عملية موحدة في كل تكرار

 مراجع 

تصنيف:خوارزميات تعتمد على نظرية البيان