स्वतंत्र सेट (ग्राफ सिद्धांत): Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 intermediate revisions by 4 users not shown) | |||
| 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> इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र समुच्चय को खोजने के लिए कुशल एल्गोरिथम सम्मिलित है।'' | |||
प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, किन्तु इसका विलोम निहितार्थ आवश्यक नहीं है। | प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, किन्तु इसका विलोम निहितार्थ आवश्यक नहीं है। | ||
== गुण == | == गुण == | ||
===अन्य ग्राफ़ पैरामीटर्स से संबंध=== | ===अन्य ग्राफ़ पैरामीटर्स से संबंध=== | ||
एक समुच्चय स्वतंत्र है | एक समुच्चय इस प्रकार स्वतंत्र रहता है कि यदि यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) होता है, तो दो अवधारणाएं पूरक रहती हैं। जहाँ वास्तव में बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र समुच्चय होते हैं, विषय जिसे [[रैमसे सिद्धांत]] में खोजा गया है। | ||
एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण | एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण होता हैं।<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> पर निर्भर करती हैं। | ||
एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने नहीं हैं, अधिकतम स्वतंत्र समुच्चय में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है | एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने पर नहीं रहती हैं, इस प्रकार अधिकतम स्वतंत्र समुच्चय में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है, यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है। | ||
=== अधिकतम स्वतंत्र समुच्चय === | === अधिकतम स्वतंत्र समुच्चय === | ||
| Line 26: | Line 24: | ||
{{Main|अधिकतम स्वतंत्र सेट}} | {{Main|अधिकतम स्वतंत्र सेट}} | ||
एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है | एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है जो कि उच्चिष्ठ कहलाता है। इस प्रकार के समुच्चय [[हावी सेट|हावी समुच्चय]] होते हैं। प्रत्येक ग्राफ में अधिकतम 3<sup>n/3</sup> होते हैं अधिकतम स्वतंत्र समुच्चय,<ref>{{harvtxt|Moon|Moser|1965}}.</ref> किन्तु कई रेखांकन बहुत कम हैं। | ||
एन-वर्टेक्स [[चक्र ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पेरिन संख्या]] द्वारा दी गई है, और एन-वर्टेक्स [[पथ ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पडोवन अनुक्रम]] द्वारा दी गई है।<ref>{{harvtxt|Füredi|1987}}.</ref> इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं। | एन-वर्टेक्स [[चक्र ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पेरिन संख्या]] द्वारा दी गई है, और एन-वर्टेक्स [[पथ ग्राफ]] में अधिकतम स्वतंत्र समुच्चय की संख्या [[पडोवन अनुक्रम]] द्वारा दी गई है।<ref>{{harvtxt|Füredi|1987}}.</ref> इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं। | ||
| Line 34: | Line 33: | ||
[[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है। | [[कंप्यूटर विज्ञान]] में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है। | ||
*अधिकतम स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र समुच्चय है। यदि एकाधिक अधिकतम स्वतंत्र समुच्चय हैं, तो केवल आउटपुट होना चाहिए। इस | *अधिकतम स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र समुच्चय है। यदि एकाधिक अधिकतम स्वतंत्र समुच्चय हैं, तो केवल आउटपुट होना चाहिए। इस समस्याओं को कभी-कभी वर्टेक्स पैकिंग भी कहा जाता है। | ||
*अधिकतम-भार स्वतंत्र समुच्चय | *अधिकतम-भार स्वतंत्र समुच्चय समस्याओं में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र समुच्चय है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं। | ||
* अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र समुच्चय समस्या को अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र समुच्चय को सभी अधिकतम स्वतंत्र सेटों में सम्मिलित किया जाना चाहिए। | * अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र समुच्चय समस्या को अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र समुच्चय को सभी अधिकतम स्वतंत्र सेटों में सम्मिलित किया जाना चाहिए। | ||
*स्वतंत्र समुच्चय निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या ' | *स्वतंत्र समुच्चय निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'k'' है, और आउटपुट [[सत्य मूल्य]] है: सच है यदि ग्राफ में आकार ' K'' का स्वतंत्र समुच्चय और गलत अन्यथा होता है। | ||
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं | इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं, स्वतंत्र समुच्चय निर्णय समस्या नहीं है, किन्तु स्वतंत्र समुच्चय से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है। | ||
=== अधिकतम स्वतंत्र समुच्चय और अधिकतम समूह === | === अधिकतम स्वतंत्र समुच्चय और अधिकतम समूह === | ||
स्वतंत्र समुच्चय समस्या और [[क्लिक समस्या]] पूरक हैं: जी में समूह जी के पूरक ग्राफ में स्वतंत्र समुच्चय | स्वतंत्र समुच्चय समस्या और [[क्लिक समस्या]] पूरक हैं: जी में समूह जी के पूरक ग्राफ में और इसके विपरीत स्वतंत्र समुच्चय है। इसलिए कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं: | ||
* स्वतंत्र समुच्चय निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है। | * स्वतंत्र समुच्चय निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है। | ||
* अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन |एनपी कठिन]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है। | * अधिकतम स्वतंत्र समुच्चय समस्या [[ एनपी कठिन |एनपी कठिन]] है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है। | ||
इन ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के अतिरिक्त, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र समुच्चय और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से अधिक स्थिर होती है), इस प्रकार अधिकतम क्लिक का आकार बंधा रहता है और बिल्कुल रैखिक समय में पाया जा सकता है;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> चूंकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र समुच्चय की जाँच SNP के कारण जटिलता से होती है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।<ref>{{harvtxt|Berman|Fujito|1995}}.</ref> | |||
{{See|क्लिक प्रॉब्लम # मनमाना ग्राफ़ में अधिकतम क्लिक ढूँढना}} | {{See|क्लिक प्रॉब्लम # मनमाना ग्राफ़ में अधिकतम क्लिक ढूँढना}} | ||
=== सटीक एल्गोरिदम === | === सटीक एल्गोरिदम === | ||
अधिकतम स्वतंत्र समुच्चय समस्या एनपी-हार्ड है। चूंकि, इसे O | अधिकतम स्वतंत्र समुच्चय समस्या एनपी-हार्ड है। चूंकि, इसे O<sup>2</sup>(n)2<sup>n</sup> की तुलना में अधिक कुशलता से हल किया जा सकता है ) समय जो भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह स्वतंत्र समुच्चय है। | ||
2017 तक इसे O (1.1996.1) समय में हल किया जा सकता है | 2017 तक इसे O<sup>n</sup> (1.1996.1) समय में हल किया जा सकता है) बहुपद स्थान का उपयोग करके किया जाता हैं।<ref>{{harvtxt|Xiao|Nagamochi|2017}}</ref> यहाँ पर अधिकतम डिग्री 3<sup>n</sup> वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता है)।<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|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> | ||
कोनिग की प्रमेय (ग्राफ सिद्धांत) | कोनिग की प्रमेय (ग्राफ सिद्धांत) या कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र समुच्चय पाया जा सकता है। | ||
=== सन्निकटन एल्गोरिदम === | === सन्निकटन एल्गोरिदम === | ||
सामान्यतः अधिकतम स्वतंत्र समुच्चय समस्या को बहुपद समय में स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि P = np)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र समुच्चय एपीएक्स संबंधित जटिलता वर्ग है। पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है।<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 के भीतर अनुमानित किया जा सकता है | प्लानर ग्राफ़ में, अधिकतम स्वतंत्र समुच्चय को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है, [[माइनर (ग्राफ सिद्धांत)]] लेने के अनुसार बंद किए गए ग्राफ़ के किसी भी समूह में समान [[बहुपद-समय सन्निकटन योजना]]एं सम्मिलित हैं।<ref>{{harvtxt|Baker|1994}}; {{harvtxt|Grohe|2003}}.</ref> | ||
=== बाउंडेड डिग्री ग्राफ़ में === | === बाउंडेड डिग्री ग्राफ़ में === | ||
बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को [[सन्निकटन अनुपात]] के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, लालची एल्गोरिद्म जो अधिकतम स्वतंत्र समुच्चय बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके | बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को [[सन्निकटन अनुपात]] के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, लालची एल्गोरिद्म जो अधिकतम स्वतंत्र समुच्चय बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके समीपस्थ मानों को हटाकर, अधिकतम Δ डिग्री वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है।<ref>{{harvtxt|Halldórsson|Radhakrishnan|1997}}.</ref> ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी। इस प्रकार {{harvtxt|बरमानी|करपिंसकी|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-आयामी अंतराल (जैसे समय अंतराल) होते हैं और दो अंतरालों के बीच किनारा होता है यदि और केवल यदि वे दूसरे को काटते हैं। अंतराल ग्राफ में स्वतंत्र समुच्चय गैर-अतिव्यापी अंतराल का समुच्चय है। इंटरवल ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[ कार्य निर्धारण |कार्य निर्धारण]] के संदर्भ में: जॉब का समुच्चय दिया गया है जिसे कंप्यूटर पर निष्पादित किया जाना है, जॉब का अधिकतम समुच्चय खोजा जाता हैं जो बिना किसी और के साथ हस्तक्षेप किए निष्पादित किया जा सकता है। इस समस्या को [[जल्द से जल्द समय सीमा पहले शेड्यूलिंग|शीघ्रता से समय सीमा से पहले शेड्यूलिंग]] का उपयोग करके बहुपद समय में हल किया जा सकता है। | |||
=== ज्यामितीय | === ज्यामितीय अंतः खण्डों के रेखांकन में === | ||
{{Main|अधिकतम असंबद्ध सेट}} | {{Main|अधिकतम असंबद्ध सेट}} | ||
एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र समुच्चय केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का समुच्चय है। ज्यामितीय | एक ज्यामितीय प्रतिच्छेदन ग्राफ ऐसा ग्राफ है जिसमें नोड्स ज्यामितीय आकार होते हैं और दो आकृतियों के बीच किनारा होता है यदि और केवल यदि वे प्रतिच्छेद करते हैं। ज्यामितीय चौराहे के ग्राफ में स्वतंत्र समुच्चय केवल असंबद्ध (गैर-अतिव्यापी) आकृतियों का समुच्चय है। ज्यामितीय अंतः खण्डों के ग्राफ़ में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या का अध्ययन किया गया है, उदाहरण के लिए, [[स्वचालित लेबल प्लेसमेंट]] के संदर्भ में: मानचित्र में स्थानों का समुच्चय दिया गया है, इन स्थानों के निकट असंबद्ध आयताकार लेबल का अधिकतम समुच्चय खोजें जाते हैं। | ||
[[ चौराहा ग्राफ | | [[ चौराहा ग्राफ |अंतःखण्ड ग्राफ]] में अधिकतम स्वतंत्र समुच्चय ढूँढना अभी भी एनपी-पूर्ण है, किन्तु सामान्य अधिकतम स्वतंत्र समुच्चय समस्या की तुलना में अनुमानित करना आसान है। इस प्रकार सर्वेक्षण के परिचय {{harvtxt|चैन|हर पेलेड|2012}} में पाया जा सकता है। | ||
=== डी- | === डी-पंच से मुक्त ग्राफ में === | ||
एक ग्राफ़ में डी- | एक ग्राफ़ में डी-पंच डी + 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 88: | Line 88: | ||
{{Main|अधिकतम स्वतंत्र सेट}} | {{Main|अधिकतम स्वतंत्र सेट}} | ||
एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या को हल किया जा सकता है।<ref>{{harvtxt|Luby|1986}}.</ref> सभी अधिकतम स्वतंत्र समुच्चय समय ओ (3 | एक तुच्छ लालची एल्गोरिथ्म द्वारा बहुपद समय में अधिकतम स्वतंत्र समुच्चय खोजने की समस्या को हल किया जा सकता है।<ref>{{harvtxt|Luby|1986}}.</ref> सभी अधिकतम स्वतंत्र समुच्चय समय ओ (3<sup>n/3</sup>) में पाए जा सकते हैं) = ओ (1.4423<sup>n</sup>). | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
| Line 285: | Line 285: | ||
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] | * [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring] | ||
* [http://www.hananayad.com/teaching/syde423/IndependentSet.pdf Independent Set and Vertex Cover], Hanan Ayad. | * [http://www.hananayad.com/teaching/syde423/IndependentSet.pdf Independent Set and Vertex Cover], Hanan Ayad. | ||
[[Category: | [[Category:Articles with hatnote templates targeting a nonexistent page]] | ||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:CS1 errors]] | |||
[[Category:CS1 français-language sources (fr)]] | |||
[[Category:CS1 maint]] | |||
[[Category:CS1 українська-language sources (uk)]] | |||
[[Category:Created On 28/02/2023]] | [[Category:Created On 28/02/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:एनपी-पूर्ण समस्याएं]] | |||
[[Category:ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याएं]] | |||
[[Category:ग्राफ सिद्धांत वस्तुओं]] | |||
Latest revision as of 13:34, 17 March 2023
सामान्यीकृत पीटरसन ग्राफ GP(12,4) के लिए नौ नीले कोने अधिकतम स्वतंत्र समुच्चय बनाते हैं।
ग्राफ सिद्धांत में उपस्थित स्वतंत्र समुच्चय ऐसे स्थिर समुच्चय हैं जो कोक्लिक या एंटीक्लिक ग्राफ (असतत गणित) में वर्टेक्स (ग्राफ सिद्धांत) के समुच्चय के रूप में उपयोग होते हैं, जिनमें से कोई भी आसन्न नहीं होता है। यह समुच्चय शीर्षों पर इस प्रकार हैं कि प्रत्येक दो शीर्षों पर इनके लिए दोनों को संयोजित करने वाला ग्राफ सिद्धांत नहीं पाया जाता है। इस प्रकार समान रूप से, ग्राफ़ में प्रत्येक किनारे में अधिकतम समापन बिंदु होता है। इस प्रकार ये समुच्चय स्वतंत्र रहते हैं जिसके लिए यदि यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) के रूप में होते हैं इस बात का ध्यान रखा जाता हैं। स्वतंत्र समुच्चय का आकार इसमें सम्मिलित शीर्षों की संख्या है। स्वतंत्र सेटों को आंतरिक रूप से स्थिर समुच्चय भी कहा जाता है, जिनमें से स्थिर समुच्चय छोटा होता है।[1]
एक अधिकतम स्वतंत्र समुच्चय स्वतंत्र समुच्चय है जो किसी अन्य स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है।
अधिकतम स्वतंत्र समुच्चय किसी दिए गए ग्राफ के लिए सबसे बड़े संभव आकार का स्वतंत्र समुच्चय है . इस आकार को की स्वतंत्रता संख्या कहा जाता है। और चूंकि द्वारा निरूपित किया जाता है।[2] ऐसे समुच्चय को खोजने की अनुकूलन समस्या को अधिकतम स्वतंत्र समुच्चय समस्या कहा जाता है। यह शक्तिशाली एनपी-पूर्णता है। इस प्रकार दृढ़ता से एनपी-कठिन समस्या है।[3] इस प्रकार, यह संभावना नहीं है कि ग्राफ़ के अधिकतम स्वतंत्र समुच्चय को खोजने के लिए कुशल एल्गोरिथम सम्मिलित है।
प्रत्येक अधिकतम स्वतंत्र समुच्चय भी अधिकतम होता है, किन्तु इसका विलोम निहितार्थ आवश्यक नहीं है।
गुण
अन्य ग्राफ़ पैरामीटर्स से संबंध
एक समुच्चय इस प्रकार स्वतंत्र रहता है कि यदि यह ग्राफ के पूरक ग्राफ में क्लिक (ग्राफ सिद्धांत) होता है, तो दो अवधारणाएं पूरक रहती हैं। जहाँ वास्तव में बिना किसी बड़े समूहों के पर्याप्त रूप से बड़े ग्राफ़ में बड़े स्वतंत्र समुच्चय होते हैं, विषय जिसे रैमसे सिद्धांत में खोजा गया है।
एक समुच्चय स्वतंत्र होता है यदि और केवल यदि उसका पूरक शीर्ष आवरण होता हैं।[4] इसलिए, सबसे बड़े स्वतंत्र समुच्चय के आकार का योग और न्यूनतम वर्टेक्स कवर का आकार ग्राफ़ में शीर्षों की संख्या के बराबर है।
एक ग्राफ का ग्राफ को रंग देना तथा स्वतंत्र उपसमुच्चय में इसके शीर्ष समुच्चय के समुच्चय के विभाजन के अनुरूप करता हैं। इसलिए शीर्ष रंगीन होने के कारण इन रंगीन संख्याओं में आवश्यक रंगों की न्यूनतम संख्या , कम से कम शीर्षों की संख्या का भागफल है और स्वतंत्र संख्या पर निर्भर करती हैं।
एक द्विदलीय ग्राफ में जिसमें कोई अलग-थलग कोने पर नहीं रहती हैं, इस प्रकार अधिकतम स्वतंत्र समुच्चय में कोने की संख्या न्यूनतम किनारे को कवर करने वाले किनारों की संख्या के बराबर होती है, यह कोनिग की प्रमेय (ग्राफ सिद्धांत) है।
अधिकतम स्वतंत्र समुच्चय
एक स्वतंत्र समुच्चय जो दूसरे स्वतंत्र समुच्चय का उचित उपसमुच्चय नहीं है जो कि उच्चिष्ठ कहलाता है। इस प्रकार के समुच्चय हावी समुच्चय होते हैं। प्रत्येक ग्राफ में अधिकतम 3n/3 होते हैं अधिकतम स्वतंत्र समुच्चय,[5] किन्तु कई रेखांकन बहुत कम हैं।
एन-वर्टेक्स चक्र ग्राफ में अधिकतम स्वतंत्र समुच्चय की संख्या पेरिन संख्या द्वारा दी गई है, और एन-वर्टेक्स पथ ग्राफ में अधिकतम स्वतंत्र समुच्चय की संख्या पडोवन अनुक्रम द्वारा दी गई है।[6] इसलिए, दोनों संख्याएं 1.324718..., प्लास्टिक संख्या की शक्तियों के समानुपाती हैं।
स्वतंत्र समुच्चय ढूँढना
कंप्यूटर विज्ञान में, स्वतंत्र सेटों से संबंधित कई कम्प्यूटेशनल समस्याओं का अध्ययन किया गया है।
- अधिकतम स्वतंत्र समुच्चय समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट ग्राफ में अधिकतम स्वतंत्र समुच्चय है। यदि एकाधिक अधिकतम स्वतंत्र समुच्चय हैं, तो केवल आउटपुट होना चाहिए। इस समस्याओं को कभी-कभी वर्टेक्स पैकिंग भी कहा जाता है।
- अधिकतम-भार स्वतंत्र समुच्चय समस्याओं में, इनपुट अप्रत्यक्ष ग्राफ है जिसके शीर्ष पर भार है और आउटपुट अधिकतम कुल भार के साथ स्वतंत्र समुच्चय है। अधिकतम स्वतंत्र समुच्चय समस्या वह विशेष स्थिति है जिसमें सभी भार होते हैं।
- अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या में, इनपुट अप्रत्यक्ष ग्राफ है, और आउटपुट इसके सभी अधिकतम स्वतंत्र सेटों की सूची है। अधिकतम स्वतंत्र समुच्चय समस्या को अधिकतम स्वतंत्र समुच्चय लिस्टिंग समस्या के लिए सबरूटीन एल्गोरिथम के रूप में उपयोग करके हल किया जा सकता है, क्योंकि अधिकतम स्वतंत्र समुच्चय को सभी अधिकतम स्वतंत्र सेटों में सम्मिलित किया जाना चाहिए।
- स्वतंत्र समुच्चय निर्णय समस्या में, इनपुट अप्रत्यक्ष ग्राफ और संख्या 'k है, और आउटपुट सत्य मूल्य है: सच है यदि ग्राफ में आकार ' K का स्वतंत्र समुच्चय और गलत अन्यथा होता है।
इनमें से पहली तीन समस्याएं व्यावहारिक अनुप्रयोगों में महत्वपूर्ण हैं, स्वतंत्र समुच्चय निर्णय समस्या नहीं है, किन्तु स्वतंत्र समुच्चय से संबंधित समस्याओं के लिए एनपी-पूर्णता के सिद्धांत को लागू करने के लिए आवश्यक है।
अधिकतम स्वतंत्र समुच्चय और अधिकतम समूह
स्वतंत्र समुच्चय समस्या और क्लिक समस्या पूरक हैं: जी में समूह जी के पूरक ग्राफ में और इसके विपरीत स्वतंत्र समुच्चय है। इसलिए कई कम्प्यूटेशनल परिणाम किसी भी समस्या के लिए समान रूप से अच्छी तरह से लागू किए जा सकते हैं। उदाहरण के लिए, क्लिक समस्या से संबंधित परिणामों में निम्नलिखित परिणाम होते हैं:
- स्वतंत्र समुच्चय निर्णय समस्या एनपी-पूर्ण है, और इसलिए यह नहीं माना जाता है कि इसे हल करने के लिए कुशल एल्गोरिदम है।
- अधिकतम स्वतंत्र समुच्चय समस्या एनपी कठिन है और यह सन्निकटन एल्गोरिथम के लिए भी कठिन है।
इन ग्राफ़ में अधिकतम क्लिक्स और अधिकतम स्वतंत्र सेटों के बीच घनिष्ठ संबंध के अतिरिक्त, ग्राफ़ के विशेष वर्गों तक सीमित होने पर स्वतंत्र समुच्चय और क्लिक की समस्याएं बहुत भिन्न हो सकती हैं। उदाहरण के लिए, सघन ग्राफ़ के लिए (ऐसे ग्राफ़ जिनमें किनारों की संख्या किसी भी सबग्राफ़ में वर्टिकल की संख्या से अधिक स्थिर होती है), इस प्रकार अधिकतम क्लिक का आकार बंधा रहता है और बिल्कुल रैखिक समय में पाया जा सकता है;[7] चूंकि, ग्राफ़ के समान वर्गों के लिए, या यहाँ तक कि सीमाबद्ध डिग्री ग्राफ़ के अधिक प्रतिबंधित वर्ग के लिए, अधिकतम स्वतंत्र समुच्चय की जाँच SNP के कारण जटिलता से होती है। MAXSNP-पूर्ण, जिसका अर्थ है कि, कुछ स्थिर c (डिग्री के आधार पर) के लिए यह इष्टतम के सी के कारक के भीतर आने वाले अनुमानित समाधान को खोजने के लिए एनपी-कठिन है।[8]
सटीक एल्गोरिदम
अधिकतम स्वतंत्र समुच्चय समस्या एनपी-हार्ड है। चूंकि, इसे O2(n)2n की तुलना में अधिक कुशलता से हल किया जा सकता है ) समय जो भोली-भाली खोज द्वारा दिया जाएगा जो प्रत्येक शीर्ष उपसमुच्चय की जांच करता है और जांचता है कि क्या यह स्वतंत्र समुच्चय है।
2017 तक इसे On (1.1996.1) समय में हल किया जा सकता है) बहुपद स्थान का उपयोग करके किया जाता हैं।[9] यहाँ पर अधिकतम डिग्री 3n वाले ग्राफ़ तक सीमित होने पर, इसे O(1.0836.0) समय में हल किया जा सकता है)।[10]
ग्राफ़ के कई वर्गों के लिए, बहुपद समय में अधिकतम भार स्वतंत्र समुच्चय पाया जा सकता है। प्रसिद्ध उदाहरण पंजा-मुक्त रेखांकन करते हैं,[11] इस प्रकार P5- मुक्त रेखांकन[12] और सही रेखांकन।[13] कॉर्डल ग्राफ के लिए, रैखिक समय में अधिकतम भार स्वतंत्र समुच्चय पाया जा सकता है।[14]
अधिकतम वजन स्वतंत्र समुच्चय समस्या को हल करने के लिए मॉड्यूलर अपघटन अच्छा उपकरण है; कोग्राफ पर लीनियर टाइम एल्गोरिद्म इसका मूल उदाहरण है। अन्य महत्वपूर्ण उपकरण क्लिक विभाजक हैं जैसा कि टारजन द्वारा वर्णित है।[15]
कोनिग की प्रमेय (ग्राफ सिद्धांत) या कोनिग की प्रमेय का अर्थ है कि द्विदलीय ग्राफ में द्विदलीय मिलान एल्गोरिदम का उपयोग करके बहुपद समय में अधिकतम स्वतंत्र समुच्चय पाया जा सकता है।
सन्निकटन एल्गोरिदम
सामान्यतः अधिकतम स्वतंत्र समुच्चय समस्या को बहुपद समय में स्थिर कारक के रूप में अनुमानित नहीं किया जा सकता है (जब तक कि P = np)। वास्तव में, सामान्य रूप से अधिकतम स्वतंत्र समुच्चय एपीएक्स संबंधित जटिलता वर्ग है। पॉली-एपीएक्स-पूर्ण, जिसका अर्थ है कि यह किसी भी समस्या के रूप में कठिन है जिसे बहुपद कारक के रूप में अनुमानित किया जा सकता है।[16] चूंकि, प्रतिबंधित वर्गों के रेखांकन के लिए कुशल सन्निकटन एल्गोरिदम हैं।
प्लेनर ग्राफ में
प्लानर ग्राफ़ में, अधिकतम स्वतंत्र समुच्चय को बहुपद समय में किसी भी सन्निकटन अनुपात c < 1 के भीतर अनुमानित किया जा सकता है, माइनर (ग्राफ सिद्धांत) लेने के अनुसार बंद किए गए ग्राफ़ के किसी भी समूह में समान बहुपद-समय सन्निकटन योजनाएं सम्मिलित हैं।[17]
बाउंडेड डिग्री ग्राफ़ में
बाउंडेड डिग्री ग्राफ़ में, प्रभावी सन्निकटन एल्गोरिदम को सन्निकटन अनुपात के साथ जाना जाता है जो अधिकतम डिग्री के निश्चित मान के लिए स्थिर होते हैं; उदाहरण के लिए, लालची एल्गोरिद्म जो अधिकतम स्वतंत्र समुच्चय बनाता है, प्रत्येक चरण पर, ग्राफ़ में न्यूनतम डिग्री वर्टेक्स चुनकर और उसके समीपस्थ मानों को हटाकर, अधिकतम Δ डिग्री वाले ग्राफ़ पर (Δ+2)/3 का अनुमानित अनुपात प्राप्त करता है।[18] ऐसे उदाहरणों के लिए सन्निकटन कठोरता सीमा में सिद्ध हुई थी। इस प्रकार बरमानी & करपिंसकी (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] सभी अधिकतम स्वतंत्र समुच्चय समय ओ (3n/3) में पाए जा सकते हैं) = ओ (1.4423n).
अनुप्रयोग
अधिकतम स्वतंत्र समुच्चय और इसके पूरक, वर्टेक्स कवर समस्या, कई सैद्धांतिक समस्याओं के कम्प्यूटेशनल जटिलता सिद्धांत को सिद्ध करने में सम्मिलित है।[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.
