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

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

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

समरूपता समूह

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

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

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

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

एक लेखाचित्र G का मिलान संकुल, जिसे M(G) के रूप में दर्शाया गया है, G में मिलान (लेखाचित्र सिद्धांत) का संक्षेप प्रतिसमुच्‍चीय संकुल है। यह 'G' के रेखा लेखाचित्र का स्वतंत्रता संकुल है।

(m,n)-बिसात संकुल पूर्ण द्विदलीय लेखाचित्र K_m,_n. पर मिलान संकुल है यह एक m-से-n बिसात पर पदों के सभी सम्मुच्चयों का सार सरल जटिल है, जिस पर उनमें से प्रत्येक के बिना दूसरे को धमकी दिए बिना हाथी (शतरंज) को रखना संभव है।

G का गुट संकुल G के पूरक लेखाचित्र का स्वतंत्रता संकुल है।

यह भी देखें

• इंद्रधनुष-स्वतंत्र सम्मुच्चय