स्वतंत्रता संकुल

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

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

समरूपता समूह

कई लेखकों ने एक ग्राफ जी = (वी, ई) के गुणों और इसके स्वतंत्रता परिसर I (जी) के होमोलॉजी समूहों के बीच संबंधों का अध्ययन किया। विशेष रूप से, जी में हावी सेट से संबंधित कई गुण गारंटी देते हैं कि आई (जी) के कुछ कम होमोलॉजी समूह तुच्छ हैं।

1. जी की कुल वर्चस्व संख्या, निरूपित $\gamma _{0}(G)$, G - एक सेट S के कुल प्रभुत्व वाले सेट की न्यूनतम कार्डिनैलिटी है, जैसे कि V का प्रत्येक शीर्ष S के शीर्ष के निकट है। यदि $\gamma _{0}(G)>k$ तब ${\tilde {H}}_{k-1}(I(G))=0$. 2. G में V के उपसमुच्चय A की कुल वर्चस्व संख्या, निरूपित $\gamma _{0}(G,A)$, एक सेट S की न्यूनतम कार्डिनैलिटी है जैसे कि A का प्रत्येक शीर्ष S के शीर्ष के समीप है। G की स्वतंत्रता प्रभुत्व संख्या, निरूपित $i\gamma (G)$, G में सभी स्वतंत्र समुच्चयों A का अधिकतम है $\gamma _{0}(G,A)$. अगर $i\gamma (G)>k$, तब ${\tilde {H}}_{k-1}(I(G))=0$. 3. जी की वर्चस्व संख्या, निरूपित $\gamma (G)$, G के एक प्रभावशाली सेट की न्यूनतम कार्डिनैलिटी है - एक सेट S ऐसा कि V \ S का प्रत्येक शीर्ष S के एक शीर्ष के निकट है। ध्यान दें कि $\gamma _{0}(G)\geq \gamma (G)$. अगर G एक कॉर्डल ग्राफ है और $\gamma (G)>k$ तब ${\tilde {H}}_{k-1}(I(G))=0$. 4. जी की प्रेरित मिलान संख्या, निरूपित $\mu (G)$, जी में एक प्रेरित मिलान की सबसे बड़ी कार्डिनैलिटी है - एक मिलान जिसमें सबसेट में किसी भी दो कोने को जोड़ने वाला हर किनारा शामिल है। यदि V का एक उपसमुच्चय A मौजूद है जैसे कि $\gamma _{0}(G,A)>k+\min[k,\mu (G[A])]$ तब ${\tilde {H}}_{k-1}(I(G))=0$. यह उपरोक्त 1 और 2 दोनों गुणों का सामान्यीकरण है।

5. G का गैर-प्रभुत्व स्वतंत्रता परिसर, जिसे I'(G) के रूप में दर्शाया गया है, स्वतंत्र सेटों का सार सरल जटिल है जो G के प्रभावी सेट नहीं हैं। जाहिर है I'(G) I(G) में निहित है; द्वारा समावेशन मानचित्र को निरूपित करें $i:I'(G)\to I(G)$. यदि G एक तारकीय ग्राफ है तो प्रेरित मानचित्र $i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))$ सभी के लिए शून्य है $k\geq -1$. यह उपरोक्त संपत्ति 3 का सामान्यीकरण है।

6. G का भिन्नात्मक तारा-वर्चस्व संख्या, निरूपित $\gamma _{s}^{*}(G)$, जी में एक भिन्नात्मक स्टार-वर्चस्व वाले सेट का न्यूनतम आकार है। यदि $\gamma _{s}^{*}(G)>k$ तब ${\tilde {H}}_{k-1}(I(G))=0$.

संबंधित अवधारणाएँ

मेशुलम का खेल एक ग्राफ 'जी' पर खेला जाने वाला खेल है, जिसका उपयोग 'जी' के स्वतंत्रता परिसर की होमोलॉजिकल कनेक्टिविटी पर निचली सीमा की गणना के लिए किया जा सकता है।

एक ग्राफ G का मैचिंग कॉम्प्लेक्स, जिसे M(G) के रूप में दर्शाया गया है, G में मिलान (ग्राफ सिद्धांत) का एब्स्ट्रैक्ट सिम्प्लिकल कॉम्प्लेक्स है। यह 'जी' के लाइन ग्राफ का इंडिपेंडेंस कॉम्प्लेक्स है। (एम,एन)-चेसबोर्ड कॉम्प्लेक्स पूर्ण द्विदलीय ग्राफ के' पर मैचिंग कॉम्प्लेक्स है_m,_n. यह एक एम-बाय-एन शतरंजबोर्ड पर पदों के सभी सेटों का सार सरल जटिल है, जिस पर उनमें से प्रत्येक को धमकी दिए बिना रूक (शतरंज) डालना संभव है। G का क्लिक कॉम्प्लेक्स G के पूरक ग्राफ का इंडिपेंडेंस कॉम्प्लेक्स है।

यह भी देखें

• इंद्रधनुष-स्वतंत्र सेट