غطاء الحافة

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

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

التغطية الدنيا للحواف هي تغطية للحواف ذات أصغر حجم ممكن. يُمثل عدد تغطية الحواف ρ ( G ) حجم التغطية الدنيا للحواف. يوضح الشكل التالي أمثلة على التغطية الدنيا للحواف (مرة أخرى، المجموعة C مُحددة باللون الأحمر).

لاحظ أن الشكل على اليمين ليس مجرد تغطية للحواف، بل هو أيضًا تطابق . على وجه الخصوص، هو تطابق تام : تطابق M حيث يكون كل رأس متصلًا بحافة واحدة فقط في M. التطابق التام (إن وُجد) هو دائمًا تغطية للحواف الدنيا.

يمكن إيجاد أصغر غطاء للحواف في وقت متعدد الحدود عن طريق إيجاد تطابق أقصى وتوسيعه بشكل جشع بحيث يتم تغطية جميع الرؤوس. ^{[ 1 ] [ 2 ]} في الشكل التالي، تم تمييز التطابق الأقصى باللون الأحمر؛ وتم تمييز الحواف الإضافية التي تمت إضافتها لتغطية العقد غير المتطابقة باللون الأزرق. (يُظهر الشكل على اليمين رسمًا بيانيًا يكون فيه التطابق الأقصى تطابقًا تامًا ؛ وبالتالي فهو يغطي جميع الرؤوس بالفعل ولم تكن هناك حاجة إلى حواف إضافية.)

من ناحية أخرى، فإن المشكلة ذات الصلة المتمثلة في إيجاد أصغر غطاء للرؤوس هي مشكلة صعبة من نوع NP . ^{[ 1 ]}

بمجرد النظر إلى الصورة، يتضح السبب، بالنسبة لغطاء حافة أدنى معين${\displaystyle C}$ومطابقة قصوى${\displaystyle M}$، السماح${\displaystyle c}$و${\displaystyle m}$ليكن عدد الحواف في${\displaystyle C}$و${\displaystyle M}$على التوالي، لدينا: ^{[ 3 ]}${\displaystyle |V|=c+m}$. بالفعل،${\displaystyle C}$يحتوي على تطابق أقصى، لذا فإن حواف${\displaystyle C}$يمكن تقسيمها بين${\displaystyle m}$حواف التطابق الأقصى، تغطي${\displaystyle 2m}$الرؤوس، و${\displaystyle cm}$حواف أخرى يغطي كل منها رأسًا آخر. وهكذا، كما${\displaystyle C}$يغطي كل شيء${\displaystyle |V|}$الرؤوس، لدينا${\displaystyle |V|=2m+(cm)}$تحقيق المساواة المطلوبة.

• غطاء فيرتكس
• تغطية المجموعة - مشكلة تغطية الحواف هي حالة خاصة من مشكلة تغطية المجموعة: عناصر الكون هي رؤوس، وكل مجموعة فرعية تغطي عنصرين بالضبط.

• وايسشتاين، إريك دبليو. "غطاء الحافة" . عالم الرياضيات .
• غاري، مايكل ر.؛ جونسون ، ديفيد س. (1979)، الحواسيب والاستعصاء: دليل لنظرية اكتمال NP ، دبليو إتش فريمان، ISBN 0-7167-1045-5.