स्वतंत्र सेट (ग्राफ सिद्धांत): 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) के लिए नौ नीले कोने अधिकतम स्वतंत्र | [[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> इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र समुच्चय को खोजने के लिए कुशल एल्गोरिथम सम्मिलित है।'' | ||
प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, | प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, किन्तु इसका विलोम निहितार्थ आवश्यक नहीं है। | ||
== गुण == | == गुण == | ||
| 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> इसलिए, सबसे बड़े स्वतंत्र | एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण हो।<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>G</math> स्वतंत्र उपसमुच्चय में इसके शीर्ष समुच्चय के समुच्चय के विभाजन के अनुरूप है। इसलिए शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या <math>\chi(G)</math>, कम से कम शीर्षों की संख्या का भागफल है <math>G</math> और स्वतंत्र संख्या <math>\alpha(G)</math>. | ||
एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र | एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र समुच्चय में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय। | ||
=== अधिकतम स्वतंत्र | === अधिकतम स्वतंत्र समुच्चय === | ||
{{Main| | {{Main|अधिकतम स्वतंत्र सेट}} | ||
एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है, उच्चिष्ठ कहलाता है। इस तरह के | एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है, उच्चिष्ठ कहलाता है। इस तरह के समुच्चय [[हावी सेट|हावी समुच्चय]] होते हैं। प्रत्येक ग्राफ में अधिकतम 3 होते हैं<sup>n/3</sup> अधिकतम स्वतंत्र समुच्चय,<ref>{{harvtxt|Moon|Moser|1965}}.</ref> किन्तु कई रेखांकन बहुत कम हैं। | ||
एन-वर्टेक्स [[चक्र ग्राफ]] में अधिकतम स्वतंत्र | एन-वर्टेक्स [[चक्र ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पेरिन संख्या]] द्वारा दी गई है, और एन-वर्टेक्स [[पथ ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पडोवन अनुक्रम]] द्वारा दी गई है।<ref>{{harvtxt|Füredi|1987}}.</ref> इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं। | ||
== स्वतंत्र | == स्वतंत्र समुच्चय ढूँढना == | ||
{{See| | {{See|क्लिक समस्या}} | ||
[[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है। | [[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है। | ||
*अधिकतम स्वतंत्र | *अधिकतम स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र समुच्चय है। यदि एकाधिक अधिकतम स्वतंत्र समुच्चय हैं, तो केवल आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है। | ||
*अधिकतम-भार स्वतंत्र | *अधिकतम-भार स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र समुच्चय है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं। | ||
* अधिकतम स्वतंत्र | * अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र समुच्चय समस्या को अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र समुच्चय को सभी अधिकतम स्वतंत्र सेटों में सम्मिलित किया जाना चाहिए। | ||
*स्वतंत्र | *स्वतंत्र समुच्चय निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'के'' है, और आउटपुट [[सत्य मूल्य]] है: सच है यदि ग्राफ में आकार 'के'' का स्वतंत्र समुच्चय होता है, और गलत अन्यथा . | ||
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र | इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र समुच्चय निर्णय समस्या नहीं है, किन्तु स्वतंत्र समुच्चय से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है। | ||
=== अधिकतम स्वतंत्र | === अधिकतम स्वतंत्र समुच्चय और अधिकतम समूह === | ||
स्वतंत्र | स्वतंत्र समुच्चय समस्या और [[क्लिक समस्या]] पूरक हैं: जी में समूह जी के पूरक ग्राफ में स्वतंत्र समुच्चय है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं: | ||
* स्वतंत्र | * स्वतंत्र समुच्चय निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है। | ||
* अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन |एनपी कठिन]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है। | * अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन |एनपी कठिन]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है। | ||
मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के | मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के अतिरिक्त, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र समुच्चय और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> चूंकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र समुच्चय खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।<ref>{{harvtxt|Berman|Fujito|1995}}.</ref> | ||
{{See| | {{See|क्लिक प्रॉब्लम # मनमाना ग्राफ़ में अधिकतम क्लिक ढूँढना}} | ||
=== सटीक एल्गोरिदम === | === सटीक एल्गोरिदम === | ||
अधिकतम स्वतंत्र | अधिकतम स्वतंत्र समुच्चय समस्या एनपी-हार्ड है। चूंकि, इसे 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|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> चूंकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं। | ||
=== [[ प्लेनर ग्राफ | प्लेनर ग्राफ]] में === | === [[ प्लेनर ग्राफ | प्लेनर ग्राफ]] में === | ||
प्लानर ग्राफ़ में, अधिकतम स्वतंत्र | प्लानर ग्राफ़ में, अधिकतम स्वतंत्र समुच्चय को बहुपद समय में किसी भी सन्निकटन अनुपात 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> | ||
=== इंटरसेक्शन ग्राफ में === | === इंटरसेक्शन ग्राफ में === | ||
{{Main| | {{Main|अंतराल समयबद्धन}} | ||
एक [[अंतराल ग्राफ]] ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है | एक [[अंतराल ग्राफ]] ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है यदि और केवल यदि वे दूसरे को काटते हैं। अंतराल ग्राफ में स्वतंत्र समुच्चय गैर-अतिव्यापी अंतराल का समुच्चय है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[ कार्य निर्धारण |कार्य निर्धारण]] के संदर्भ में: जॉब का समुच्चय दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम समुच्चय खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है दूसरे के साथ। इस समस्या को [[जल्द से जल्द समय सीमा पहले शेड्यूलिंग]] का उपयोग करके बहुपद समय में हल किया जा सकता है। | ||
=== ज्यामितीय चौराहों के रेखांकन में === | === ज्यामितीय चौराहों के रेखांकन में === | ||
{{Main| | {{Main|अधिकतम असंबद्ध सेट}} | ||
[[ चौराहा ग्राफ | चौराहा ग्राफ]] में अधिकतम स्वतंत्र | एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र समुच्चय केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का समुच्चय है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[स्वचालित लेबल प्लेसमेंट]] के संदर्भ में: मानचित्र में स्थानों का समुच्चय दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम समुच्चय खोजें। | ||
[[ चौराहा ग्राफ | चौराहा ग्राफ]] में अधिकतम स्वतंत्र समुच्चय ढूँढना अभी भी एनपी-पूर्ण है, किन्तु सामान्य अधिकतम स्वतंत्र समुच्चय समस्या की तुलना में अनुमानित करना आसान है। हालिया सर्वेक्षण के परिचय में पाया जा सकता है {{harvtxt|चैन|हर पेलेड|2012}}. | |||
=== डी-पंजे से मुक्त ग्राफ में === | === डी-पंजे से मुक्त ग्राफ में === | ||
एक ग्राफ़ में डी-पंजे डी + 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 सन्निकटन प्राप्त करता है। | ||
=== अधिकतम स्वतंत्र | === अधिकतम स्वतंत्र समुच्चय ढूँढना === | ||
{{Main| | {{Main|अधिकतम स्वतंत्र सेट}} | ||
एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र | एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या को हल किया जा सकता है।<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> | ||
== यह भी देखें == | == यह भी देखें == | ||
* किनारों का स्वतंत्र | * किनारों का स्वतंत्र समुच्चय किनारों का समुच्चय होता है, जिसमें किन्हीं भी दो में शीर्ष उभयनिष्ठ नहीं होता है। इसे चूंकि [[मिलान (ग्राफ सिद्धांत)]] कहा जाता है। | ||
* एक [[शीर्ष रंग]] स्वतंत्र | * एक [[शीर्ष रंग]] स्वतंत्र समुच्चय में शीर्ष समुच्चय का विभाजन है। | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Revision as of 18:53, 13 March 2023
सामान्यीकृत पीटरसन ग्राफ GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र समुच्चय बनाते हैं।
ग्राफ सिद्धांत में, स्वतंत्र समुच्चय, स्थिर समुच्चय, कोक्लिक या एंटीक्लिक ग्राफ (असतत गणित) में वर्टेक्स (ग्राफ सिद्धांत) का समुच्चय है, जिनमें से कोई भी आसन्न नहीं है। अर्ताथ यह समुच्चय है शीर्षों का ऐसा है कि प्रत्येक दो शीर्षों के लिए , दोनों को जोड़ने वाला कोई किनारा (ग्राफ सिद्धांत) नहीं है। समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम समापन बिंदु होता है . समुच्चय स्वतंत्र है यदि और केवल यदि यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) है। स्वतंत्र समुच्चय का आकार इसमें सम्मिलित शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर समुच्चय भी कहा जाता है, जिनमें से स्थिर समुच्चय छोटा होता है।[1]
एक अधिकतम स्वतंत्र समुच्चय स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।
एक अधिकतम स्वतंत्र समुच्चय किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का स्वतंत्र समुच्चय है . इस आकार को की स्वतंत्रता संख्या कहा जाता हैऔर चूंकि द्वारा निरूपित किया जाता है .[2] ऐसे समुच्चय को खोजने की अनुकूलन समस्या को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह मजबूत एनपी-पूर्णता है | दृढ़ता से एनपी-कठिन समस्या है।[3] इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र समुच्चय को खोजने के लिए कुशल एल्गोरिथम सम्मिलित है।
प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, किन्तु इसका विलोम निहितार्थ आवश्यक नहीं है।
गुण
अन्य ग्राफ़ पैरामीटर्स से संबंध
एक समुच्चय स्वतंत्र है यदि और केवल यदि यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) है, तो दो अवधारणाएं पूरक हैं। वास्तव में, बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र समुच्चय होते हैं, विषय जिसे रैमसे सिद्धांत में खोजा गया है।
एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण हो।[4] इसलिए, सबसे बड़े स्वतंत्र समुच्चय के आकार का योग और न्यूनतम वर्टेक्स कवर का आकार ग्राफ़ में शीर्षों की संख्या के बराबर है।
एक ग्राफ का ग्राफ रंगना स्वतंत्र उपसमुच्चय में इसके शीर्ष समुच्चय के समुच्चय के विभाजन के अनुरूप है। इसलिए शीर्ष रंग, रंगीन संख्या में आवश्यक रंगों की न्यूनतम संख्या , कम से कम शीर्षों की संख्या का भागफल है और स्वतंत्र संख्या .
एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र समुच्चय में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है; यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है|कोनिग की प्रमेय।
अधिकतम स्वतंत्र समुच्चय
एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है, उच्चिष्ठ कहलाता है। इस तरह के समुच्चय हावी समुच्चय होते हैं। प्रत्येक ग्राफ में अधिकतम 3 होते हैंn/3 अधिकतम स्वतंत्र समुच्चय,[5] किन्तु कई रेखांकन बहुत कम हैं। एन-वर्टेक्स चक्र ग्राफ में अधिकतम स्वतंत्र समुच्चय की संख्या पेरिन संख्या द्वारा दी गई है, और एन-वर्टेक्स पथ ग्राफ में अधिकतम स्वतंत्र समुच्चय की संख्या पडोवन अनुक्रम द्वारा दी गई है।[6] इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं।
स्वतंत्र समुच्चय ढूँढना
कंप्यूटर विज्ञान में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।
- अधिकतम स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र समुच्चय है। यदि एकाधिक अधिकतम स्वतंत्र समुच्चय हैं, तो केवल आउटपुट होना चाहिए। इस समस्या को कभी-कभी वर्टेक्स पैकिंग कहा जाता है।
- अधिकतम-भार स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र समुच्चय है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं।
- अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र समुच्चय समस्या को अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र समुच्चय को सभी अधिकतम स्वतंत्र सेटों में सम्मिलित किया जाना चाहिए।
- स्वतंत्र समुच्चय निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'के है, और आउटपुट सत्य मूल्य है: सच है यदि ग्राफ में आकार 'के का स्वतंत्र समुच्चय होता है, और गलत अन्यथा .
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं; स्वतंत्र समुच्चय निर्णय समस्या नहीं है, किन्तु स्वतंत्र समुच्चय से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।
अधिकतम स्वतंत्र समुच्चय और अधिकतम समूह
स्वतंत्र समुच्चय समस्या और क्लिक समस्या पूरक हैं: जी में समूह जी के पूरक ग्राफ में स्वतंत्र समुच्चय है और इसके विपरीत। इसलिए, कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:
- स्वतंत्र समुच्चय निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है।
- अधिकतम स्वतंत्र समुच्चय समस्या एनपी कठिन है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।
मनमाने ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के अतिरिक्त, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र समुच्चय और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से ज़्यादा से ज़्यादा स्थिर होती है), अधिकतम क्लिक का आकार बंधा हुआ होता है और बिल्कुल रैखिक समय में पाया जा सकता है;[7] चूंकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र समुच्चय खोजना SNP (जटिलता) है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।[8]
सटीक एल्गोरिदम
अधिकतम स्वतंत्र समुच्चय समस्या एनपी-हार्ड है। चूंकि, इसे 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]
इंटरसेक्शन ग्राफ में
एक अंतराल ग्राफ ग्राफ है जिसमें नोड्स 1-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है यदि और केवल यदि वे दूसरे को काटते हैं। अंतराल ग्राफ में स्वतंत्र समुच्चय गैर-अतिव्यापी अंतराल का समुच्चय है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, कार्य निर्धारण के संदर्भ में: जॉब का समुच्चय दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम समुच्चय खोजें जो बिना हस्तक्षेप के निष्पादित किया जा सकता है दूसरे के साथ। इस समस्या को जल्द से जल्द समय सीमा पहले शेड्यूलिंग का उपयोग करके बहुपद समय में हल किया जा सकता है।
ज्यामितीय चौराहों के रेखांकन में
एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र समुच्चय केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का समुच्चय है। ज्यामितीय चौराहों के ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, स्वचालित लेबल प्लेसमेंट के संदर्भ में: मानचित्र में स्थानों का समुच्चय दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम समुच्चय खोजें।
चौराहा ग्राफ में अधिकतम स्वतंत्र समुच्चय ढूँढना अभी भी एनपी-पूर्ण है, किन्तु सामान्य अधिकतम स्वतंत्र समुच्चय समस्या की तुलना में अनुमानित करना आसान है। हालिया सर्वेक्षण के परिचय में पाया जा सकता है चैन & हर पेलेड (2012).
डी-पंजे से मुक्त ग्राफ में
एक ग्राफ़ में डी-पंजे डी + 1 कोने का समुच्चय है, जिनमें से (केंद्र) अन्य डी कोने से जुड़ा हुआ है, किन्तु अन्य डी कोने दूसरे से जुड़े नहीं हैं। डी-क्लॉ-फ्री ग्राफ ऐसा ग्राफ है जिसमें डी-क्लॉ सबग्राफ नहीं होता है। एल्गोरिदम पर विचार करें जो खाली समुच्चय के साथ प्रारंभ होता है, और जब तक यह किसी मौजूदा शीर्ष के निकट नहीं होता है, तब तक इसमें मनमाना वर्टेक्स जोड़ता है। डी-क्लॉ-फ्री ग्राफ़ में, प्रत्येक जोड़ा शीर्ष अधिकतम स्वतंत्र समुच्चय से अधिकांश d-1 शीर्षों पर अमान्य हो जाता है; इसलिए, यह तुच्छ एल्गोरिथम अधिकतम स्वतंत्र समुच्चय के लिए (d-1)-समीक्षा एल्गोरिथम प्राप्त करता है। वास्तव में, बहुत उत्तम सन्निकटन अनुपात प्राप्त करना संभव है:
- न्यूवॉनर[20] बहुपद समय एल्गोरिदम प्रस्तुत किया गया है, जो किसी भी निरंतर ε> 0 के लिए, (डी/2-1/63,700,992+ε) पाता है - डी-क्लॉ फ्री ग्राफ में अधिकतम वजन स्वतंत्र समुच्चय के लिए सन्निकटन।
- साइगन[21] अर्ध-बहुपद समय एल्गोरिथ्म प्रस्तुत किया है, जो किसी भी ε>0 के लिए, (d+ε)/3 सन्निकटन प्राप्त करता है।
अधिकतम स्वतंत्र समुच्चय ढूँढना
एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या को हल किया जा सकता है।[22] सभी अधिकतम स्वतंत्र समुच्चय समय ओ (3) में पाए जा सकते हैंn/3) = ओ (1.4423एन).
अनुप्रयोग
अधिकतम स्वतंत्र समुच्चय और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के कम्प्यूटेशनल जटिलता सिद्धांत को सिद्ध करने में सम्मिलित है।[23] वे वास्तविक विश्व अनुकूलन समस्याओं के लिए उपयोगी मॉडल के रूप में भी काम करते हैं, उदाहरण के लिए संश्लेषित जीव विज्ञान विज्ञान को डिजाइन करने के लिए स्थिर जीन नियामक नेटवर्क की खोज के लिए अधिकतम स्वतंत्र समुच्चय उपयोगी मॉडल है।[24]
यह भी देखें
- किनारों का स्वतंत्र समुच्चय किनारों का समुच्चय होता है, जिसमें किन्हीं भी दो में शीर्ष उभयनिष्ठ नहीं होता है। इसे चूंकि मिलान (ग्राफ सिद्धांत) कहा जाता है।
- एक शीर्ष रंग स्वतंत्र समुच्चय में शीर्ष समुच्चय का विभाजन है।
टिप्पणियाँ
- ↑ Korshunov (1974)
- ↑ Godsil & Royle (2001), p. 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.
- ↑ 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.
- ↑ Moon & Moser (1965).
- ↑ Füredi (1987).
- ↑ Chiba & Nishizeki (1985).
- ↑ Berman & Fujito (1995).
- ↑ Xiao & Nagamochi (2017)
- ↑ Xiao & Nagamochi (2013)
- ↑ Minty (1980),Sbihi (1980),Nakamura & Tamura (2001),Faenza, Oriolo & Stauffer (2014),Nobili & Sassano (2015)
- ↑ Lokshtanov, Vatshelle & Villanger (2014)
- ↑ Grötschel, Lovász & Schrijver (1988)
- ↑ Frank (1976)
- ↑ Tarjan (1985)
- ↑ 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.
- ↑ Baker (1994); Grohe (2003).
- ↑ Halldórsson & Radhakrishnan (1997).
- ↑ 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.
- ↑ Neuwohner, Meike (2021-06-07). "डी-क्लॉ मुक्त रेखांकन में अधिकतम वजन स्वतंत्र सेट समस्या के लिए एक बेहतर सन्निकटन एल्गोरिथम". arXiv:2106.03545.
{{cite journal}}: Cite journal requires|journal=(help) - ↑ 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.
- ↑ Luby (1986).
- ↑ Skiena, Steven S. (2012). एल्गोरिथ्म डिजाइन मैनुअल. Springer. ISBN 978-1-84800-069-8. OCLC 820425142.
- ↑ 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.
संदर्भ
- Baker, Brenda S. (1994), "Approximation algorithms for NP-complete problems on planar graphs", Journal of the ACM, 41 (1): 153–180, doi:10.1145/174644.174650, S2CID 9706753.
- Berman, Piotr; Fujito, Toshihiro (1995), "On approximation properties of the Independent set problem for degree 3 graphs", Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 955, Springer-Verlag, pp. 449–460, doi:10.1007/3-540-60220-8_84, ISBN 978-3-540-60220-0.
- Berman, Piotr; Karpinski, Marek (1999), "On some tighter inapproximability results", Automata, Languages and Programming, 26th International Colloquium, ICALP'99 Prague, Lecture Notes in Computer Science, vol. 1644, Prague: Springer-Verlag, pp. 200–209, doi:10.1007/3-540-48523-6, ISBN 978-3-540-66224-2, S2CID 23288736
- Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis Th.; van Rooij, Johan M. M. (2010), "A bottom-up method and fast algorithms for MAX INDEPENDENT SET", Algorithm theory—SWAT 2010, Lecture Notes in Computer Science, vol. 6139, Berlin: Springer, pp. 62–73, Bibcode:2010LNCS.6139...62B, doi:10.1007/978-3-642-13731-0_7, ISBN 978-3-642-13730-3, MR 2678485.
- Chan, T. M. (2003), "Polynomial-time approximation schemes for packing and piercing fat objects", Journal of Algorithms, 46 (2): 178–189, CiteSeerX 10.1.1.21.5344, doi:10.1016/s0196-6774(02)00294-8.
- Chan, T. M.; Har-Peled, S. (2012), "Approximation algorithms for maximum independent set of pseudo-disks", Discrete & Computational Geometry, 48 (2): 373, arXiv:1103.1431, CiteSeerX 10.1.1.219.2131, doi:10.1007/s00454-012-9417-5, S2CID 38183751.
- Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017.
- Erlebach, T.; Jansen, K.; Seidel, E. (2005), "Polynomial-Time Approximation Schemes for Geometric Intersection Graphs", SIAM Journal on Computing, 34 (6): 1302, doi:10.1137/s0097539702402676.
- Faenza, Yuri; Oriolo, Gianpaolo; Stauffer, Gautier (2014), "Solving the Weighted Stable Set Problem in Claw-Free Graphs", Journal of the ACM, 61 (4): 1–41, doi:10.1145/2629600, S2CID 1995056.
- Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), "A measure & conquer approach for the analysis of exact algorithms", Journal of the ACM, 56 (5): 1–32, doi:10.1145/1552285.1552286, S2CID 1186651, article no. 25
{{citation}}: CS1 maint: postscript (link). - Frank, András (1976), "Some polynomial algorithms for certain graphs and hypergraphs", Congressus Numerantium, XV: 211–226.
- Füredi, Zoltán (1987), "The number of maximal independent sets in connected graphs", Journal of Graph Theory, 11 (4): 463–470, doi:10.1002/jgt.3190110403.
- Godsil, Chris; Royle, Gordon (2001), Algebraic Graph Theory, New York: Springer, ISBN 978-0-387-95220-8.
- Grohe, Martin (2003), "Local tree-width, excluded minors, and approximation algorithms", Combinatorica, 23 (4): 613–632, arXiv:math/0001128, doi:10.1007/s00493-003-0037-9, S2CID 11751235.
- Grötschel, M.; Lovász, L.; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer-Verlag, pp. 296–298, ISBN 978-0-387-13624-0.
- Halldórsson, M. M.; Radhakrishnan, J. (1997), "Greed is good: Approximating independent sets in sparse and bounded-degree graphs", Algorithmica, 18 (1): 145–163, CiteSeerX 10.1.1.145.4523, doi:10.1007/BF02523693, S2CID 4661668.
- Korshunov, A.D. (1974), "Coefficient of Internal Stability", Kibernetika (in українська), 10 (1): 17–28, doi:10.1007/BF01069014, S2CID 120343511.
- Lokshtanov, D.; Vatshelle, M.; Villanger, Y. (2014), "Independent sets in P5-free graphs in polynomial time", SODA (Symposium on Discrete Algorithms): 570–581.
- Luby, Michael (1986), "A simple parallel algorithm for the maximal independent set problem", SIAM Journal on Computing, 15 (4): 1036–1053, CiteSeerX 10.1.1.225.5475, doi:10.1137/0215074, MR 0861369.
- Minty, G.J. (1980), "On maximal independent sets of vertices in claw-free graphs", Journal of Combinatorial Theory, Series B, 28 (3): 284–304, doi:10.1016/0095-8956(80)90074-x.
- Moon, J.W.; Moser, Leo (1965), "On cliques in graphs", Israel Journal of Mathematics, 3 (1): 23–28, doi:10.1007/BF02760024, MR 0182577, S2CID 9855414.
- Nakamura, D.; Tamura, A. (2001), "A revision of Minty's algorithm for finding a maximum weight stable set in a claw-free graph", Journal of Operations Research Society Japan, 44 (2): 194–204, doi:10.15807/jorsj.44.194.
- Nobili, P.; Sassano, A. (2015), An O(n^2 log n) algorithm for the weighted stable set problem in claw-free graphs, arXiv:1501.05775, Bibcode:2015arXiv150105775N
- Robson, J. M. (1986), "Algorithms for maximum independent sets", Journal of Algorithms, 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5.
- Sbihi, Najiba (1980), "Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile", Discrete Mathematics (in français), 29 (1): 53–76, doi:10.1016/0012-365X(90)90287-R, MR 0553650.
- Xiao, Mingyu; Nagamochi, Hiroshi (2017), "Exact algorithms for maximum independent set", Information and Computation, 255: 126–146, arXiv:1312.6260, doi:10.1016/j.ic.2017.06.001, S2CID 1714739.
- Xiao, Mingyu; Nagamochi, Hiroshi (2013), "Confining sets and avoiding bottleneck cases: A simple maximum independent set algorithm in degree-3 graphs", Theoretical Computer Science, 469: 92–104, doi:10.1016/j.tcs.2012.09.022.
- Tarjan, R.E. (1985), "Decomposition by clique separators", Discrete Mathematics, 55 (2): 221–232, doi:10.1016/0012-365x(85)90051-2.
