प्रभावी समुच्चय

एक ही ग्राफ के तीन प्रभावशाली समुच्चय (लाल रंग में)। इस ग्राफ की वर्चस्व संख्या 2 है: (बी) और (सी) से पता चलता है कि 2 शीर्षों के साथ प्रभावशाली समुच्चय है, और केवल 1 शीर्ष के साथ कोई प्रधान समुच्चय नहीं है।

ग्राफ सिद्धांत में, ग्राफ के लिए प्रभावी समुच्चय (असतत गणित) G का उपसमुच्चय है, इस प्रकार इसके शीर्ष 1=D के लिए कोई भी शीर्ष G या D के अंदर है या तो उसका कोई निकटतम अंश D है, इस प्रकार प्रभुत्व संख्या γ(G) में सबसे छोटे प्रभुत्व वाले समुच्चय में शीर्षों की संख्या G के बराबर होती हैं।

प्रधान समुच्चय समस्या परीक्षण की चिंता करती है कि क्या γ(G) ≤ K दिए गए ग्राफ के लिए G और इनपुट K पर निर्भर करती हैं, इस प्रकार कम्प्यूटरीकृत जटिलता सिद्धांत में यह मौलिक एनपी-पूर्ण निर्णय समस्या के रूप में देखा जाता है। इसलिए यह माना जाता है कि कोई बहुपद-समय एल्गोरिदम नहीं हो सकता है जो γ(G) की गणना कर सके इस प्रकार सभी रेखांकन के लिए G आवश्यक रहती हैं, चूंकि कुशल एल्गोरिदम हैं तथा साथ ही कुछ ग्राफ के वर्गों के लिए कुशल एल्गोरिदम भी उपयोग की जाती हैं।

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

औपचारिक परिभाषा

एक अप्रत्यक्ष ग्राफ दिया G = (V, E), शीर्षों का उपसमुच्चय $D\subseteq V$ प्रत्येक शीर्ष के लिए प्रभुत्वशाली समुच्चय कहा जाता है जहाँ $u\in V\setminus D$ शिखर है तथा $v\in D$ का मान $(u,v)\in E$ पर निर्भर करता हैं।

यहाँ प्रत्येक ग्राफ में कम से कम प्रभावशाली समुच्चय होते है: यदि $D=V=$ सभी शीर्षों का समुच्चय है, तो परिभाषा के अनुसार D प्रभावी समुच्चय है, क्योंकि कोई शीर्ष नहीं है $u\in V\setminus D$. और इस रूचिकर अनुभूति के लिए प्रधान समुच्च्यों को प्राप्त किया जाता है। जिसका प्रभुत्व संख्या $\gamma (G):=\min\{|D|:D{\text{ is a dominating set of }}G\}$ द्वारा परिभाषित किया जाता है।

वेरिएंट

एक संयोजित प्रधान समुच्चय ऐसा प्रधान समुच्चय है जो संयोजित रहता है। यदि S जुड़ा हुआ वर्चस्व समुच्चय है, तो कोई G का फैले हुए पेड़ का निर्माण कर सकता है जिसमें S पेड़ के गैर-पत्ती के शीर्ष का समुच्चय बनाता है, इसके विपरीत यदि T दो से अधिक शीर्षों वाले ग्राफ़ में कोई भी फैला हुआ पेड़ है, तो T के शीर्ष से जुड़े हुए प्रभावी समुच्चय का निर्माण करते हैं। इसलिए, न्यूनतम जुड़े हुए वर्चस्व वाले समुच्च्यों को खोजना पत्तियों की अधिकतम संभव संख्या वाले फैले हुए पेड़ों को खोजने के बराबर है।

