न्यूनतम बनाम मिनिमल शिखर को शामिल किया गया

Question

मैं एक परीक्षा के लिए अध्ययन कर रहा हूँ और नमूना प्रश्नों में से एक इस प्रकार है:

वर्टेक्स कवर: एक ग्राफ में एक शीर्ष कवर कोने ऐसी है कि प्रत्येक बढ़त कम से कम एक है का एक सेट है इस सेट में अपने दो अंत बिंदुओं के।

न्यूनतम वर्टेक्स कवर: ग्राफ़ में एक न्यूनतम वर्टेक्स कवर एक वर्टेक्स कवर है जिसमें सभी संभावित वर्टेक्स कवरों में सबसे छोटी संख्या में शिखर होते हैं।

मिनिमल शीर्ष कवर एक ग्राफ में कम से कम शीर्ष कवर एक शीर्ष कवर है कि एक और शिखर कवर शामिल नहीं है (सेट से किसी शीर्ष को हटाने कि एक शीर्ष कवर नहीं है कोने का एक सेट बनाना होगा)

प्रश्न है : न्यूनतम वर्टेक्स कवर हमेशा न्यूनतम वर्टेक्स कवर नहीं होता है। इसे एक साधारण उदाहरण के साथ प्रदर्शित करें।

क्या कोई इस के आसपास अपना सिर ले सकता है? मैं दोनों के बीच भेद देखने में असफल रहा हूं। सबसे महत्वपूर्ण बात यह है कि मुझे इसे देखने में कठिनाई हो रही है।

मुझे गंभीरता से उम्मीद है कि वह परीक्षा में इस तरह के अजीब प्रश्न पूछने वाला नहीं है!

Answer 1

ग्राफ

A --- B --- C 

बी न्यूनतम शीर्ष कवर है पर विचार करें।

ए, सी न्यूनतम वर्टेक्स कवर है। या तो ए या सी निकालें, आपको वर्टेक्स कवर के साथ नहीं छोड़ा गया है।

Answer 2

निम्नलिखित अनिर्दिष्ट ग्राफ पर विचार करें:

कोने का सेट {2,4,5} ग्राफ़ के न्यूनतम शीर्ष कवर है। क्यूं कर? क्योंकि यह एक कशेरुक कवर है (सभी किनारों को कवर किया गया है) और कम शिखर के साथ कोई अन्य कशेरुका कवर नहीं है।

कोने {2,3,5,6,7} के सेट एक न्यूनतम शीर्ष कवर है। क्यूं कर? क्योंकि यह एक कशेरुक कवर है और {2,3,5,6,7} का कोई गैर-तुच्छ सबसेट एक वर्टेक्स कवर नहीं है। {2,3,5,6,7} से किसी भी कशेरुक को हटाने का प्रयास करें और देखें कि आप एक अनदेखा किनारा छोड़ देते हैं। एक कशेरुक कवर न्यूनतम बनाता है जो इसे कम करने में असमर्थता है। आप सेट को पहले से छोटा नहीं बना सकते हैं और अभी भी एक कशेरुक कवर प्राप्त कर सकते हैं (इसके लिए कोष्ठक डाले बिना)।

जाहिर है, दिया गया न्यूनतम वर्टेक्स कवर न्यूनतम वर्टेक्स कवर नहीं है क्योंकि न्यूनतम वर्टेक्स कवर में तीन शिरोब होते हैं और हमारे न्यूनतम वर्टेक्स कवर में 5 शिखर होते हैं। इसलिए, प्रत्येक न्यूनतम कशेरुक कवर भी न्यूनतम वर्टेक्स कवर नहीं है।

प्रत्येक न्यूनतम वर्टेक्स कवर भी न्यूनतम वर्टेक्स कवर होता है क्योंकि न्यूनतम वर्टेक्स कवर से शिखर को हटाने से परिणामस्वरूप न्यूनतम कवर के आकार के शिखर का एक सेट होता है। इस प्रकार, न्यूनतम वर्टेक्स कवर का कोई गैर-तुच्छ सबसेट एक वर्टेक्स कवर नहीं है, और इसलिए न्यूनतम वर्टेक्स कवर भी न्यूनतम है।