غطاء دراجة فيرتكس

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة
غطاء دورة غير منفصل، وغطاء دورة منفصل الحواف، وغطاء دورة منفصل الرؤوس والحواف، على التوالي

في الرياضيات ، غطاء دورة الرؤوس (يسمى عادةً ببساطة غطاء الدورة ) للرسم البياني G هو مجموعة من الدورات التي هي رسوم بيانية فرعية من G وتحتوي على جميع رؤوس G.

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

إذا لم يكن لدورات الغطاء أي حواف مشتركة، فإن الغطاء يسمى غطاء دورات منفصلة الحواف أو ببساطة غطاء دورات منفصلة .

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

الخصائص والتطبيقات

دائم

يُساوي العنصر الدائم لمصفوفة (0,1) عددَ أغطية الدورات المنفصلة الرؤوس في رسم بياني موجه باستخدام مصفوفة التجاور هذه . تُستخدم هذه الحقيقة في برهان مُبسّط يُبيّن أن حساب العنصر الدائم مسألة كاملة من فئة #P . [ 5 ]

أغطية دراجات منفصلة بأقل قدر ممكن

تُعدّ مسائل إيجاد أغطية دورات منفصلة الرؤوس والحواف بأقل عدد ممكن من الدورات مسائلَ كاملةً من فئة NP . ولا تندرج هذه المسائل ضمن فئة التعقيد APX . كما أن المتغيرات الخاصة بالرسوم البيانية الموجهة لا تندرج ضمن فئة APX أيضًا. [ 6 ]

انظر أيضاً

مراجع

  1. ↑ ديفيد إبستين . "تقسيم الرسم البياني إلى دورات منفصلة العقد" .
  2. ↑ توت، دبليو تي (1954)، "برهان مختصر لنظرية العامل للرسوم البيانية المحدودة" (ملف PDF) ، المجلة الكندية للرياضيات ، 6 : 347-352 ، doi : 10.4153/CJM-1954-033-3 ، MR 0063008 ، S2CID 123221074  .
  3. ↑ https://www.cs.cmu.edu/~avrim/451f13/recitation/rec1016.txt (المسألة 1)
  4. ↑ غاري وجونسون، الحواسيب والاستعصاء ، GT13
  5. ↑ بن دور، أمير وهاليفي، شاي. (1993). " المتغير الدائم ذو الصفر والواحد كامل من النوع #P ، برهان أبسط ". وقائع الندوة الإسرائيلية الثانية حول نظرية وأنظمة الحوسبة ، 108-117.
  6. ↑ التعقيد والتقريب: مسائل التحسين التوافقي وخصائص قابليتها للتقريب (1999) ISBN 3-540-65431-3ص 378، 379 ، نقلاً عن ساهني، سرتاج ؛ غونزاليس ، تيوفيلو (1976)، “ P – مشاكل التقريب الكاملة” (PDF) ، مجلة ACM ، 23 (3): 555–565 ، دوى : 10.1145 / 321958.321975 ، السيد 0408313 ، S2CID 207548581  .