टोटल डोमिनेटिंग समुच्चय (या स्ट्रॉन्गली-डोमिनेटिंग समुच्चय) उर्ध्वाधर का समुच्चय है, जैसे कि ग्राफ में सभी उर्ध्वाधर, सहित डोमिनेटिंग समुच्चय में उर्ध्वाधर, डोमिनेटिंग समुच्चय में समीप है। प्रत्येक शीर्ष के लिए $u\in V$, $v\in D$ शिखर है, ऐसा है कि $(u,v)\in E$. उपरोक्त चित्र (c) प्रधान समुच्चय दिखाता है जो जुड़ा हुआ प्रधान समुच्चय और कुल प्रधान समुच्चय है, इन आंकड़ों के आधार पर (a) और (b) में कोई उदाहरण नहीं हैं। साधारण प्रधान समुच्चय के विपरीत, कुल प्रधान समुच्चय सम्मिलित नहीं हो सकते हैं। उदाहरण के लिए इसके अधिक शीर्षों और बिना किनारों वाले ग्राफ़ में कुल प्रभावी समुच्चय नहीं होते हैं। इसका शक्तिशाली वर्चस्व संख्या G द्वारा परिभाषित किया जाता है जो इस प्रकार हैं: $\gamma ^{strong}(G):=\min\{|D|:D{\text{ is a strongly-dominating set of }}G\}$, इस प्रकार इसे $\gamma ^{strong}(G)\geq \gamma (G)$ द्वारा प्रकट किया जाता हैं।

एक प्रधान एज-समुच्चय किनारों (शीर्ष जोड़े) का समुच्चय है जिसका संघ प्रभावशाली समुच्चय है, इस प्रकार के समुच्चय सम्मिलित नहीं हो सकते है (उदाहरण के लिए, ग्राफ जिसमें या अधिक कोने हैं और कोई किनारा नहीं है)। यदि यह अस्तित्व में है, तो इसके सभी किनारों का संयोजिन अत्यधिक प्रभावशाली समुच्चय पर आधारित होते हैं। इसलिए एज-डोमिनेटिंग समुच्चय का सबसे छोटा आकार $\gamma ^{strong}(G)/2$ कम से कम है।

इसके विपरीत, एज डोमिनेटिंग समुच्चय या एज-डोमिनेटिंग समुच्चय किनारों का समुच्चय d है, जैसे कि d में नहीं हर किनारा d में कम से कम किनारे से संयोजित रहता है, ऐसा समुच्चय सदैव सम्मिलित होता है (उदाहरण के लिए, सभी किनारों का समुच्चय एज-डोमिनेटिंग समुच्चय होता है)।

एक k-डोमिनेटिंग समुच्चय उर्ध्वाधर का समुच्चय है जैसे कि समुच्चय में सम्मिलित प्रत्येक वर्टेक्स में समुच्चय में कम से कम k पड़ोसी होते हैं (एक मानक डोमिनेटिंग समुच्चय 1-डोमिनेटिंग समुच्चय होता है)। इसी प्रकार k-टपल डोमिनेटिंग समुच्चय उर्ध्वाधर का समुच्चय है जैसे कि ग्राफ में प्रत्येक वर्टेक्स में समुच्चय में कम से कम k पड़ोसी होते हैं (कुल डोमिनेटिंग समुच्चय 1-ट्यूपल डोमिनेटिंग समुच्चय होता है)। इस प्रकार (1 + log n)-बहुपद समय में न्यूनतम k-टपल प्रधान समुच्चय का सन्निकटन पाया जा सकता है। प्रत्येक ग्राफ k-प्रभुत्व समुच्चय को स्वीकार करता है (उदाहरण के लिए, सभी शीर्षों का समुच्चय) परन्तु न्यूनतम डिग्री वाले रेखांकन k − 1 k-टपल प्रधान समुच्चय को स्वीकार करते हैं। चूंकि ग्राफ k-टपल प्रधान समुच्चय को स्वीकार करता हो, न्यूनतम k-टपल प्रधान समुच्चय समान ग्राफ़ के लिए न्यूनतम k- प्रधान समुच्चय से लगभग k गुना बड़ा हो सकता है; (1.7 + log Δ)-न्यूनतम k-प्रभुत्व वाले समुच्चय का बहुपद समय में भी पाया जा सकता है।

