خوارزمية هوبكروفت-كارب
هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي (G(U,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف. هذه المشكلة NP-كاملة. خوارزمية هوبكروفت وكارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف.

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

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

رأس على حافة تنتمي إلى الإقتران 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)
الاقتران 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 كل هذه الإجراءات في عملية موحدة في كل تكرار

مراجع 

خوارزميات مخططات
هذه الخوارزمية تبحث عن الاقتران الأقصى في بيان ثنائي ( G ( U ,V,E و هو الاقتران M ذو أكبر عدد ممكن من الحواف . هذه المشكلة NP - كاملة . خوارزمية هوبكروفت وكارب أول من حلت الاقتران الأقصى في وقت متعدد الأطراف . إن هذه المشكلة تحظى ب اهتمام عمل ي كبير ، تم طرح ها في خمسينيات القرن العشرين وتبقى اليوم ذات أهمية كبيرة على سبيل المثال في ميدان التعلّم العميق و ما يعرف ب مشكلة تخصيص المهام في الأنظمة متعددة الروبوتات ( أو أ سراب الروبوتات ) . مصطلحات خوارزمية هوبكروفت كارب رأس على حافة تنتمي إلى الإقتران M يقال رأس مشبع في M رأس على حافة لا تنتمي إلى M يقال رأس حر ب النسبة إلى M الاقتران الأقصى هو اقتران يحتوي على أكبر عدد ممكن من الحواف في ( G ( U ,V,E اقتران كامل في بيان ليس ب الضرورة ثنائي متكون من رأس ، هو اقتران يتكون من N حواف مسار M - م تناوب في ( G ( U ,V,E هو مسار تنتمي حواف ه بال تناوب إلى اقتران ( M ⊆ E ( G و إلى المجموعة ه التكميلية E ( G ) - M مسار M - متزايد هو مسار M - م تناوب كلا طرفيه حران يحتوي هذا المسار على حافة واحدة في E ( G ) - M إضافة إلى حواف M الخوارزمية تعتمد على نظرية بيرج الاقتران M هو الاقتران الأقصى إذا وفقط إذا كان ( G ( U ,V,E لا يحتوي على مسار M - متزايد خوارزمية هوبكروفت كارب ال تهيئة M ← φ علامة φ هنا تعني المجموعة الفارغة طالما ( G ( U ،V،E لدي ه مسار M متزايد Pi ابحث عن أكبر مجموعة من أقصر المسارات M - متزايدة {P1 ، P2 ، \ . . . ، P max } التي تكون رؤوس ها متمايزة 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 كل هذه الإجراءات في عملية موحدة في كل تكرار مراجع خوارزميات مخططات