مطابقة الحد الأقصى للعددية

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 9 صور
الموسوعة الحرة
يحتوي الرسم البياني الموجود على اليمين على عدد أقصى من العناصر أقل بواحد من الرسم البياني الموجود على اليسار، على الرغم من حقيقة أن كلاهما يحتوي على نفس عدد الرؤوس.

في نظرية المخططات ، يُعدّ التطابق ذو العدد الأقصى من العناصر نوعًا خاصًا من المخططات الفرعية، وهو مفيد في العديد من السياقات الحسابية. بالنسبة لمخطط G ، يُعرَّف التطابق بأنه مخطط فرعي لا يشترك فيه أي ضلعين في رأس واحد. عدد عناصر التطابق هو عدد الأضلاع في المخطط الفرعي، والعدد الأقصى للعناصر هو أكبر عدد من الأضلاع التي يمكن أن يحتويها التطابق. يُسمى التطابق لمخطط معين تطابقًا ذا عدد أقصى من العناصر إذا كان عدد عناصره هو هذا العدد الأقصى. إذا اعتبرنا أن كل ضلع "يغطي" الرؤوس التي يربطها مرة واحدة فقط، فإن التطابق الأقصى هو أيضًا أكبر غطاء غير متداخل للمخطط. إذا تم تغطية جميع الرؤوس، يُطلق عليه اسم التطابق الكامل . بالنسبة للمخططات المحدودة، يوجد دائمًا تطابق ذو عدد أقصى من العناصر، ولكنه ليس فريدًا عادةً. لا يتجاوز عدد عناصر التطابق أبدًا نصف عدد الرؤوس، ولا يتجاوز أيضًا عدد الأضلاع.

تُعدّ حالة خاصة مهمة من مسألة المطابقة ذات العدد الأقصى للعناصر هي عندما يكون G رسمًا بيانيًا ثنائي الأجزاء يُمثّل علاقة ثنائية ، حيث تُقسّم رؤوسه V بين رؤوس يسرى في X ورؤوس يمنى في Y ، وتربط الحواف في E دائمًا رأسًا يسرى برأس يميني. في هذه الحالة، يُمكن حلّ المسألة بكفاءة باستخدام خوارزميات أبسط من تلك المُستخدمة في الحالة العامة.

يُعدّ حساب التطابق الأقصى لرسم بياني مُعطى مهمةً أساسيةً في نظرية الرسوم البيانية الحاسوبية . [ 1 ] توجد نظريات توصيف غير بنائية لحجم التطابق الأقصى. تتناول هذه المقالة حساب التطابقات القصوى.

خوارزميات للرسوم البيانية ثنائية الأجزاء

خوارزمية قائمة على التدفق

أبسط طريقة لحساب مطابقة ذات عدد عناصر أقصى هي اتباع خوارزمية فورد-فولكرسون . تحل هذه الخوارزمية المشكلة الأكثر عمومية المتمثلة في حساب التدفق الأقصى . يمكن تحويل الرسم البياني الثنائي ( X + Y , E ) إلى شبكة تدفق كما يلي.

  • أضف رأس مصدر s ؛ أضف حافة من s إلى كل رأس في X.
  • أضف رأسًا مصبًا t ؛ أضف حافة من كل رأس في Y إلى t .
  • قم بتعيين سعة مقدارها 1 لكل حافة.

بما أن لكل حافة في الشبكة سعة عددية صحيحة، فإنه يوجد تدفق أقصى تكون فيه جميع التدفقات أعدادًا صحيحة؛ يجب أن تكون هذه الأعداد الصحيحة إما 0 أو 1 لأن جميع السعات تساوي 1. يحدد كل تدفق عددي صحيح مطابقة تكون فيها الحافة ضمن المطابقة إذا وفقط إذا كان تدفقها يساوي 1. وهي مطابقة لأن:

  • التدفق الوارد إلى كل رأس في X هو 1 على الأكثر، لذا فإن التدفق الصادر هو 1 على الأكثر أيضًا، لذلك يوجد على الأكثر حافة واحدة مجاورة لكل رأس في X.
  • التدفق الخارج من كل رأس في Y هو 1 على الأكثر، لذا فإن التدفق الداخل هو 1 على الأكثر أيضًا، لذلك يوجد على الأكثر حافة واحدة مجاورة لكل رأس في Y.