एक 'स्टार-डोमिनेटिंग समुच्चय' V का उपसमुच्चय है, जैसे कि V में प्रत्येक शीर्ष v के लिए, v का स्टार (ग्राफ़ सिद्धांत) (v से संयोजित किनारों का समुच्चय हैं) D में किसी शीर्ष के तारे को काटता है। स्पष्ट रूप से, यदि G के पास अलग-थलग शीर्ष है तो इसका कोई स्टार वर्चस्व वाला समुच्चय नहीं है, चूंकि अलग-अलग शीर्षों पर स्टार का मान रिक्त होता है। यदि G का कोई पृथक शीर्ष नहीं है, तो प्रत्येक प्रभावी समुच्चय स्टार-प्रभुत्व समुच्चय है और इसके विपरीत स्टार-वर्चस्व और सामान्य वर्चस्व के बीच का अंतर तब अधिक महत्वपूर्ण होता है जब उनके भिन्नात्मक रूपों पर विचार किया जाता है।

डोमैटिक विभाजन उर्ध्वाधर का विभाजन है जो अलग-अलग वर्चस्व वाले समुच्च्यों में होता है। डोमैटिक संख्या डोमेटिक विभाजन का अधिकतम आकार है।

एक शाश्वत प्रधान समुच्चय वर्चस्व का गतिशील संस्करण है जिसमें प्रधान समुच्चय डी में शीर्ष वी को चुना जाता है और समीपस्थ यू (यू में नहीं है) के साथ परिवर्तित कर दिया जाता है। D) ऐसा है कि संशोधित D भी प्रभावशाली समुच्चय है और इस प्रक्रिया को कोने के विकल्पों v के किसी भी अनंत अनुक्रम पर दोहराया जा सकता है।

प्रधान और स्वतंत्र समुच्चय

डोमिनेटिंग समुच्चय स्वतंत्र समुच्चय (ग्राफ थ्योरी) से निकटता से संबंधित हैं: स्वतंत्र समुच्चय भी प्रधान समुच्चय है यदि और केवल यदि यह अधिकतम स्वतंत्र समुच्चय है, तो ग्राफ में कोई भी अधिकतम स्वतंत्र समुच्चय आवश्यक रूप से न्यूनतम प्रधान समुच्चय भी है।

स्वतंत्र समुच्च्यों द्वारा प्रभुत्व

प्रभावशाली समुच्चय स्वतंत्र समुच्चय हो भी सकते है और नहीं भी हो सकते हैं। उदाहरण के लिए, उपरोक्त आंकड़े (a) और (b) स्वतंत्र प्रभावशाली समुच्चय दिखाते हैं, जबकि आंकड़ा (m) प्रभावशाली समुच्चय दिखाता है जो स्वतंत्र समुच्चय नहीं है।

'स्वतंत्र प्रभुत्व संख्या' i(G) ग्राफ का G सबसे छोटे प्रधान होने वाले समुच्चय का आकार है जो स्वतंत्र समुच्चय है। समतुल्य रूप से, यह सबसे छोटे अधिकतम स्वतंत्र समुच्चय का आकार है। न्यूनतम में i(G) कम तत्वों पर लिया जाता है (केवल स्वतंत्र समुच्चय माने जाते हैं), इसलिए γ(G) ≤ i(G) सभी रेखांकन के लिए G द्वारा प्रकट किया जाता हैं।

असमानता सख्त हो सकती है - रेखांकन G हैं, जिसके लिए γ(G) < i(G) को उदाहरण के लिए G डबल स्टार ग्राफ द्वारा बनाकर प्रकट किया जाता हैं, जिसमें उर्ध्वाधर मान इस प्रकार हैं- $x_{1},\ldots ,x_{p},a,b,y_{1},\ldots ,y_{q}$, जहाँ p, q > 1 के किनारे G को इस प्रकार परिभाषित किया गया है: प्रत्येक x_i लगी हुई है a, a लगी हुई है b, और b प्रत्येक के निकट है y_j. तब γ(G) = 2 तब से {a, b} सबसे छोटा प्रभावशाली समुच्चय है। यदि p ≤ q, तब i(G) = p + 1 तब से $\{x_{1},\ldots ,x_{p},b\}$ सबसे छोटा प्रभावी समुच्चय है जो स्वतंत्र भी है और यह सबसे छोटा तथा अधिकांशतः स्वतंत्र समुच्चय है।

