स्वतंत्र सेट (ग्राफ सिद्धांत): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Unrelated vertices in graphs}}
{{Short description|Unrelated vertices in graphs}}


[[File:Independent set graph.svg|thumb|[[सामान्यीकृत पीटरसन ग्राफ]] GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र सेट बनाते हैं।]][[ग्राफ सिद्धांत]] में, एक स्वतंत्र सेट, स्थिर सेट, कोक्लिक या एंटीक्लिक एक [[ग्राफ (असतत गणित)]] में वर्टेक्स (ग्राफ सिद्धांत) का एक सेट है, जिनमें से कोई भी आसन्न नहीं है। यानी यह एक सेट है <math>S</math> शीर्षों का ऐसा है कि प्रत्येक दो शीर्षों के लिए <math>S</math>, दोनों को जोड़ने वाला कोई [[ किनारा (ग्राफ सिद्धांत) ]] नहीं है। समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम एक समापन बिंदु होता है <math>S</math>. एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के [[पूरक ग्राफ]] में एक [[क्लिक (ग्राफ सिद्धांत)]] है। एक स्वतंत्र सेट का आकार इसमें शामिल शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर सेट भी कहा जाता है, जिनमें से स्थिर सेट छोटा होता है।<ref>{{harvtxt|Korshunov|1974}}</ref>
[[File:Independent set graph.svg|thumb|[[सामान्यीकृत पीटरसन ग्राफ]] GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र सेट बनाते हैं।]][[ग्राफ सिद्धांत]] में, स्वतंत्र सेट, स्थिर सेट, कोक्लिक या एंटीक्लिक [[ग्राफ (असतत गणित)]] में वर्टेक्स (ग्राफ सिद्धांत) का सेट है, जिनमें से कोई भी आसन्न नहीं है। यानी यह सेट है <math>S</math> शीर्षों का ऐसा है कि प्रत्येक दो शीर्षों के लिए <math>S</math>, दोनों को जोड़ने वाला कोई [[ किनारा (ग्राफ सिद्धांत) |किनारा (ग्राफ सिद्धांत)]] नहीं है। समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम समापन बिंदु होता है <math>S</math>. सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के [[पूरक ग्राफ]] में [[क्लिक (ग्राफ सिद्धांत)]] है। स्वतंत्र सेट का आकार इसमें शामिल शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर सेट भी कहा जाता है, जिनमें से स्थिर सेट छोटा होता है।<ref>{{harvtxt|Korshunov|1974}}</ref>
एक अधिकतम स्वतंत्र समुच्चय एक स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।
एक अधिकतम स्वतंत्र समुच्चय स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।


एक [[अधिकतम स्वतंत्र सेट]] किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का एक स्वतंत्र सेट है <math>G</math>. इस आकार को '' की स्वतंत्रता संख्या कहा जाता है<math>G</math>और आमतौर पर द्वारा निरूपित किया जाता है <math>\alpha(G)</math>.<ref>{{harvtxt|Godsil|Royle|2001}}, p. 3.</ref> ऐसे समुच्चय को खोजने की [[अनुकूलन समस्या]] को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह एक [[मजबूत एनपी-पूर्णता]] है | दृढ़ता से एनपी-कठिन समस्या है।<ref>{{Cite journal|last1=Garey|first1=M. R.|last2=Johnson|first2=D. S.|date=1978-07-01|title="Strong" NP-Completeness Results: Motivation, Examples, and Implications|journal=Journal of the ACM|volume=25|issue=3|pages=499–508|doi=10.1145/322077.322090|s2cid=18371269|issn=0004-5411|doi-access=free}}</ref> इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र सेट को खोजने के लिए एक कुशल एल्गोरिथम मौजूद है।
एक [[अधिकतम स्वतंत्र सेट]] किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का स्वतंत्र सेट है <math>G</math>. इस आकार को ''की स्वतंत्रता संख्या कहा जाता है<math>G</math>और आमतौर पर द्वारा निरूपित किया जाता है <math>\alpha(G)</math>.<ref>{{harvtxt|Godsil|Royle|2001}}, p. 3.</ref> ऐसे समुच्चय को खोजने की [[अनुकूलन समस्या]] को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह [[मजबूत एनपी-पूर्णता]] है | दृढ़ता से एनपी-कठिन समस्या है।<ref>{{Cite journal|last1=Garey|first1=M. R.|last2=Johnson|first2=D. S.|date=1978-07-01|title="Strong" NP-Completeness Results: Motivation, Examples, and Implications|journal=Journal of the ACM|volume=25|issue=3|pages=499–508|doi=10.1145/322077.322090|s2cid=18371269|issn=0004-5411|doi-access=free}}</ref> इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र सेट को खोजने के लिए कुशल एल्गोरिथम मौजूद है।''


प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, लेकिन इसका विलोम निहितार्थ जरूरी नहीं है।
प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, लेकिन इसका विलोम निहितार्थ जरूरी नहीं है।
Line 14: Line 14:
===अन्य ग्राफ़ पैरामीटर्स से संबंध===
===अन्य ग्राफ़ पैरामीटर्स से संबंध===


एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में एक क्लिक (ग्राफ सिद्धांत) है, तो दो अवधारणाएं पूरक हैं। वास्तव में, बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र सेट होते हैं, एक विषय जिसे [[रैमसे सिद्धांत]] में खोजा गया है।
एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) है, तो दो अवधारणाएं पूरक हैं। वास्तव में, बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र सेट होते हैं, विषय जिसे [[रैमसे सिद्धांत]] में खोजा गया है।


एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक एक शीर्ष आवरण हो।<ref>Proof: A set V of vertices is an independent set. if and only if every edge in the graph is adjacent to at most one member of V, if and only if every edge in the graph is adjacent to at least one member not in V, if and only if the complement of V is a vertex cover.</ref> इसलिए, सबसे बड़े स्वतंत्र सेट के आकार का योग <math>\alpha(G)</math> और न्यूनतम वर्टेक्स कवर का आकार <math>\beta(G)</math> ग्राफ़ में शीर्षों की संख्या के बराबर है।
एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण हो।<ref>Proof: A set V of vertices is an independent set. if and only if every edge in the graph is adjacent to at most one member of V, if and only if every edge in the graph is adjacent to at least one member not in V, if and only if the complement of V is a vertex cover.</ref> इसलिए, सबसे बड़े स्वतंत्र सेट के आकार का योग <math>\alpha(G)</math> और न्यूनतम वर्टेक्स कवर का आकार <math>\beta(G)</math> ग्राफ़ में शीर्षों की संख्या के बराबर है।


एक ग्राफ का एक [[ग्राफ रंगना]] <math>G</math> स्वतंत्र उपसमुच्चय में इसके शीर्ष सेट के एक सेट के विभाजन के अनुरूप है। इसलिए एक शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या <math>\chi(G)</math>, कम से कम शीर्षों की संख्या का भागफल है <math>G</math> और स्वतंत्र संख्या <math>\alpha(G)</math>.
एक ग्राफ का [[ग्राफ रंगना]] <math>G</math> स्वतंत्र उपसमुच्चय में इसके शीर्ष सेट के सेट के विभाजन के अनुरूप है। इसलिए शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या <math>\chi(G)</math>, कम से कम शीर्षों की संख्या का भागफल है <math>G</math> और स्वतंत्र संख्या <math>\alpha(G)</math>.


एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र सेट में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय।
एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र सेट में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय।
Line 34: Line 34:


[[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।
[[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।
*अधिकतम स्वतंत्र सेट समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र सेट है। यदि एकाधिक अधिकतम स्वतंत्र सेट हैं, तो केवल एक आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है।
*अधिकतम स्वतंत्र सेट समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र सेट है। यदि एकाधिक अधिकतम स्वतंत्र सेट हैं, तो केवल आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है।
*अधिकतम-भार स्वतंत्र सेट समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ एक स्वतंत्र सेट है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार एक होते हैं।
*अधिकतम-भार स्वतंत्र सेट समस्या में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र सेट है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं।
* अधिकतम स्वतंत्र सेट लिस्टिंग समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की एक सूची है। अधिकतम स्वतंत्र सेट समस्या को अधिकतम स्वतंत्र सेट लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र सेट को सभी अधिकतम स्वतंत्र सेटों में शामिल किया जाना चाहिए।
* अधिकतम स्वतंत्र सेट लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र सेट समस्या को अधिकतम स्वतंत्र सेट लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र सेट को सभी अधिकतम स्वतंत्र सेटों में शामिल किया जाना चाहिए।
*स्वतंत्र सेट निर्णय समस्या में, इनपुट एक अप्रत्यक्ष ग्राफ और एक संख्या 'के'' है, और आउटपुट एक [[सत्य मूल्य]] है: सच है अगर ग्राफ में आकार 'के'' का एक स्वतंत्र सेट होता है, और गलत अन्यथा .
*स्वतंत्र सेट निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'के'' है, और आउटपुट [[सत्य मूल्य]] है: सच है अगर ग्राफ में आकार 'के'' का स्वतंत्र सेट होता है, और गलत अन्यथा .
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र सेट निर्णय समस्या नहीं है, लेकिन स्वतंत्र सेट से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र सेट निर्णय समस्या नहीं है, लेकिन स्वतंत्र सेट से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।


=== अधिकतम स्वतंत्र सेट और अधिकतम समूह ===
=== अधिकतम स्वतंत्र सेट और अधिकतम समूह ===


स्वतंत्र सेट समस्या और [[क्लिक समस्या]] पूरक हैं: जी में एक समूह जी के पूरक ग्राफ में एक स्वतंत्र सेट है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:
स्वतंत्र सेट समस्या और [[क्लिक समस्या]] पूरक हैं: जी में समूह जी के पूरक ग्राफ में स्वतंत्र सेट है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:
* स्वतंत्र सेट निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए एक कुशल एल्गोरिदम है।
* स्वतंत्र सेट निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है।
* अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन ]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।
* अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन |एनपी कठिन]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।


मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के बावजूद, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र सेट और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> हालाँकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र सेट खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के एक कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।<ref>{{harvtxt|Berman|Fujito|1995}}.</ref>
मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के बावजूद, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र सेट और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> हालाँकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र सेट खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।<ref>{{harvtxt|Berman|Fujito|1995}}.</ref>


{{See|Clique problem#Finding maximum cliques in arbitrary graphs}}
{{See|Clique problem#Finding maximum cliques in arbitrary graphs}}


=== सटीक एल्गोरिदम ===
=== सटीक एल्गोरिदम ===
अधिकतम स्वतंत्र सेट समस्या एनपी-हार्ड है। हालाँकि, इसे O(n) की तुलना में अधिक कुशलता से हल किया जा सकता है<sup>2</sup> 2<sup>n</sup>) समय जो एक भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह एक स्वतंत्र सेट है।
अधिकतम स्वतंत्र सेट समस्या एनपी-हार्ड है। हालाँकि, इसे O(n) की तुलना में अधिक कुशलता से हल किया जा सकता है<sup>2</sup> 2<sup>n</sup>) समय जो भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह स्वतंत्र सेट है।


2017 तक इसे O (1.1996.1) समय में हल किया जा सकता है<sup>n</sup>) बहुपद स्थान का उपयोग करके।<ref>{{harvtxt|Xiao|Nagamochi|2017}}</ref> अधिकतम डिग्री 3 वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता है<sup>एन</sup>).<ref>{{harvtxt|Xiao|Nagamochi|2013}}</ref>
2017 तक इसे O (1.1996.1) समय में हल किया जा सकता है<sup>n</sup>) बहुपद स्थान का उपयोग करके।<ref>{{harvtxt|Xiao|Nagamochi|2017}}</ref> अधिकतम डिग्री 3 वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता है<sup>एन</sup>).<ref>{{harvtxt|Xiao|Nagamochi|2013}}</ref>
ग्राफ़ के कई वर्गों के लिए, बहुपद समय में एक अधिकतम भार स्वतंत्र सेट पाया जा सकता है। प्रसिद्ध उदाहरण पंजा-मुक्त रेखांकन हैं,<ref>{{harvtxt|Minty|1980}},{{harvtxt|Sbihi|1980}},{{harvtxt|Nakamura|Tamura|2001}},{{harvtxt|Faenza|Oriolo|Stauffer|2014}},{{harvtxt|Nobili|Sassano|2015}}</ref> P<sub>5</sub>- मुक्त रेखांकन<ref>{{harvtxt|Lokshtanov|Vatshelle|Villanger|2014}}</ref> और सही रेखांकन।<ref>{{harvtxt|Grötschel|Lovász|Schrijver|1988}}</ref> [[कॉर्डल ग्राफ]]़ के लिए, रैखिक समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है।<ref>{{harvtxt|Frank|1976}}</ref>
ग्राफ़ के कई वर्गों के लिए, बहुपद समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है। प्रसिद्ध उदाहरण पंजा-मुक्त रेखांकन हैं,<ref>{{harvtxt|Minty|1980}},{{harvtxt|Sbihi|1980}},{{harvtxt|Nakamura|Tamura|2001}},{{harvtxt|Faenza|Oriolo|Stauffer|2014}},{{harvtxt|Nobili|Sassano|2015}}</ref> P<sub>5</sub>- मुक्त रेखांकन<ref>{{harvtxt|Lokshtanov|Vatshelle|Villanger|2014}}</ref> और सही रेखांकन।<ref>{{harvtxt|Grötschel|Lovász|Schrijver|1988}}</ref> [[कॉर्डल ग्राफ]]़ के लिए, रैखिक समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है।<ref>{{harvtxt|Frank|1976}}</ref>