تعتمد خوارزمية فورد-فولكرسون على إيجاد مسار مُعزز من نقطة x ∈ X إلى نقطة y ∈ Y بشكل متكرر ، ثم تحديث المطابقة M بأخذ الفرق المتناظر بين هذا المسار و M (بافتراض وجود مثل هذا المسار). وبما أنه يمكن إيجاد كل مسار في زمن O ( E ) ، فإن زمن التشغيل هو O ( VE ) ، وتتكون المطابقة القصوى من حواف E التي تحمل التدفق من X إلى Y.

خوارزميات متقدمة

يُعدّ خوارزمية هوبكروفت-كارب الأكثر تعقيدًا تحسينًا لهذه الخوارزمية ، حيث تبحث عن مسارات تعزيز متعددة في آنٍ واحد. تعمل هذه الخوارزمية فييا(Vهـ){\displaystyle O({\sqrt {V}}E)}وقت.

تستغرق خوارزمية تشاندرا وهوشباوم [ 2 ] للرسوم البيانية ثنائية الأجزاء وقتًا يعتمد على حجم المطابقة القصوى k ، والذي يكون عندما يكون | X | < | Y | هو

يا(مين{|X|ك،هـ}+كمين{ك2،هـ}).{\displaystyle O\left(\min\{|X|k,E\}+{\sqrt {k}}\min\{k^{2},E\}\right).}

استخدام العمليات المنطقية على الكلمات ذات الحجمλ{\displaystyle \lambda }تم تحسين التعقيد بشكل أكبر إلى [ 2 ]

يا(مين{|X|ك،|X||Y|λ،هـ}+ك2+ك2.5λ).{\displaystyle O\left(\min \left\{|X|k,{\frac {|X||Y|}{\lambda }},E\right\}+k^{2}+{\frac {k^{2.5}}{\lambda }}\right).}

توجد خوارزميات أكثر كفاءة لأنواع خاصة من الرسوم البيانية ثنائية الأجزاء:

  • بالنسبة للرسوم البيانية الثنائية المتفرقة ، يمكن حل مشكلة المطابقة القصوى فييا~(هـ10/7){\displaystyle {\tilde {O}}(E^{10/7})}باستخدام خوارزمية مادري القائمة على التدفقات الكهربائية. [ 3 ]
  • بالنسبة للرسوم البيانية ثنائية الأجزاء المستوية ، يمكن حل المشكلة في زمن O ( n log 3 n ) حيث n هو عدد الرؤوس، وذلك عن طريق اختزال المشكلة إلى تدفق أقصى مع مصادر ومصارف متعددة. [ 4 ]

خوارزميات للرسوم البيانية العشوائية

تجد خوارزمية بلوسوم تطابقًا ذا عدد أقصى من العناصر في الرسوم البيانية العامة (ليس بالضرورة ثنائية الأجزاء). وتعمل في وقتيا(|V|2⋅|هـ|){\displaystyle O(|V|^{2}\cdot |E|)}يمكن تحقيق أداء أفضل من رتبة O(√VE ) للرسوم البيانية العامة ، يضاهي أداء خوارزمية هوبكروفت-كارب على الرسوم البيانية ثنائية الأجزاء ، باستخدام خوارزمية ميكالي وفازيراني الأكثر تعقيدًا. [ 5 ] وقد تم تحقيق الحد نفسه بواسطة خوارزمية بلوم [ 6 ] وخوارزمية جابو وتارجان . [ 7 ]

يستخدم نهج بديل التوزيع العشوائي ويعتمد على خوارزمية ضرب المصفوفات السريعة . وهذا يوفر خوارزمية عشوائية للرسوم البيانية العامة ذات تعقيديا(V2.372){\displaystyle O(V^{2.372})}[ 8 ] هذا أفضل نظرياً للرسوم البيانية الكثيفة بما فيه الكفاية ، ولكن عملياً تكون الخوارزمية أبطأ. [ 2 ]

استعرض دوان وبيتي [ 9 ] خوارزميات أخرى لهذه المهمة (انظر الجدول الأول). وفيما يتعلق بخوارزميات التقريب ، أشارا أيضًا إلى أن خوارزمية بلوسوم وخوارزميات ميكالي وفازيراني يمكن اعتبارها خوارزميات تقريب تعمل في زمن خطي لأي حد خطأ ثابت.

التطبيقات والتعميمات

