غطاء الرؤوس (نظرية المخططات)

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

تعريف

غطاء الرؤوس $V^{'}$ من الرسم البياني $G = (V, E)$ هو مجموعة فرعية من $V$ حيث أن $u v \in E \Rightarrow u \in V^{'} \lor v \in V^{'}$ . هذه المجموعة تغطي جميع حواف $V^{'}$ . الشكل التالي يوضح أمثلة بعض قمم الغطاء باللون الأحمر.

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

المراجع

^ Mathematical foundations of computer science 2005 : 30th international symposium, MFCS 2005, Gdansk, Poland, August 29- September 2, 2005 : proceedings. Berlin: Springer. 2005. ISBN:9783540318675. OCLC:262681831. مؤرشف من الأصل في 2019-12-11.

وصلات خارجية

بوابة رياضيات

هذه بذرة مقالة عن الرياضيات او موضوع متعلق بها بحاجة للتوسيع. فضلًا شارك في تحريرها.

[1] Mathematical foundations of computer science 2005 : 30th international symposium, MFCS 2005, Gdansk, Poland, August 29- September 2, 2005 : proceedings. Berlin: Springer. 2005. ISBN:9783540318675. OCLC:262681831. مؤرشف من الأصل في 2019-12-11.

[1]