अधिकतम वजन स्वतंत्र सेट समस्या को हल करने के लिए [[मॉड्यूलर अपघटन]] एक अच्छा उपकरण है; [[कोग्राफ]] पर लीनियर टाइम एल्गोरिद्म इसका मूल उदाहरण है। एक अन्य महत्वपूर्ण उपकरण क्लिक विभाजक हैं जैसा कि टारजन द्वारा वर्णित है।<ref>{{harvtxt|Tarjan|1985}}</ref>
अधिकतम वजन स्वतंत्र सेट समस्या को हल करने के लिए [[मॉड्यूलर अपघटन]] अच्छा उपकरण है; [[कोग्राफ]] पर लीनियर टाइम एल्गोरिद्म इसका मूल उदाहरण है। अन्य महत्वपूर्ण उपकरण क्लिक विभाजक हैं जैसा कि टारजन द्वारा वर्णित है।<ref>{{harvtxt|Tarjan|1985}}</ref>


कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र सेट पाया जा सकता है।
कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र सेट पाया जा सकता है।


=== सन्निकटन एल्गोरिदम ===
=== सन्निकटन एल्गोरिदम ===
सामान्य तौर पर, अधिकतम स्वतंत्र सेट समस्या को बहुपद समय में एक स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि पी = एनपी)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र सेट एपीएक्स # संबंधित जटिलता वर्ग है | पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है।<ref>{{cite journal|last1=Bazgan|first1=Cristina|author1-link=Cristina Bazgan|last2=Escoffier|first2=Bruno|last3=Paschos|first3=Vangelis Th.|title=Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness|journal=Theoretical Computer Science|date=2005|volume=339|issue=2–3|pages=272–292|doi=10.1016/j.tcs.2005.03.007|s2cid=1418848 |url=https://basepub.dauphine.fr/handle/123456789/3724|doi-access=free}}</ref> हालांकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं।
सामान्य तौर पर, अधिकतम स्वतंत्र सेट समस्या को बहुपद समय में स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि पी = एनपी)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र सेट एपीएक्स # संबंधित जटिलता वर्ग है | पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है।<ref>{{cite journal|last1=Bazgan|first1=Cristina|author1-link=Cristina Bazgan|last2=Escoffier|first2=Bruno|last3=Paschos|first3=Vangelis Th.|title=Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness|journal=Theoretical Computer Science|date=2005|volume=339|issue=2–3|pages=272–292|doi=10.1016/j.tcs.2005.03.007|s2cid=1418848 |url=https://basepub.dauphine.fr/handle/123456789/3724|doi-access=free}}</ref> हालांकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं।


