غلاف كليك

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

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

العلاقة بالتلوين

يمكن اعتبار غطاء الزمر للرسم البياني G بمثابة تلوين للرسم البياني المكمل لـ G ، وهو الرسم البياني الذي يحتوي على نفس مجموعة الرؤوس ويربط بين رؤوس G غير المتجاورة حوافًا . ومثل أغطية الزمر، فإن تلوينات الرسوم البيانية هي تقسيمات لمجموعة الرؤوس، ولكن إلى مجموعات فرعية لا توجد بينها روابط ( مجموعات مستقلة ) بدلاً من الزمر. تُعتبر مجموعة فرعية من الرؤوس زمرة في G إذا وفقط إذا كانت مجموعة مستقلة في مكمل G ، وبالتالي فإن تقسيم رؤوس G يُعد غطاء زمر لـ G إذا وفقط إذا كان تلوينًا لمكمل G.

التعقيد الحسابي

تُعرف مسألة تغطية الزمر في نظرية التعقيد الحسابي بأنها المسألة الخوارزمية لإيجاد غطاء زمر أدنى، أو (بصيغة أخرى، مسألة قرار ) إيجاد غطاء زمر يكون عدد زمره أقل من عتبة معينة. تُصنف مسألة إيجاد غطاء زمر أدنى ضمن المسائل الصعبة حسابيًا (NP-hard )، بينما تُصنف مسألة القرار الخاصة بها ضمن المسائل الكاملة حسابيًا ( NP-complete ). وكانت هذه المسألة إحدى المسائل الـ 21 الأصلية التي طرحها ريتشارد كارب، والتي أثبت أنها كاملة حسابيًا (NP-complete) في بحثه المنشور عام 1972 بعنوان "الاختزال بين المسائل التوافقية". [ 1 ]

إن التكافؤ بين تغطية الزمر وتلوينها هو اختزال يمكن استخدامه لإثبات اكتمال مسألة تغطية الزمر من نوع NP انطلاقاً من اكتمال مسألة تلوين الرسوم البيانية المعروف من نوع NP. [ 2 ]

في فئات خاصة من الرسوم البيانية

تُعرَّف الرسوم البيانية المثالية بأنها الرسوم البيانية التي يكون فيها العدد اللوني (الحد الأدنى لعدد الألوان في التلوين) مساويًا لحجم الزمرة القصوى ، وذلك لكل رسم بياني فرعي مُستحث . ووفقًا لنظرية الرسم البياني المثالي الضعيفة ، فإن مُتمِّم الرسم البياني المثالي يكون مثاليًا أيضًا. لذا، فإن الرسوم البيانية المثالية هي أيضًا الرسوم البيانية التي يكون فيها عدد تغطية الزمر مساويًا لحجم المجموعة المستقلة القصوى ، وذلك لكل رسم بياني فرعي مُستحث . ومن الممكن حساب عدد تغطية الزمر في الرسوم البيانية المثالية في وقت متعدد الحدود .

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

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

تظل مشكلة تغطية الزمر مسألة NP-كاملة على بعض الفئات الخاصة الأخرى من الرسوم البيانية، بما في ذلك الرسوم البيانية المستوية المكعبة [ 4 ] ورسوم بيانية القرص الواحد . [ 5 ]

تقريب

ينطبق نفس مستوى صعوبة نتائج التقريب المعروف في تلوين الرسوم البيانية على تغطية الزمر. لذلك، ما لم يكن P = NP ، فلا يمكن أن توجد خوارزمية تقريبية ذات زمن متعدد الحدود لأي قيمة ε > 0 تحقق، على الرسوم البيانية ذات n رأس، نسبة تقريب أفضل من n 1 − ε . [ 6 ]

في الرسوم البيانية التي لا يزيد عدد جيران كل رأس فيها عن ثلاثة ، تظل مسألة تغطية الزمر من المسائل الصعبة حسابيًا (NP-hard)، ويوجد ثابت ρ > 1 بحيث يكون من الصعب حسابيًا (NP-hard) تقريبها بنسبة تقريب ρ أو أفضل. ومع ذلك، في وقت متعدد الحدود، من الممكن إيجاد تقريب بنسبة 5/4. أي أن خوارزمية التقريب هذه تجد تغطية زمر لا يزيد عدد زمرها عن 5/4 من العدد الأمثل. [ 4 ]

يمكن استخدام تقنية بيكر لتوفير مخطط تقريبي متعدد الحدود للمسألة على الرسوم البيانية المستوية. [ 7 ]

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

مراجع

  1. ↑ كارب، ريتشارد (1972)، "قابلية الاختزال بين المسائل التوافقية" (ملف PDF) ، في ميلر، ر. إي.؛ ثاتشر، ج. و. (محرران)، وقائع ندوة حول تعقيد الحسابات الحاسوبية ، مطبعة بلينوم، الصفحات 85-103 ، مؤرشف من الأصل (ملف PDF) بتاريخ 29-06-2011 ، تم استرجاعه بتاريخ 29-08-2008 
  2. ↑ غاري، مايكل ر .؛ جونسون، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 0-7167-1045-5A1.2: GT19، صفحة 194.
  3. ↑ إسبلاج، وولفغانغ؛ غورسكي، فرانك؛ وانكي، إيغون (2001)، "كيفية حل مسائل الرسوم البيانية الصعبة من فئة NP على الرسوم البيانية ذات العرض المحدود للزمرة في وقت متعدد الحدود"، ورشة العمل الدولية حول مفاهيم نظرية الرسوم البيانية في علوم الحاسوب (WG 2001) ، سلسلة محاضرات في علوم الحاسوب، المجلد 2204، سبرينغر، الصفحات 117-128 ، doi : 10.1007/3-540-45477-2_12 ، ISBN   978-3-540-42707-0.
  4. 1 2 سيرولي، إم آر؛ فاريا، إل؛ فيريرا، تي أو؛ مارتينون، سي إيه جيه؛ بروتي، إف؛ ريد، بي (يونيو 2008)، "التقسيم إلى زمر للرسوم البيانية المكعبة: الحالة المستوية، والتعقيد، والتقريب"، الرياضيات التطبيقية المنفصلة ، ​​156 (12): 2270-2278 ، doi : 10.1016/j.dam.2007.10.015.
  5. ^ دوميتريسكو، أدريان. Pach، János (2009)، “الحد الأدنى لتقسيم الزمرة في الرسوم البيانية لقرص الوحدة”، أرخايف : 0909.1552 [ cs.CG ].
  6. ↑ زوكرمان، د. (2007)، "مستخلصات الدرجة الخطية وعدم إمكانية تقريب الزمرة القصوى والعدد اللوني" (ملف PDF) ، نظرية الحوسبة ، 3 : 103-128 ، doi : 10.4086/toc.2007.v003a006.
  7. ↑ بلانشيت، ماثيو؛ كيم، إيثان؛ فيتا، أدريان (يناير 2012)، "تغطية الزمر على الشبكات المتفرقة"، وقائع ورشة العمل الرابعة عشرة حول هندسة الخوارزميات والتجارب (ALENEX) ، جمعية الرياضيات الصناعية والتطبيقية، ص 93-102 ، doi : 10.1137/1.9781611972924.10 ، ISBN  978-1-61197-212-2
  8. ^ غاري وجونسون (1979) ، مشكلة GT59.