غطاء الرأس (نظرية البيان)

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

 تعريف 
غطاء الرؤوس  من الرسم البياني  هو مجموعة فرعية من  حيث أن . هذه المجموعة تغطي جميع حواف . الشكل التالي يوضح أمثلة  بعض قمم الغطاء باللون الأحمر.

 ملف:Vertex-cover.svg

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

 ملف:Minimum-vertex-cover.svg

 المراجع 

 وصلات خارجية 
 معابر الأنهار (Alcuin الأرقام) - Numberphile
 الحد الأدنى من قمة غطاءالرؤوس

تصنيف:مسائل كثيرة حدود غير قطعية كاملة
تصنيف:نظرية البيان الجبري