=== [[ प्लेनर ग्राफ ]] में ===
=== [[ प्लेनर ग्राफ | प्लेनर ग्राफ]] में ===
प्लानर ग्राफ़ में, अधिकतम स्वतंत्र सेट को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है; [[माइनर (ग्राफ सिद्धांत)]] लेने के तहत बंद किए गए ग्राफ़ के किसी भी परिवार में समान [[बहुपद-समय सन्निकटन योजना]]एं मौजूद हैं।<ref>{{harvtxt|Baker|1994}}; {{harvtxt|Grohe|2003}}.</ref>
प्लानर ग्राफ़ में, अधिकतम स्वतंत्र सेट को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है; [[माइनर (ग्राफ सिद्धांत)]] लेने के तहत बंद किए गए ग्राफ़ के किसी भी परिवार में समान [[बहुपद-समय सन्निकटन योजना]]एं मौजूद हैं।<ref>{{harvtxt|Baker|1994}}; {{harvtxt|Grohe|2003}}.</ref>
=== बाउंडेड डिग्री ग्राफ़ में ===
=== बाउंडेड डिग्री ग्राफ़ में ===
बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को [[सन्निकटन अनुपात]] के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, एक लालची एल्गोरिद्म जो अधिकतम स्वतंत्र सेट बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके पड़ोसियों को हटाकर, अधिकतम डिग्री Δ वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है।<ref>{{harvtxt|Halldórsson|Radhakrishnan|1997}}.</ref> ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी {{harvtxt|Berman|Karpinski|1999}}. वास्तव में, 3-रेगुलर 3-एज-कलरेबल ग्राफ़ पर भी मैक्स इंडिपेंडेंट सेट [[APX]]|APX-पूर्ण है।<ref name=chlebik>{{cite journal|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka|author2-link=Janka Chlebíková|title=एनपी-हार्ड समस्याओं की छोटी घटना के उदाहरणों के लिए सन्निकटन कठोरता|journal=Proceedings of the 5th International Conference on Algorithms and Complexity|series=Lecture Notes in Computer Science|date=2003|volume=2653|pages=152–164|doi=10.1007/3-540-44849-7_21|isbn=978-3-540-40176-6|url=https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-for-small-occurrence-instances-of-nphard-problems(fe0d8e3c-740b-4b84-9962-4a0b05cc6f6b).html}}</ref>
बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को [[सन्निकटन अनुपात]] के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, लालची एल्गोरिद्म जो अधिकतम स्वतंत्र सेट बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके पड़ोसियों को हटाकर, अधिकतम डिग्री Δ वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है।<ref>{{harvtxt|Halldórsson|Radhakrishnan|1997}}.</ref> ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी {{harvtxt|Berman|Karpinski|1999}}. वास्तव में, 3-रेगुलर 3-एज-कलरेबल ग्राफ़ पर भी मैक्स इंडिपेंडेंट सेट [[APX]]|APX-पूर्ण है।<ref name=chlebik>{{cite journal|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka|author2-link=Janka Chlebíková|title=एनपी-हार्ड समस्याओं की छोटी घटना के उदाहरणों के लिए सन्निकटन कठोरता|journal=Proceedings of the 5th International Conference on Algorithms and Complexity|series=Lecture Notes in Computer Science|date=2003|volume=2653|pages=152–164|doi=10.1007/3-540-44849-7_21|isbn=978-3-540-40176-6|url=https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-for-small-occurrence-instances-of-nphard-problems(fe0d8e3c-740b-4b84-9962-4a0b05cc6f6b).html}}</ref>
=== इंटरसेक्शन ग्राफ में ===
=== इंटरसेक्शन ग्राफ में ===
{{Main|Interval scheduling}}
{{Main|Interval scheduling}}
एक [[अंतराल ग्राफ]] एक ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच एक किनारा होता है अगर और केवल अगर वे एक दूसरे को काटते हैं। एक अंतराल ग्राफ में एक स्वतंत्र सेट गैर-अतिव्यापी अंतराल का एक सेट है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[ कार्य निर्धारण ]] के संदर्भ में: जॉब का एक सेट दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम सेट खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है एक दूसरे के साथ। इस समस्या को [[जल्द से जल्द समय सीमा पहले शेड्यूलिंग]] का उपयोग करके बहुपद समय में हल किया जा सकता है।
एक [[अंतराल ग्राफ]] ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है अगर और केवल अगर वे दूसरे को काटते हैं। अंतराल ग्राफ में स्वतंत्र सेट गैर-अतिव्यापी अंतराल का सेट है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[ कार्य निर्धारण |कार्य निर्धारण]] के संदर्भ में: जॉब का सेट दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम सेट खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है दूसरे के साथ। इस समस्या को [[जल्द से जल्द समय सीमा पहले शेड्यूलिंग]] का उपयोग करके बहुपद समय में हल किया जा सकता है।


=== ज्यामितीय चौराहों के रेखांकन में ===
=== ज्यामितीय चौराहों के रेखांकन में ===
{{Main|Maximum disjoint set}}
{{Main|Maximum disjoint set}}
एक ज्यामितीय प्रतिच्छेदन ग्राफ एक ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच एक किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। एक ज्यामितीय चौराहे के ग्राफ में एक स्वतंत्र सेट केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का एक सेट है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[स्वचालित लेबल प्लेसमेंट]] के संदर्भ में: मानचित्र में स्थानों का एक सेट दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम सेट खोजें।
एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र सेट केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का सेट है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[स्वचालित लेबल प्लेसमेंट]] के संदर्भ में: मानचित्र में स्थानों का सेट दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम सेट खोजें।


[[ चौराहा ग्राफ ]] में अधिकतम स्वतंत्र सेट ढूँढना अभी भी एनपी-पूर्ण है, लेकिन सामान्य अधिकतम स्वतंत्र सेट समस्या की तुलना में अनुमानित करना आसान है। एक हालिया सर्वेक्षण के परिचय में पाया जा सकता है {{harvtxt|Chan|Har-Peled|2012}}.
[[ चौराहा ग्राफ | चौराहा ग्राफ]] में अधिकतम स्वतंत्र सेट ढूँढना अभी भी एनपी-पूर्ण है, लेकिन सामान्य अधिकतम स्वतंत्र सेट समस्या की तुलना में अनुमानित करना आसान है। हालिया सर्वेक्षण के परिचय में पाया जा सकता है {{harvtxt|Chan|Har-Peled|2012}}.


