जब तक कोई किनारा नहीं छोड़ा जाता है तब तक लंबवत निकालें
एक अप्रत्यक्ष ग्राफ़ G (V, E) को देखते हुए, निकालने के लिए न्यूनतम संख्या का पता लगाएं ताकि ग्राफ का एज सेट खाली हो जाए।
दूसरे शब्दों में: यदि हम एक शीर्ष को हटाते हैं, तो हम उस शीर्ष से जुड़े सभी किनारों के साथ उस शीर्ष को हटा देते हैं। निष्कासन की न्यूनतम संख्या ज्ञात करें ताकि उनके निकालने के बाद G में कोई किनारा न बचे।
जवाब
ऐसा लगता है जैसे आपने स्वयं उत्तर पाया, आप वर्टेक्स कवर का वर्णन कर रहे हैं , जो कई मायनों में स्वतंत्र सेट के समान है, दोनों समस्याएं एनपी-पूर्ण हैं ।
इंडिपेंडेंट सेट का रिश्ता एक ग्राफ में है $G = (V,E)$, एक सेट $S$ एक न्यूनतम शीर्ष कवर है अगर और केवल अगर $V \setminus S$ एक अधिकतम स्वतंत्र सेट है।
यदि आप जानते हैं कि इंडिपेंडेंट सेट एनपी-पूर्ण है, तो यह इस प्रकार है कि वर्टेक्स कवर एनपी-पूर्ण भी है।
दूसरे शब्दों में, आप एक अधिकतम स्वतंत्र सेट की तलाश में हैं।
वर्टेक्स कवर । एक ग्राफ दिया$G = (V,E)$ और एक पूर्णांक $k$, वहाँ एक सेट मौजूद है $S \subseteq V$ अधिकतम आकार का $k$ ऐसे कि सभी किनारों में $G$ में एक शीर्ष करने के लिए घटना कर रहे हैं $S$?
स्वतंत्र सेट । एक ग्राफ दिया$G = (V,E)$ और एक पूर्णांक $k$, वहाँ एक सेट मौजूद है $S \subseteq V$ कम से कम आकार का $k$ऐसा है कि प्रेरित ग्राफ $G[S]$ कोई किनारा नहीं है