वर्टेक्स कवरेज समस्या

परिचय।

फिलहाल, एनपी-हार्ड समस्याओं के सटीक समाधान के लिए बहुपद-काल एल्गोरिदम ज्ञात नहीं हैं। इसके अलावा, जटिलता सिद्धांत के विशेषज्ञों का विकल्प है कि ऐसे एल्गोरिदम मौजूद नहीं हैं। हालांकि, जीवन में एनपी-हार्ड कार्य अक्सर पाए जाते हैं। व्यवहार में एनपी-कठिन समस्याओं से निपटने का एक तरीका अनुमानित एल्गोरिदम का उपयोग करना है।

शीर्ष कवरेज समस्या को हल करने के लिए सबसे अच्छा ज्ञात अनुमानित एल्गोरिथ्म पर विचार करें।

समस्या का बयान।

एक शीर्ष आवरण, ग्राफ के S शीर्षकों का एक ऐसा सेट है जिसमें ग्राफ़ के प्रत्येक किनारे के लिए कम से कम एक छोर एस में प्रवेश करता है ।

कार्य एक अप्रत्यक्ष ग्राफ़ में न्यूनतम (कोने की संख्या द्वारा) शीर्ष कवरेज का चयन करना है।

उद्देश्य।

आइए हम इस समस्या को हल करने के लिए एक सरल एल्गोरिथ्म का निर्माण करें, जिसमें दो बार से अधिक गलती न हो। इसका मतलब यह है कि यदि कोई इष्टतम समाधान है - कोने का टी, तो हमारे द्वारा प्राप्त समाधान एस असमानता को संतुष्ट करता है | एस | <= 2 | टी | ।

एक उदाहरण है।

उपरोक्त उदाहरण में, शीर्ष को कवर करना है, उदाहरण के लिए, कोने का सेट {0, 1, 2, 4} । ग्राफ के सभी छह कोने एक शीर्ष आवरण भी बनाते हैं। हालाँकि, विचाराधीन ग्राफ में न्यूनतम वर्टेक्स कवरेज एक सेट होगा जिसमें केवल दो कोने होंगे। उदाहरण के लिए, ये संख्या 1 और 3 के साथ लंबवत हो सकते हैं। वास्तव में, ग्राफ के सभी किनारों को इन दो शीर्षकों द्वारा कवर किया गया है।

एल्गोरिथ्म।

एल्गोरिथ्म के प्रत्येक चरण में, हम निम्नलिखित क्रियाएं करते हैं:

• ग्राफ e = (u, v) का एक यादृच्छिक किनारा चुनें।
• समाधान में जोड़ें S दोनों चयनित कोने u और v ।
• हम ग्राफ से सभी किनारों की घटना को यू या वी तक हटा देते हैं।

इस चरण को तब तक दोहराएं जब तक हम ग्राफ़ के सभी किनारों को हटा नहीं देते।

एल्गोरिथ्म का एक उदाहरण।

उपरोक्त उदाहरण में, न्यूनतम वर्टेक्स कवरेज में तीन कोने होते हैं। उदाहरण के लिए, ये चोटियाँ 1, 3 और 6 हो सकती हैं। उपरोक्त उदाहरण में हमारे एल्गोरिथ्म के संचालन पर विचार करें।

पहला पुनरावृत्ति:

• एक यादृच्छिक किनारा चुनें। उदाहरण के लिए, एक किनारे (1, 3) ।
• चयनित किनारे के दोनों एस के समाधान में जोड़ें: S = {1, 3} ।
• हम ग्राफ़ से सभी किनारों की घटना को 1 या 3 कोने तक हटा देते हैं।

दूसरा पुनरावृत्ति:

• एक यादृच्छिक किनारा चुनें। इसे एक किनारे होने दें (4, 6) ।
• चयनित किनारे के दोनों एस के समाधान में जोड़ें: S = {1, 3, 4, 6} ।
• हम ग्राफ़ से सभी किनारों की घटना को कोने 4 या 6 पर हटा देते हैं।

ग्राफ में कोई किनारे नहीं हैं। इसलिए, हमारे एल्गोरिथ्म के काम का परिणाम एक शीर्ष कवर S = {1, 3, 4, 6} होगा ।

सबूत।

आइए हम साबित करें कि निर्मित सेट एक शीर्ष आवरण है। वास्तव में, हर कदम पर हमने केवल पहले से ही कवर की गई पसलियों को हटा दिया। हमने इस पुनरावृत्ति को दोहराया जबकि ग्राफ में अभी भी किनारे थे। इस प्रकार, हमने ग्राफ़ के सभी किनारों को कवर किया है।

हम साबित करते हैं कि हमारा एल्गोरिथ्म 2 गुना गलत नहीं है।

एल्गोरिथ्म द्वारा विचार किए गए सभी किनारों में कोई सामान्य कोने नहीं हैं। इसलिए, इन किनारों में से प्रत्येक से, इष्टतम समाधान टी में कम से कम एक शीर्ष शामिल होना चाहिए। इसका मतलब है कि 2 | T |> = | S | ।

थोड़ा इतिहास

रिचर्ड कर्प के प्रसिद्ध काम "कॉम्बिनेटरियल समस्याओं के बीच रिड्यूसबिलिटी" को नोड कवर कहा जाता है, वर्टेक्स कवर समस्या को हल करने योग्य माना जाता है और इसकी एनपी-पूर्णता साबित होती है।
हमने जिस एल्गोरिथ्म की जांच की वह स्वतंत्र रूप से 1974 में फैनिका गैवरिल और मिहलिस यानाकिस द्वारा विकसित किया गया था।
अनुमानित वर्टेक्स कवर समस्या एल्गोरिथ्म का आज तक का सबसे प्रसिद्ध अनुमान जॉर्ज Karakostas के स्वामित्व में। वर्टिकल कवर की समस्या के लिए अनुमान एक बेहतर सन्निकटन अनुपात में सिद्ध होता है ।

निष्कर्ष।

फिलहाल, वर्टेक्स कवर के लिए कोई ज्ञात बहुपद अनुमानित एल्गोरिदम नहीं हैं जो हमारी सटीकता में काफी सुधार करते हैं। यही है, यह उस समय में एक एल्गोरिथ्म बहुपद ज्ञात नहीं है जिसे 1.999 बार से अधिक गलत नहीं किया जाएगा। इस प्रकार, हमने एनपी-हार्ड समस्या को हल करने के लिए अच्छी सटीकता के साथ एक सरल बहुपद-समय एल्गोरिथ्म प्राप्त किया।