=== डी-पंजे से मुक्त ग्राफ में ===
=== डी-पंजे से मुक्त ग्राफ में ===
एक ग्राफ़ में एक डी-पंजे डी + 1 कोने का एक सेट है, जिनमें से एक (केंद्र) अन्य डी कोने से जुड़ा हुआ है, लेकिन अन्य डी कोने एक दूसरे से जुड़े नहीं हैं। एक डी-क्लॉ-फ्री ग्राफ एक ऐसा ग्राफ है जिसमें डी-क्लॉ सबग्राफ नहीं होता है। एल्गोरिदम पर विचार करें जो एक खाली सेट के साथ शुरू होता है, और जब तक यह किसी मौजूदा शीर्ष के निकट नहीं होता है, तब तक इसमें एक मनमाना वर्टेक्स जोड़ता है। डी-क्लॉ-फ्री ग्राफ़ में, प्रत्येक जोड़ा शीर्ष अधिकतम स्वतंत्र सेट से अधिकांश d-1 शीर्षों पर अमान्य हो जाता है; इसलिए, यह तुच्छ एल्गोरिथम अधिकतम स्वतंत्र सेट के लिए (d-1)-समीक्षा एल्गोरिथम प्राप्त करता है। वास्तव में, बहुत बेहतर सन्निकटन अनुपात प्राप्त करना संभव है:
एक ग्राफ़ में डी-पंजे डी + 1 कोने का सेट है, जिनमें से (केंद्र) अन्य डी कोने से जुड़ा हुआ है, लेकिन अन्य डी कोने दूसरे से जुड़े नहीं हैं। डी-क्लॉ-फ्री ग्राफ ऐसा ग्राफ है जिसमें डी-क्लॉ सबग्राफ नहीं होता है। एल्गोरिदम पर विचार करें जो खाली सेट के साथ शुरू होता है, और जब तक यह किसी मौजूदा शीर्ष के निकट नहीं होता है, तब तक इसमें मनमाना वर्टेक्स जोड़ता है। डी-क्लॉ-फ्री ग्राफ़ में, प्रत्येक जोड़ा शीर्ष अधिकतम स्वतंत्र सेट से अधिकांश d-1 शीर्षों पर अमान्य हो जाता है; इसलिए, यह तुच्छ एल्गोरिथम अधिकतम स्वतंत्र सेट के लिए (d-1)-समीक्षा एल्गोरिथम प्राप्त करता है। वास्तव में, बहुत बेहतर सन्निकटन अनुपात प्राप्त करना संभव है:


