غطاء فيرتكس

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 32 صور
الموسوعة الحرة
مثال على رسم بياني يحتوي على غطاء رأسي يتألف من رأسين (أسفل)، ولكن لا يوجد أي رسم بياني يحتوي على أقل من ذلك.

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

في علوم الحاسوب ، تُعدّ مسألة إيجاد غطاء الرؤوس الأدنى مسألة تحسين كلاسيكية . وهي مسألة صعبة الحل (NP-hard) ، لذا لا يمكن حلّها بخوارزمية ذات زمن متعدد الحدود إذا كانت P ≠ NP . علاوة على ذلك، يصعب تقريبها - إذ لا يمكن تقريبها بمعامل أقل من 2 إذا كانت فرضية الألعاب الفريدة صحيحة. من ناحية أخرى، لها عدة تقريبات بسيطة بمعامل 2. وهي مثال نموذجي لمسألة تحسين صعبة الحل (NP-hard) لها خوارزمية تقريب . وكانت صيغة القرار الخاصة بها ، وهي مسألة غطاء الرؤوس ، إحدى مسائل كارب الـ 21 الكاملة (NP-complete) ، وبالتالي فهي مسألة كلاسيكية كاملة (NP-complete) في نظرية التعقيد الحسابي . إضافة إلى ذلك، فإن مسألة غطاء الرؤوس قابلة للحل بمعاملات ثابتة ، وهي مسألة مركزية في نظرية التعقيد المُعَلم .

يمكن صياغة مشكلة تغطية الرؤوس الدنيا كبرنامج خطي نصف متكامل ، وبرنامجه الخطي المزدوج هو مشكلة المطابقة القصوى .

تم تعميم مشاكل تغطية الرؤوس لتشمل الرسوم البيانية الفائقة ، انظر تغطية الرؤوس في الرسوم البيانية الفائقة .

تعريف

أمثلة على أغطية الرؤوس
أمثلة على أغطية الرؤوس الدنيا

بصورة رسمية، غطاء الرأسV′{\displaystyle V'}رسم بياني غير موجهجي=(V،هـ){\displaystyle G=(V,E)}هي مجموعة فرعية منV{\displaystyle V}بحيث(uv∈هـ)⇒(u∈V′∨v∈V′){\displaystyle (uv\in E)\Rightarrow (u\in V'\lor v\in V')}أي أنها مجموعة من الرؤوسV′{\displaystyle V'}حيث يكون لكل حافة نقطة نهاية واحدة على الأقل في غطاء الرؤوسV′{\displaystyle V'}يقال إن هذه المجموعة تغطي حوافجي{\displaystyle G}يوضح الشكل العلوي مثالين على أغطية الرؤوس، مع بعض أغطية الرؤوس.V′{\displaystyle V'}مُعلَّم باللون الأحمر.

