[ تعرٌف على ] خوارزمية هوبكروفت-كارب

تم النشر اليوم 06-12-2025 | [ تعرٌف على ] خوارزمية هوبكروفت-كارب
تم النشر اليوم [dadate] | خوارزمية هوبكروفت-كارب

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

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

شرح مبسط

تعديل - تعديل مصدري - تعديل ويكي بيانات