* न्यूवॉनर<ref>{{Cite journal |last=Neuwohner |first=Meike |date=2021-06-07 |title=डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम|arxiv=2106.03545 }}</ref> एक बहुपद समय एल्गोरिदम प्रस्तुत किया गया है, जो किसी भी निरंतर ε> 0 के लिए, एक (डी/2-1/63,700,992+ε) पाता है - डी-क्लॉ फ्री ग्राफ में अधिकतम वजन स्वतंत्र सेट के लिए सन्निकटन।
* न्यूवॉनर<ref>{{Cite journal |last=Neuwohner |first=Meike |date=2021-06-07 |title=डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम|arxiv=2106.03545 }}</ref> बहुपद समय एल्गोरिदम प्रस्तुत किया गया है, जो किसी भी निरंतर ε> 0 के लिए, (डी/2-1/63,700,992+ε) पाता है - डी-क्लॉ फ्री ग्राफ में अधिकतम वजन स्वतंत्र सेट के लिए सन्निकटन।
* साइगन<ref>{{Cite journal |last=Cygan |first=Marek |date=October 2013 |title=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |url=https://ieeexplore.ieee.org/document/6686187 |journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> एक [[अर्ध-बहुपद समय]] एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, (d+ε)/3 सन्निकटन प्राप्त करता है।
* साइगन<ref>{{Cite journal |last=Cygan |first=Marek |date=October 2013 |title=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |url=https://ieeexplore.ieee.org/document/6686187 |journal=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> [[अर्ध-बहुपद समय]] एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, (d+ε)/3 सन्निकटन प्राप्त करता है।


=== अधिकतम स्वतंत्र सेट ढूँढना ===
=== अधिकतम स्वतंत्र सेट ढूँढना ===
Line 87: Line 87:
{{Main|Maximal independent set}}
{{Main|Maximal independent set}}


एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में एक अधिकतम स्वतंत्र सेट खोजने की समस्या को हल किया जा सकता है।<ref>{{harvtxt|Luby|1986}}.</ref> सभी अधिकतम स्वतंत्र सेट समय ओ (3) में पाए जा सकते हैं<sup>n/3</sup>) = ओ (1.4423<sup>एन</sup>).
एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र सेट खोजने की समस्या को हल किया जा सकता है।<ref>{{harvtxt|Luby|1986}}.</ref> सभी अधिकतम स्वतंत्र सेट समय ओ (3) में पाए जा सकते हैं<sup>n/3</sup>) = ओ (1.4423<sup>एन</sup>).


== अनुप्रयोग ==
== अनुप्रयोग ==
अधिकतम स्वतंत्र सेट और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के [[कम्प्यूटेशनल जटिलता सिद्धांत]] को साबित करने में शामिल है।<ref>{{Cite book|last=Skiena, Steven S.|title=एल्गोरिथ्म डिजाइन मैनुअल|date=2012|publisher=Springer|isbn=978-1-84800-069-8|oclc=820425142}}</ref> वे वास्तविक विश्व अनुकूलन समस्याओं के लिए उपयोगी मॉडल के रूप में भी काम करते हैं, उदाहरण के लिए [[संश्लेषित जीव विज्ञान]] विज्ञान को डिजाइन करने के लिए स्थिर [[जीन नियामक नेटवर्क]] की खोज के लिए अधिकतम स्वतंत्र सेट एक उपयोगी मॉडल है।<ref>{{Cite journal|last1=Hossain|first1=Ayaan|last2=Lopez|first2=Eriberto|last3=Halper|first3=Sean M.|last4=Cetnar|first4=Daniel P.|last5=Reis|first5=Alexander C.|last6=Strickland|first6=Devin|last7=Klavins|first7=Eric|last8=Salis|first8=Howard M.|date=2020-07-13|title=इंजीनियरिंग स्थिर आनुवंशिक प्रणालियों के लिए हजारों गैर-दोहराव वाले भागों का स्वचालित डिजाइन|url=https://www.nature.com/articles/s41587-020-0584-2|journal=Nature Biotechnology|volume=38|issue=12|language=en|pages=1466–1475|doi=10.1038/s41587-020-0584-2|pmid=32661437|s2cid=220506228|issn=1546-1696}}</ref>
अधिकतम स्वतंत्र सेट और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के [[कम्प्यूटेशनल जटिलता सिद्धांत]] को साबित करने में शामिल है।<ref>{{Cite book|last=Skiena, Steven S.|title=एल्गोरिथ्म डिजाइन मैनुअल|date=2012|publisher=Springer|isbn=978-1-84800-069-8|oclc=820425142}}</ref> वे वास्तविक विश्व अनुकूलन समस्याओं के लिए उपयोगी मॉडल के रूप में भी काम करते हैं, उदाहरण के लिए [[संश्लेषित जीव विज्ञान]] विज्ञान को डिजाइन करने के लिए स्थिर [[जीन नियामक नेटवर्क]] की खोज के लिए अधिकतम स्वतंत्र सेट उपयोगी मॉडल है।<ref>{{Cite journal|last1=Hossain|first1=Ayaan|last2=Lopez|first2=Eriberto|last3=Halper|first3=Sean M.|last4=Cetnar|first4=Daniel P.|last5=Reis|first5=Alexander C.|last6=Strickland|first6=Devin|last7=Klavins|first7=Eric|last8=Salis|first8=Howard M.|date=2020-07-13|title=इंजीनियरिंग स्थिर आनुवंशिक प्रणालियों के लिए हजारों गैर-दोहराव वाले भागों का स्वचालित डिजाइन|url=https://www.nature.com/articles/s41587-020-0584-2|journal=Nature Biotechnology|volume=38|issue=12|language=en|pages=1466–1475|doi=10.1038/s41587-020-0584-2|pmid=32661437|s2cid=220506228|issn=1546-1696}}</ref>
== यह भी देखें ==
== यह भी देखें ==


* किनारों का एक स्वतंत्र सेट किनारों का एक सेट होता है, जिसमें किन्हीं भी दो में एक शीर्ष उभयनिष्ठ नहीं होता है। इसे आमतौर पर [[मिलान (ग्राफ सिद्धांत)]] कहा जाता है।
* किनारों का स्वतंत्र सेट किनारों का सेट होता है, जिसमें किन्हीं भी दो में शीर्ष उभयनिष्ठ नहीं होता है। इसे आमतौर पर [[मिलान (ग्राफ सिद्धांत)]] कहा जाता है।
* एक [[शीर्ष रंग]] स्वतंत्र सेट में शीर्ष सेट का विभाजन है।
* एक [[शीर्ष रंग]] स्वतंत्र सेट में शीर्ष सेट का विभाजन है।


Revision as of 18:23, 13 March 2023

सामान्यीकृत पीटरसन ग्राफ GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र सेट बनाते हैं।

ग्राफ सिद्धांत में, स्वतंत्र सेट, स्थिर सेट, कोक्लिक या एंटीक्लिक ग्राफ (असतत गणित) में वर्टेक्स (ग्राफ सिद्धांत) का सेट है, जिनमें से कोई भी आसन्न नहीं है। यानी यह सेट है शीर्षों का ऐसा है कि प्रत्येक दो शीर्षों के लिए , दोनों को जोड़ने वाला कोई किनारा (ग्राफ सिद्धांत) नहीं है। समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम समापन बिंदु होता है . सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) है। स्वतंत्र सेट का आकार इसमें शामिल शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर सेट भी कहा जाता है, जिनमें से स्थिर सेट छोटा होता है।[1]

एक अधिकतम स्वतंत्र समुच्चय स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।

एक अधिकतम स्वतंत्र सेट किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का स्वतंत्र सेट है . इस आकार को की स्वतंत्रता संख्या कहा जाता हैऔर आमतौर पर द्वारा निरूपित किया जाता है .[2] ऐसे समुच्चय को खोजने की अनुकूलन समस्या को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह मजबूत एनपी-पूर्णता है | दृढ़ता से एनपी-कठिन समस्या है।[3] इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र सेट को खोजने के लिए कुशल एल्गोरिथम मौजूद है।

प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, लेकिन इसका विलोम निहितार्थ जरूरी नहीं है।

गुण

Covering/packing-problem pairs
Covering problems Packing problems
Minimum set cover Maximum set packing
Minimum edge cover Maximum matching
Minimum vertex cover Maximum independent set
Bin covering Bin packing
Polygon covering Rectangle packing

अन्य ग्राफ़ पैरामीटर्स से संबंध

एक सेट स्वतंत्र है अगर और केवल अगर यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) है, तो दो अवधारणाएं पूरक हैं। वास्तव में, बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र सेट होते हैं, विषय जिसे रैमसे सिद्धांत में खोजा गया है।

एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण हो।[4] इसलिए, सबसे बड़े स्वतंत्र सेट के आकार का योग और न्यूनतम वर्टेक्स कवर का आकार ग्राफ़ में शीर्षों की संख्या के बराबर है।

एक ग्राफ का ग्राफ रंगना स्वतंत्र उपसमुच्चय में इसके शीर्ष सेट के सेट के विभाजन के अनुरूप है। इसलिए शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या , कम से कम शीर्षों की संख्या का भागफल है और स्वतंत्र संख्या .

एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र सेट में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय।

अधिकतम स्वतंत्र सेट

Main article: Maximal independent set

एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है, उच्चिष्ठ कहलाता है। इस तरह के सेट हावी सेट होते हैं। प्रत्येक ग्राफ में अधिकतम 3 होते हैंn/3 अधिकतम स्वतंत्र सेट,[5] लेकिन कई रेखांकन बहुत कम हैं। एन-वर्टेक्स चक्र ग्राफ में अधिकतम स्वतंत्र सेट की संख्या पेरिन संख्या द्वारा दी गई है, और एन-वर्टेक्स पथ ग्राफ में अधिकतम स्वतंत्र सेट की संख्या पडोवन अनुक्रम द्वारा दी गई है।[6] इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं।

स्वतंत्र सेट ढूँढना

Further information: Clique problem

कंप्यूटर विज्ञान में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।

  • अधिकतम स्वतंत्र सेट समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र सेट है। यदि एकाधिक अधिकतम स्वतंत्र सेट हैं, तो केवल आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है।
  • अधिकतम-भार स्वतंत्र सेट समस्या में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र सेट है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं।
  • अधिकतम स्वतंत्र सेट लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र सेट समस्या को अधिकतम स्वतंत्र सेट लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र सेट को सभी अधिकतम स्वतंत्र सेटों में शामिल किया जाना चाहिए।
  • स्वतंत्र सेट निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'के है, और आउटपुट सत्य मूल्य है: सच है अगर ग्राफ में आकार 'के का स्वतंत्र सेट होता है, और गलत अन्यथा .

इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र सेट निर्णय समस्या नहीं है, लेकिन स्वतंत्र सेट से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।

अधिकतम स्वतंत्र सेट और अधिकतम समूह

स्वतंत्र सेट समस्या और क्लिक समस्या पूरक हैं: जी में समूह जी के पूरक ग्राफ में स्वतंत्र सेट है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:

  • स्वतंत्र सेट निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है।
  • अधिकतम स्वतंत्र समुच्चय समस्या एनपी कठिन है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।

मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के बावजूद, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र सेट और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है;[7] हालाँकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र सेट खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।[8]

Further information: Clique problem § Finding maximum cliques in arbitrary graphs

सटीक एल्गोरिदम

अधिकतम स्वतंत्र सेट समस्या एनपी-हार्ड है। हालाँकि, इसे O(n) की तुलना में अधिक कुशलता से हल किया जा सकता है2 2n) समय जो भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह स्वतंत्र सेट है।

2017 तक इसे O (1.1996.1) समय में हल किया जा सकता हैn) बहुपद स्थान का उपयोग करके।[9] अधिकतम डिग्री 3 वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता हैएन).[10] ग्राफ़ के कई वर्गों के लिए, बहुपद समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है। प्रसिद्ध उदाहरण पंजा-मुक्त रेखांकन हैं,[11] P5- मुक्त रेखांकन[12] और सही रेखांकन।[13] कॉर्डल ग्राफ़ के लिए, रैखिक समय में अधिकतम भार स्वतंत्र सेट पाया जा सकता है।[14]

अधिकतम वजन स्वतंत्र सेट समस्या को हल करने के लिए मॉड्यूलर अपघटन अच्छा उपकरण है; कोग्राफ पर लीनियर टाइम एल्गोरिद्म इसका मूल उदाहरण है। अन्य महत्वपूर्ण उपकरण क्लिक विभाजक हैं जैसा कि टारजन द्वारा वर्णित है।[15]

कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र सेट पाया जा सकता है।

सन्निकटन एल्गोरिदम

सामान्य तौर पर, अधिकतम स्वतंत्र सेट समस्या को बहुपद समय में स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि पी = एनपी)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र सेट एपीएक्स # संबंधित जटिलता वर्ग है | पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है।[16] हालांकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं।

