Dense subgraph
ग्राफ सिद्धांत और कंप्यूटर विज्ञान में, एक घना उपग्राफ प्रति शीर्ष कई किनारों वाला एक उपग्राफ है। इसे इस प्रकार औपचारिक रूप दिया गया हैः मान लीजिए कि यह एक दिशाहीन ग्राफ है और इसका एक उप-ग्राफ है। फिर के घनत्व को इस प्रकार परिभाषित किया गया हैः सबसे घनी उपग्राफ समस्या अधिकतम घनत्व के उपग्राफ को खोजने की है। ग्राफ के अधिकतम घने उपग्राफ के घनत्व को कभी-कभी इसके उपग्राफ घनत्व के रूप में संदर्भित किया जाता है। 1984 में, एंड्रयू वी. गोल्डबर्ग ने एक अधिकतम प्रवाह तकनीक का उपयोग करके अधिकतम घनत्व उपग्राफ खोजने के लिए एक बहुपद समय एल्गोरिथ्म विकसित किया। 1989 में गैलो, ग्रिगोरियाडिस और टार्जन द्वारा समय पर चलने के लिए इसमें सुधार किया गया है। 2000 में चारीकर द्वारा इष्टतम समाधान खोजने के लिए एक सरल एल. पी. दी गई थी। सबग्राफ घनत्व आर्बरिसिटी और ग्राफ अपक्षय की संबंधित धारणा के लिए एसिम्प्टोटिक है। सघनतम उपग्राफ सबसे सघनतम उपग्राफ समस्या पर कई भिन्नताएँ हैं। उनमें से एक सबसे घनी सबग्राफ समस्या है, जहाँ उद्देश्य सटीक शीर्षों पर अधिकतम घनत्व सबग्राफ का पता लगाना है। यह समस्या गुट समस्या को सामान्य बनाती है और इस प्रकार सामान्य ग्राफ में एन. पी.-कठोर होती है। एक बहुपद एल्गोरिथ्म मौजूद है जो प्रत्येक के लिए के अनुपात के भीतर सबसे घने उपग्राफ का अनुमान लगाता है, जबकि यह बहुपद समय में एक-सन्निकटन को स्वीकार नहीं करता है जब तक कि घातीय समय परिकल्पना गलत न हो। एक कमजोर धारणा के तहत कि समस्या के लिए कोई पी. टी. ए. एस. मौजूद नहीं है। द्विदलीय ग्राफ और कॉर्डल ग्राफ में समस्या एनपी-हार्ड बनी हुई है लेकिन पेड़ों और विभाजित ग्राफ के लिए बहुपद है। यह खुला है कि क्या समस्या (उचित) अंतराल ग्राफ और समतल ग्राफ में एन. पी.-कठोर या बहुपद है; हालाँकि, समस्या की एक भिन्नता जिसमें उपग्राफ को जोड़ने की आवश्यकता होती है, समतल ग्राफ में एन. पी.-कठोर होती है। सबसे अधिक उपग्राफ पर सबसे घना सबसे अधिक समस्या का उद्देश्य अधिकांश शीर्षों पर अधिकतम घनत्व उपग्राफ का पता लगाना है। एंडरसन और चेल्लापिल्ला ने दिखाया कि यदि इस समस्या के लिए एक-सन्निकटन मौजूद है तो इससे सबसे घनी उपग्राफ समस्या के लिए एक-सन्निकटन होगा। सबसे घनी कम से कम सबग्राफ कम से कम सबसे घनी समस्या को सबसे घनी सबग्राफ समस्या के समान परिभाषित किया जाता है। समस्या एन. पी.-पूर्ण है, लेकिन बहुपद समय में 2-सन्निकटन को स्वीकार करती है। इसके अलावा, कुछ प्रमाण हैं कि यह सन्निकटन एल्गोरिथ्म अनिवार्य रूप से सबसे अच्छा संभव हैः छोटे समूह विस्तार परिकल्पना (एक कम्प्यूटेशनल जटिलता धारणा जो अद्वितीय खेल अनुमान से निकटता से संबंधित है) को मानते हुए, तो प्रत्येक स्थिरांक के लिए कारक के भीतर समस्या का अनुमान लगाना एन. पी.-कठिन है। --------------------------------------------------------------------------------------------------------------------------------------------- - सघनतम उपग्राफ समस्या की इस भिन्नता का उद्देश्य प्रेरित गुटों की औसत संख्या को अधिकतम करना है, जहां-क्लिकों का सेट प्रेरित होता है। ध्यान दें कि सबसे घनी सबग्राफ समस्या एक विशेष मामले के रूप में प्राप्त की जाती है। यह सामान्यीकरण बड़े पैमाने पर वास्तविक दुनिया के नेटवर्क से बड़े निकट-क्लिक निकालने के लिए एक अनुभवजन्य रूप से सफल बहु-समय दृष्टिकोण प्रदान करता है। स्थानीय रूप से सबसे अधिक सघन उपग्राफ किन और अन्य। एक ग्राफ में टॉप-के स्थानीय रूप से सबसे घने उपग्राफ की खोज की समस्या पेश की गई, जिनमें से प्रत्येक ग्राफ में अपने स्थानीय क्षेत्र में उच्चतम घनत्व प्राप्त करता हैः यह न तो समान या बड़े घनत्व के साथ किसी भी सुपरग्राफ में निहित है, न ही इसमें घनत्व के साथ उपग्राफ शामिल हैं जो बाकी स्थानीय सबसे घने उपग्राफ के साथ शिथिल रूप से जुड़े हुए हैं। ध्यान दें कि सबसे घनी उपग्राफ समस्या एक विशेष मामले के रूप में प्राप्त की जाती है। ग्राफ में स्थानीय रूप से सबसे घने सबग्राफ के सेट की गणना बहुपद समय में की जा सकती है। संदर्भ आगे पढ़ें। .. .. .. .. ग्राफ सिद्धांत