ऐसे ग्राफ समूह हैं जिनमें γ(G) = i(G), अर्ताथ हर न्यूनतम अधिकतम स्वतंत्र समुच्चय न्यूनतम प्रधान समुच्चय है। उदाहरण के लिए, γ(G) = i(G) यदि G पंजा मुक्त ग्राफ है।

एक ग्राफ G को वर्चस्व-पूर्ण ग्राफ़ कहा जाता है, यदि γ(H) = i(H) हर प्रेरित सबग्राफ में H का G का रूप हैं। चूंकि यहाँ पर क्लॉ-फ्री ग्राफ का प्रेरित सबग्राफ क्लॉ-फ्री है, इसलिए यह इस प्रकार है कि प्रत्येक क्लॉ-फ्री ग्राफ भी वर्चस्व-परिपूर्ण है।

किसी भी ग्राफ के लिए G, इसका लाइन ग्राफ L(G) मुक्त रहता है, और इसलिए न्यूनतम अधिकतम स्वतंत्र समुच्चय L(G) है इस प्रकार न्यूनतम प्रधान समुच्चय L(G) है। इसमें स्वतंत्र समुच्चय L(G) में मिलान (ग्राफ सिद्धांत) G से मेल खाता है, और प्रधान समुच्चय में L(G) किनारे पर प्रधान समुच्चय G से मेल खाता है। इसलिए न्यूनतम अधिकतम मिलान का आकार न्यूनतम किनारे पर प्रधान होने वाले समुच्चय के समान होता है।

स्वतंत्र समुच्च्यों का वर्चस्व

'स्वतंत्रता प्रभुत्व संख्या' iγ(G) ग्राफ का G सभी स्वतंत्र समुच्च्यों में अधिकतम है यहाँ पर A का G, प्रधान होने वाले सबसे छोटे समुच्चय का मान A द्वारा प्रकट करता हैं। उर्ध्वाधर के उपसमुच्चय पर प्रधान होने के लिए सभी उर्ध्वाधर पर प्रधान होने की तुलना में संभावित रूप से कम उर्ध्वाधर की आवश्यकता होती है, इसलिए iγ(G) ≤ γ(G) सभी रेखांकन G के लिए उपयोग किया जाता हैं।

असमानता सख्त हो सकती है - रेखांकन G हैं, जिसके लिए iγ(G) < γ(G) के रूप में प्रकट होता हैं। उदाहरण के लिए, कुछ पूर्णांक के लिए n, होने देना G ऐसा ग्राफ़ हो जिसमें कोने a की पंक्तियाँ और स्तंभ हों n-द्वारा-n बोर्ड और ऐसे दो शीर्ष जुड़े हुए हैं यदि और केवल यदि वे प्रतिच्छेद करते हैं। केवल स्वतंत्र समुच्चय केवल पंक्तियों या केवल स्तंभों के समुच्चय होते हैं, और उनमें से प्रत्येक पर एकल शीर्ष (एक स्तंभ या पंक्ति) का प्रभुत्व हो सकता है, इसलिए iγ(G) = 1 चूंकि, सभी शीर्षों पर प्रधान होने के लिए हमें कम से कम पंक्ति और स्तंभ की आवश्यकता होती है, इसलिए γ(G) = 2. इसके अतिरिक्त, के बीच का अनुपात γ(G) / iγ(G) मनमाने ढंग से बड़ा हो सकता है। उदाहरण के लिए, यदि के शिखर G a के वर्गों के सभी उपसमुच्चय हैं n-द्वारा-n बोर्ड, फिर भी iγ(G) = 1, किन्तु γ(G) = n पर निर्भर हैं।

द्वि-स्वतंत्र वर्चस्व संख्या iγi(G) ग्राफ का G सभी स्वतंत्र समुच्च्यों में अधिकतम है A का G, सबसे छोटे स्वतंत्र समुच्चय का प्रभुत्व A. निम्नलिखित G के लिए संबंधित किसी भी ग्राफ के लिए मान्य हैं:

$$\begin{array}{rl}i(G)& \ge <!--\; \ge \; -->\mathrm{\gamma <!--\; \gamma \; -->}(G)\ge <!--\; \ge \; -->i\mathrm{\gamma <!--\; \gamma \; -->}(G)\\ i(G)& \ge <!--\; \ge \; -->i\end{array}$$