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

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