غطاء الرؤوس الأدنى هو غطاء رؤوس بأصغر حجم ممكن. عدد غطاء الرؤوسτ{\displaystyle \tau }هو حجم غطاء الرؤوس الأدنى، أيτ=|V′|{\displaystyle \tau =|V'|}يوضح الشكل السفلي أمثلة على الحد الأدنى لتغطية الرؤوس في الرسوم البيانية السابقة.

أمثلة

  • مجموعة جميع الرؤوس هي غطاء الرؤوس.
  • تشكل نقاط نهاية أي تطابق أقصى غطاءً للرؤوس.
  • الرسم البياني الثنائي الكاملكم،ن{\displaystyle K_{m,n}}يحتوي على غطاء رأس أدنى بحجمτ(كم،ن)=مين{م،ن}{\displaystyle \tau (K_{m,n})=\min\{\,m,n\,\}}.

ملكيات

  • تُعتبر مجموعة الرؤوس غطاءً للرؤوس إذا وفقط إذا كانت مكملتها مجموعة مستقلة .
  • وبالتالي، فإن عدد رؤوس الرسم البياني يساوي الحد الأدنى لعدد رؤوسه المغطاة بالإضافة إلى حجم أكبر مجموعة مستقلة. [ 1 ]

مشكلة حسابية

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

مثال: رسم بيانيجي{\displaystyle G}
الناتج: أصغر رقمك{\displaystyle k}بحيثجي{\displaystyle G}يحتوي على غطاء رأس بحجمك{\displaystyle k}.

إذا تم صياغة المشكلة على أنها مشكلة قرار ، فإنها تسمى مشكلة تغطية الرؤوس :

مثال: رسم بيانيجي{\displaystyle G}وعدد صحيح موجبك{\displaystyle k}.
سؤال: هلجي{\displaystyle G}يجب أن يكون غطاء الرأس بحجم لا يتجاوزك{\displaystyle k}؟

هما متكافئان في ظل اختزال الوقت متعدد الحدود باستخدام البحث الثنائي . تُعدّ مسألة تغطية الرؤوس مسألةً كاملةً من فئة NP ، وكانت إحدى مسائل كارب الـ 21 الكاملة من فئة NP . وكثيراً ما تُستخدم في نظرية التعقيد الحسابي كنقطة انطلاق لإثباتات صعوبة المسائل من فئة NP .

صياغة ILP

افترض أن لكل رأس تكلفة مرتبطة به قدرهاج(v)≥0{\displaystyle c(v)\geq 0}يمكن صياغة مسألة تغطية الرؤوس الدنيا (الموزونة) على النحو التالي كبرنامج خطي صحيح (ILP). [ 2 ]

التقليل∑v∈Vج(v)xv{\displaystyle \textstyle \sum _{v\in V}c(v)x_{v}}  (تقليل التكلفة الإجمالية)
رهناً بـxu+xv≥1{\displaystyle x_{u}+x_{v}\geq 1}للجميع{u،v}∈هـ{\displaystyle \{u,v\}\in E}(تغطية كل حافة من حواف الرسم البياني)،
xv∈{0،1}{\displaystyle x_{v}\in \{0,1\}}للجميعv∈V{\displaystyle v\in V}.(كل رأس إما أن يكون ضمن غطاء الرؤوس أو لا يكون)

ينتمي هذا البرنامج الخطي الصحيح إلى فئة أعم من البرامج الخطية الصحيحة لمسائل التغطية . فجوة التكامل لهذا البرنامج الخطي الصحيح هي2{\displaystyle 2}لذا فإن تخفيفها (السماح لكل متغير بأن يكون في الفترة من 0 إلى 1، بدلاً من اشتراط أن تكون المتغيرات إما 0 أو 1 فقط) يعطي عاملاً-2{\displaystyle 2}خوارزمية تقريبية لمسألة تغطية الرؤوس الدنيا. علاوة على ذلك، فإن استرخاء البرمجة الخطية لمسألة البرمجة الخطية الصحيحة هذه هو نصف تكاملي ، أي أنه يوجد حل أمثل بحيث يكون كل مدخلxv{\displaystyle x_{v}}إما أن تكون 0 أو 1/2 أو 1. يمكن الحصول على غطاء رأس تقريبي من الدرجة 2 من هذا الحل الكسري عن طريق تحديد مجموعة فرعية من الرؤوس التي تكون متغيراتها غير صفرية.

التقييم الدقيق

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

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

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

قابلية المعالجة ذات المعلمات الثابتة

يمكن لخوارزمية البحث الشامل حل المشكلة في زمن قدره O (1) 2kn ، حيث k هو حجم غطاء الرؤوس. وبالتالي، فإن غطاء الرؤوس قابل للحل بمعامل ثابت ، وإذا كنا مهتمين فقط بقيم k الصغيرة ، فيمكننا حل المشكلة في زمن متعدد الحدود . إحدى التقنيات الخوارزمية التي تعمل هنا تُسمى خوارزمية شجرة البحث المحدودة ، وتتلخص فكرتها في اختيار رأس ما بشكل متكرر والتفرع بشكل متكرر، مع حالتين في كل خطوة: وضع إما الرأس الحالي أو جميع جيرانه في غطاء الرؤوس. تعمل خوارزمية حل غطاء الرؤوس التي تحقق أفضل اعتماد تقاربي على المعامل في زمن قدره O(1) 2kn.يا(1.2738ك+(ك⋅ن)){\displaystyle O(1.2738^{k}+(k\cdot n))}[ 5 ] تبلغ قيمة klam لهذا الحد الزمني (وهو تقدير لأكبر قيمة للمعامل يمكن حلها في وقت معقول) حوالي 190. أي أنه ما لم يتم إيجاد تحسينات خوارزمية إضافية، فإن هذه الخوارزمية مناسبة فقط للحالات التي يكون فيها عدد تغطية الرؤوس 190 أو أقل. في ظل افتراضات معقولة لنظرية التعقيد، وتحديدًا فرضية الوقت الأسي ، لا يمكن تحسين وقت التشغيل إلى 2o ( k ) ، حتى عندمان{\displaystyle n}يكونيا(ك){\displaystyle O(k)}.

مع ذلك، بالنسبة للرسوم البيانية المستوية ، وبشكل أعم، بالنسبة للرسوم البيانية التي تستبعد رسمًا بيانيًا ثابتًا كرسم بياني فرعي، يمكن إيجاد غطاء رأس بحجم k في وقت2يا(ك)نيا(1){\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}أي أن المشكلة قابلة للحل في زمن شبه أسي ذي معلمات ثابتة . [ 6 ] هذه الخوارزمية مثالية أيضًا، بمعنى أنه في ظل فرضية الزمن الأسي ، لا توجد خوارزمية قادرة على حل مشكلة تغطية الرؤوس على الرسوم البيانية المستوية في زمن2o(ك)نيا(1){\displaystyle 2^{o({\sqrt {k}})}n^{O(1)}}[ 7 ]​

التقييم التقريبي

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

تُشكل المجموعة C المُنشأة بهذه الطريقة غطاءً للرؤوس: لنفترض أن الحافة e غير مغطاة بواسطة C ؛ عندئذٍ يكون M  ∪  { e } تطابقًا، و e  ∉ M ، وهو ما يتناقض مع افتراض أن M مجموعة عظمى. علاوة على ذلك، إذا كانت e = { u , v } ∈ M ، فإن أي غطاء للرؤوس - بما في ذلك الغطاء الأمثل - يجب أن يحتوي على u أو v (أو كليهما)؛ وإلا فإن الحافة e غير مغطاة. أي أن الغطاء الأمثل يحتوي على نقطة نهاية واحدة على الأقل لكل حافة في M ؛ إجمالاً، تكون المجموعة C أكبر بمرتين على الأكثر من الغطاء الأمثل.    

تم اكتشاف هذه الخوارزمية البسيطة بشكل مستقل من قبل فانيكا جافريل وميهاليس ياناكاكيس . [ 8 ]

تُظهر تقنيات أكثر تعقيدًا وجود خوارزميات تقريبية ذات معامل تقريب أفضل قليلًا. على سبيل المثال، خوارزمية تقريبية بمعامل تقريب قدره2-Θ(1/سجل⁡|V|){\textstyle 2-\Theta \left(1/{\sqrt {\log |V|}}\right)}معروف. [ 9 ] يمكن تقريب المسألة بمعامل تقريب2/(1+دلتا){\displaystyle 2/(1+\delta )}فيدلتا{\displaystyle \delta }- الرسوم البيانية الكثيفة. [ 10 ]

عدم التقريب

لا توجد خوارزمية تقريب ذات عامل ثابت أفضل من الخوارزمية المذكورة أعلاه. تُعدّ مسألة تغطية الرؤوس الدنيا مسألة كاملة من نوع APX ، أي أنه لا يمكن تقريبها بدقة عالية إلا إذا كانت P  = NP  . باستخدام تقنيات من نظرية PCP ، أثبت دينور وسافرا في عام 2005 أنه لا يمكن تقريب تغطية الرؤوس الدنيا بعامل 1.3606 لأي درجة رأس كبيرة بما فيه الكفاية إلا إذا كانت P = NP . [ 11 ] لاحقًا، تم تحسين العامل إلى  2-ϵ{\displaystyle {\sqrt {2}}-\epsilon }لأيϵ>0{\displaystyle \epsilon >0}[ 12 ] علاوة على ذلك ، إذا كانت فرضية الألعاب الفريدة صحيحة، فلا يمكن تقريب الحد الأدنى لتغطية الرؤوس ضمن أي عامل ثابت أفضل من 2. [ 13 ]

على الرغم من أن إيجاد غطاء الرؤوس ذي الحجم الأدنى يعادل إيجاد المجموعة المستقلة ذات الحجم الأقصى، كما هو موضح أعلاه، فإن المشكلتين ليستا متكافئتين بطريقة تحافظ على التقريب: فمشكلة المجموعة المستقلة ليس لها تقريب ذو عامل ثابت إلا إذا كان P  = NP . 

الشفرة الزائفة

خوارزمية التقريب: [ 14 ] [ 15 ]

التقريب - غطاء الرأس ( G ) C = ∅ E ' = G.E​​​بينما E ' ≠ ∅ : ليكن ( u , v ) ضلعًا عشوائيًا من E ' ، C = C ∪ { u , v } ، أزل من E ' كل ضلع متصل إما بـ u أو vإرجاع C

انظر أيضاً

ملحوظات

  1. ↑ جالاي 1959 .
  2. ^ وزيراني 2003 ، ص 121 – 122 
  3. ^ جاري وجونسون وستوكمير 1974
  4. ^ غاري وجونسون 1977 ؛ غاري وجونسون 1979 ، ص 190 و 195.
  5. ^ تشن وكانج وشيا 2006
  6. ↑ ديمين وآخرون 2005
  7. ^ فلوم وغروهي (2006 ، ص. 437) 
  8. ^ باباديميتريو وستيجليتز 1998 ، ص. 432، يذكر كلا من جافريل وياناكاكيس. غاري وجونسون 1979 ، ص. 134، يستشهد جافريل.
  9. ↑ كاراكوستاس 2009
  10. ↑ كاربينسكي وزيليكوفسكي 1998
  11. ↑ دينور وسافرا 2005
  12. ↑ خوت ومنزر وصفرة 2017 ؛ دينور وآخرون. 2018 ; خوت ومنزر وصفرة 2018
  13. ↑ خوت وريجيف 2008
  14. ↑ كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2001) [1990]. "القسم 35.1: مشكلة تغطية الرؤوس". مقدمة في الخوارزميات (  الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 1024-1027 . ISBN  0-262-03293-7.
  15. ↑ تشاكرابارتي، أميت (شتاء 2005). "خوارزميات التقريب: تغطية الرؤوس" (ملف PDF) . علوم الحاسوب 105. كلية دارتموث . تاريخ الاسترجاع: 21 فبراير 2005 .

مراجع