प्लेनर ग्राफ में

प्लानर ग्राफ़ में, अधिकतम स्वतंत्र सेट को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है; माइनर (ग्राफ सिद्धांत) लेने के तहत बंद किए गए ग्राफ़ के किसी भी परिवार में समान बहुपद-समय सन्निकटन योजनाएं मौजूद हैं।[17]

बाउंडेड डिग्री ग्राफ़ में

बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को सन्निकटन अनुपात के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, लालची एल्गोरिद्म जो अधिकतम स्वतंत्र सेट बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके पड़ोसियों को हटाकर, अधिकतम डिग्री Δ वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है।[18] ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी Berman & Karpinski (1999). वास्तव में, 3-रेगुलर 3-एज-कलरेबल ग्राफ़ पर भी मैक्स इंडिपेंडेंट सेट APX|APX-पूर्ण है।[19]

इंटरसेक्शन ग्राफ में

Main article: Interval scheduling

एक अंतराल ग्राफ ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है अगर और केवल अगर वे दूसरे को काटते हैं। अंतराल ग्राफ में स्वतंत्र सेट गैर-अतिव्यापी अंतराल का सेट है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, कार्य निर्धारण के संदर्भ में: जॉब का सेट दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम सेट खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है दूसरे के साथ। इस समस्या को जल्द से जल्द समय सीमा पहले शेड्यूलिंग का उपयोग करके बहुपद समय में हल किया जा सकता है।

ज्यामितीय चौराहों के रेखांकन में

Main article: Maximum disjoint set

एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र सेट केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का सेट है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र सेट खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, स्वचालित लेबल प्लेसमेंट के संदर्भ में: मानचित्र में स्थानों का सेट दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम सेट खोजें।

चौराहा ग्राफ में अधिकतम स्वतंत्र सेट ढूँढना अभी भी एनपी-पूर्ण है, लेकिन सामान्य अधिकतम स्वतंत्र सेट समस्या की तुलना में अनुमानित करना आसान है। हालिया सर्वेक्षण के परिचय में पाया जा सकता है Chan & Har-Peled (2012).

डी-पंजे से मुक्त ग्राफ में

