دورة فردية مستعرضة

📅 آخر تحديث: ٤ أغسطس ٢٠٢٦
✍️ نُشر في: ٤ أغسطس ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة
رسم بياني ذو دورة فردية بحجم 2: إزالة الرأسين السفليين الأزرقين ينتج عنه رسم بياني ثنائي الأجزاء.

في نظرية المخططات ، يُعرف اجتياز الدورة الفردية لمخطط غير موجه بأنه مجموعة من رؤوس المخطط التي تتقاطع مع كل دورة فردية في المخطط بشكل غير فارغ. يؤدي حذف رؤوس اجتياز الدورة الفردية من المخطط إلى الحصول على مخطط ثنائي الأجزاء كمخطط فرعي مستحث متبقٍ . [ 1 ]

العلاقة بغطاء الرأس

أمر مفروغ منهن{\displaystyle n}الرسم البياني ذو الرؤوسجي{\displaystyle G}يحتوي على تقاطع دوري فردي بحجمك{\displaystyle k}، إذا وفقط إذا كان حاصل الضرب الديكارتي للرسوم البيانيةجي◻ك2{\displaystyle G\square K_{2}}(رسم بياني يتكون من نسختين منجي{\displaystyle G}(مع رؤوس متناظرة لكل نسخة متصلة بحواف مطابقة مثالية ) لها غطاء رأس بحجمن+ك{\displaystyle n+k}يمكن تحويل المستعرض الدوري الفردي إلى غطاء رأسي عن طريق تضمين نسختين من كل رأس من المستعرض ونسخة واحدة من كل رأس متبقٍ، يتم اختيارها من بين النسختين وفقًا للجانب الذي يحتويه من التقسيم الثنائي. في الاتجاه الآخر، غطاء رأسي منجي◻ك2{\displaystyle G\square K_{2}}يمكن تحويلها إلى مسار عرضي دوري فردي عن طريق الاحتفاظ فقط بالرؤوس التي توجد نسختان منها في الغطاء. ويمكن تقسيم الرؤوس خارج المسار العرضي الناتج إلى قسمين وفقًا للنسخة المستخدمة من الرأس في الغطاء. [ 1 ]

الخوارزميات والتعقيد

تُعرف مسألة إيجاد أصغر تقاطع دوري فردي، أو ما يُكافئه أكبر رسم بياني فرعي ثنائي الأجزاء مُستحث، باسم تقاطع الدوري الفردي، ويُختصر إلى OCT. وهي مسألة صعبة الحل (NP-hard )، باعتبارها حالة خاصة من مسألة إيجاد أكبر رسم بياني فرعي مُستحث بخاصية وراثية (حيث أن خاصية كونه ثنائي الأجزاء وراثية). جميع هذه المسائل المتعلقة بالخصائص غير التافهة هي مسائل صعبة الحل (NP-hard). [ 2 ] [ 3 ]

تم استخدام التكافؤ بين مشكلتي اجتياز الدورة الفردية وتغطية الرؤوس لتطوير خوارزميات قابلة للمعالجة ذات معلمات ثابتة لاجتياز الدورة الفردية، مما يعني وجود خوارزمية يمكن تحديد وقت تشغيلها بدالة متعددة الحدود لحجم الرسم البياني مضروبة في دالة أكبر لـك{\displaystyle k}أدى تطوير هذه الخوارزميات إلى ظهور طريقة الضغط التكراري ، وهي أداة أكثر عمومية للعديد من الخوارزميات الأخرى ذات المعاملات. [ 1 ] تستغرق الخوارزميات ذات المعاملات المعروفة لهذه المشكلات وقتًا خطيًا تقريبًا لأي قيمة ثابتة لـك{\displaystyle k}[ 4 ] بدلاً من ذلك ، مع اعتماد متعدد الحدود على حجم الرسم البياني، فإن الاعتماد علىك{\displaystyle k}يمكن تصنيعها بأحجام صغيرة مثل2.3146ك{\displaystyle 2.3146^{k}}[ 5 ] في المقابل ، لا تسمح المشكلة المماثلة للرسوم البيانية الموجهة بخوارزمية قابلة للمعالجة ذات معلمات ثابتة في ظل افتراضات نظرية التعقيد القياسية. [ 6 ]

انظر أيضاً

  • القطع الأقصى ، وهو ما يعادل طلب الحد الأدنى من مجموعة الحواف التي يؤدي حذفها إلى رسم بياني ثنائي الأجزاء

مراجع

  1. 1 2 3 سيجان، ماريك؛ فومين، فيدور الخامس؛ كواليك، لوكاش. لوكشتانوف، دانيال؛ ماركس، دانيال؛ بيليبتشوك، مارسين؛ بيليبتشوك، ميشال؛ سوراب، ساكيت (2015)، خوارزميات ذات معلمات ، سبرينغر، الصفحات من 64 إلى 65، دوى : 10.1007 / 978-3-319-21275-3 ، ISBN  978-3-319-21274-6، MR 3380745 
  2. ↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979)، "GT21: رسم بياني فرعي مستحث ذو خاصية Π"، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ص 195 
  3. ↑ ياناكاكيس، ميهاليس (1978)، "مسائل حذف العقد والحواف من فئة NP الكاملة"، وقائع الندوة العاشرة لجمعية ACM حول نظرية الحوسبة (STOC '78) ، الصفحات 253-264 ، doi : 10.1145/800133.804355 
  4. ↑ كاواراباياشي، كين-إيتشي ؛ ريد، بروس (2010)، "خوارزمية زمنية (شبه) خطية لاجتياز الدورات الفردية"، وقائع الندوة السنوية الحادية والعشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​فيلادلفيا، بنسلفانيا: SIAM، الصفحات 365-378 ، CiteSeerX 10.1.1.215.2581 ، doi : 10.1137/1.9781611973075.31 ، ISBN   978-0-89871-701-3MR 2809682​ 
  5. ↑ لوكشتانوف، دانيال؛ ناراياناسوامي، إن إس؛ رامان، فينكاتيش؛ رامانوجان، إم إس؛ سوراب، ساكيت (2014)، "خوارزميات مُعَلمة أسرع باستخدام البرمجة الخطية"، معاملات ACM في الخوارزميات ، 11 (2): المادة 15، 31، arXiv : 1203.0833 ، doi : 10.1145/2566616 ، MR 3283570 
  6. ↑ لوكشتانوف، دانيال؛ رامانوجان، إم إس؛ سوراب، ساكيت؛ زهافي، ميراف (2017)، التعقيد البارامتري وقابلية تقريب التقاطع الدوري الفردي الموجه ، arXiv : 1704.04249 ، Bibcode : 2017arXiv170404249L