مراجع

  1. ↑ ويست، دوغلاس برنت (1999)، مقدمة في نظرية الرسم البياني (  الطبعة الثانية)، برنتيس هول، الفصل 3، رقم ISBN 0-13-014400-2
  2. 1 2 3 تشاندرا، بالا جي؛ هوشباوم، دوريت إس (2011)، تحسينات عملية ونظرية للمطابقة الثنائية باستخدام خوارزمية التدفق الزائف ، arXiv : 1105.1569 ، Bibcode : 2011arXiv1105.1569C ، تميل الخوارزميات الفعالة نظريًا والمذكورة أعلاه إلى الأداء الضعيف عمليًا..
  3. ↑ مادري، أ. (2013)، "التنقل في المسار المركزي باستخدام التدفقات الكهربائية: من التدفقات إلى المطابقات، والعودة"، أسس علوم الحاسوب (FOCS)، الندوة السنوية الرابعة والخمسون لمعهد مهندسي الكهرباء والإلكترونيات (IEEE) ، الصفحات 253-262 ، arXiv : 1307.2205 ، Bibcode : 2013arXiv1307.2205M 
  4. ↑ بوراديل، جلينكورا؛ كلاين، فيليب ن.؛ موزيس، شاي؛ نوسباوم، ياهف؛ وولف-نيلسن، كريستيان (2017)، "التدفق الأقصى متعدد المصادر ومتعدد المصارف في الرسوم البيانية المستوية الموجهة في وقت شبه خطي"، مجلة SIAM للحوسبة ، 46 (4): 1280-1303 ، arXiv : 1105.2228 ، doi : 10.1137/15M1042929 ، MR 3681377 ، S2CID 207071917  
  5. ^ ميكالي، س . فازيراني، في في (1980)، “آنيا(|V|⋅|هـ|){\displaystyle \scriptstyle O({\sqrt {|V|}}\cdot |E|)}"خوارزمية لإيجاد التطابق الأقصى في الرسوم البيانية العامة"، وقائع الندوة الحادية والعشرين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، الصفحات 17-27 ، doi : 10.1109/SFCS.1980.12 ، S2CID 27467816  .
  6. ↑ بلوم، نوربرت (1990)، "نهج جديد للمطابقة القصوى في الرسوم البيانية العامة" (ملف PDF) ، في باترسون، مايك (محرر)، الأوتوماتا واللغات والبرمجة، الندوة الدولية السابعة عشرة، ICALP90، جامعة وارويك، إنجلترا، المملكة المتحدة، 16-20 يوليو 1990، وقائع ، سلسلة محاضرات في علوم الحاسوب، المجلد 443، سبرينغر، الصفحات 586-597 ، doi : 10.1007/BFb0032060  
  7. ↑ جابو، هارولد ن .؛ تارجان، روبرت إي. (1991-10-01). "خوارزميات توسيع نطاق أسرع لمشاكل مطابقة الرسوم البيانية العامة" (ملف PDF) . مجلة ACM . 38 (4): 815-853 . doi : 10.1145/115234.115366 . S2CID 18350108 . 
  8. ↑ موتشا، م.؛ سانكوفسكي، ب. (2004)، " المطابقات القصوى عبر الإزالة الغاوسية" (ملف PDF) ، وقائع الندوة الخامسة والأربعين لمؤسسة مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب ، الصفحات 248-255 
  9. ↑ دوان، ران؛ بيتي، سيث (2014-01-01). "تقريب زمني خطي لمطابقة الوزن الأقصى" (ملف PDF) . مجلة ACM . 61 : 1-23 . doi : 10.1145/2529989 . S2CID 207208641 . 
  10. ↑ كارب، ريتشارد م. (1972)، "قابلية الاختزال بين المسائل التوافقية"، في ميلر، ريموند إي.؛ ثاتشر، جيمس دبليو.؛ بولينجر، جان دي. (محررون)، تعقيد الحسابات الحاسوبية: وقائع ندوة حول تعقيد الحسابات الحاسوبية، عُقدت في الفترة من 20 إلى 22 مارس 1972، في مركز أبحاث توماس جيه واتسون التابع لشركة آي بي إم، يوركتاون هايتس، نيويورك، برعاية مكتب البحوث البحرية، وبرنامج الرياضيات، وشركة آي بي إم للتجارة العالمية، وقسم العلوم الرياضية البحثية في آي بي إم ، سلسلة ندوات أبحاث آي بي إم، بوسطن، ماساتشوستس: سبرينغر الولايات المتحدة، الصفحات 85-103 ، doi : 10.1007/978-1-4684-2001-2_9 ، ISBN  978-1-4684-2001-2