एक ग्राफ़ में डी-पंजे डी + 1 कोने का सेट है, जिनमें से (केंद्र) अन्य डी कोने से जुड़ा हुआ है, लेकिन अन्य डी कोने दूसरे से जुड़े नहीं हैं। डी-क्लॉ-फ्री ग्राफ ऐसा ग्राफ है जिसमें डी-क्लॉ सबग्राफ नहीं होता है। एल्गोरिदम पर विचार करें जो खाली सेट के साथ शुरू होता है, और जब तक यह किसी मौजूदा शीर्ष के निकट नहीं होता है, तब तक इसमें मनमाना वर्टेक्स जोड़ता है। डी-क्लॉ-फ्री ग्राफ़ में, प्रत्येक जोड़ा शीर्ष अधिकतम स्वतंत्र सेट से अधिकांश d-1 शीर्षों पर अमान्य हो जाता है; इसलिए, यह तुच्छ एल्गोरिथम अधिकतम स्वतंत्र सेट के लिए (d-1)-समीक्षा एल्गोरिथम प्राप्त करता है। वास्तव में, बहुत बेहतर सन्निकटन अनुपात प्राप्त करना संभव है:

  • न्यूवॉनर[20] बहुपद समय एल्गोरिदम प्रस्तुत किया गया है, जो किसी भी निरंतर ε> 0 के लिए, (डी/2-1/63,700,992+ε) पाता है - डी-क्लॉ फ्री ग्राफ में अधिकतम वजन स्वतंत्र सेट के लिए सन्निकटन।
  • साइगन[21] अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, (d+ε)/3 सन्निकटन प्राप्त करता है।

अधिकतम स्वतंत्र सेट ढूँढना

Main article: Maximal independent set

एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र सेट खोजने की समस्या को हल किया जा सकता है।[22] सभी अधिकतम स्वतंत्र सेट समय ओ (3) में पाए जा सकते हैंn/3) = ओ (1.4423एन).

अनुप्रयोग

अधिकतम स्वतंत्र सेट और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के कम्प्यूटेशनल जटिलता सिद्धांत को साबित करने में शामिल है।[23] वे वास्तविक विश्व अनुकूलन समस्याओं के लिए उपयोगी मॉडल के रूप में भी काम करते हैं, उदाहरण के लिए संश्लेषित जीव विज्ञान विज्ञान को डिजाइन करने के लिए स्थिर जीन नियामक नेटवर्क की खोज के लिए अधिकतम स्वतंत्र सेट उपयोगी मॉडल है।[24]

यह भी देखें

  • किनारों का स्वतंत्र सेट किनारों का सेट होता है, जिसमें किन्हीं भी दो में शीर्ष उभयनिष्ठ नहीं होता है। इसे आमतौर पर मिलान (ग्राफ सिद्धांत) कहा जाता है।
  • एक शीर्ष रंग स्वतंत्र सेट में शीर्ष सेट का विभाजन है।

टिप्पणियाँ

  1. ↑ Korshunov (1974)
  2. ↑ Godsil & Royle (2001), p. 3.
  3. ↑ Garey, M. R.; Johnson, D. S. (1978-07-01). ""Strong" NP-Completeness Results: Motivation, Examples, and Implications". Journal of the ACM. 25 (3): 499–508. doi:10.1145/322077.322090. ISSN 0004-5411. S2CID 18371269.
  4. ↑ Proof: A set V of vertices is an independent set. if and only if every edge in the graph is adjacent to at most one member of V, if and only if every edge in the graph is adjacent to at least one member not in V, if and only if the complement of V is a vertex cover.
  5. ↑ Moon & Moser (1965).
  6. ↑ Füredi (1987).
  7. ↑ Chiba & Nishizeki (1985).
  8. ↑ Berman & Fujito (1995).
  9. ↑ Xiao & Nagamochi (2017)
  10. ↑ Xiao & Nagamochi (2013)
  11. ↑ Minty (1980),Sbihi (1980),Nakamura & Tamura (2001),Faenza, Oriolo & Stauffer (2014),Nobili & Sassano (2015)
  12. ↑ Lokshtanov, Vatshelle & Villanger (2014)
  13. ↑ Grötschel, Lovász & Schrijver (1988)
  14. ↑ Frank (1976)
  15. ↑ Tarjan (1985)
  16. ↑ Bazgan, Cristina; Escoffier, Bruno; Paschos, Vangelis Th. (2005). "Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness". Theoretical Computer Science. 339 (2–3): 272–292. doi:10.1016/j.tcs.2005.03.007. S2CID 1418848.
  17. ↑ Baker (1994); Grohe (2003).
  18. ↑ Halldórsson & Radhakrishnan (1997).
  19. ↑ Chlebík, Miroslav; Chlebíková, Janka (2003). "एनपी-हार्ड समस्याओं की छोटी घटना के उदाहरणों के लिए सन्निकटन कठोरता". Proceedings of the 5th International Conference on Algorithms and Complexity. Lecture Notes in Computer Science. 2653: 152–164. doi:10.1007/3-540-44849-7_21. ISBN 978-3-540-40176-6.
  20. ↑ Neuwohner, Meike (2021-06-07). "डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम". arXiv:2106.03545. {{cite journal}}: Cite journal requires |journal= (help)
  21. ↑ Cygan, Marek (October 2013). "Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search". 2013 IEEE 54th Annual Symposium on Foundations of Computer Science: 509–518. arXiv:1304.1424. doi:10.1109/FOCS.2013.61. ISBN 978-0-7695-5135-7. S2CID 14160646.
  22. ↑ Luby (1986).
  23. ↑ Skiena, Steven S. (2012). एल्गोरिथ्म डिजाइन मैनुअल. Springer. ISBN 978-1-84800-069-8. OCLC 820425142.
  24. ↑ Hossain, Ayaan; Lopez, Eriberto; Halper, Sean M.; Cetnar, Daniel P.; Reis, Alexander C.; Strickland, Devin; Klavins, Eric; Salis, Howard M. (2020-07-13). "इंजीनियरिंग स्थिर आनुवंशिक प्रणालियों के लिए हजारों गैर-दोहराव वाले भागों का स्वचालित डिजाइन". Nature Biotechnology (in English). 38 (12): 1466–1475. doi:10.1038/s41587-020-0584-2. ISSN 1546-1696. PMID 32661437. S2CID 220506228.

संदर्भ

बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=स्वतंत्र_सेट_(ग्राफ_सिद्धांत)&oldid=111076’