स्वतंत्रता संकुल: Difference between revisions
From Vigyanwiki
(Created page with "ग्राफ़ (ग्राफ़ सिद्धांत) का स्वतंत्रता परिसर एक गणितीय वस्तु है जो...") |
(TEXT) |
||
| Line 1: | Line 1: | ||
लेखाचित्र (लेखाचित्र सिद्धांत) का स्वतंत्रता संकुल एक गणितीय वस्तु है जो लेखाचित्र के स्वतंत्र सम्मुच्चय (लेखाचित्र सिद्धांत) का वर्णन करता है। औपचारिक रूप से, एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष लेखाचित्र]] ''G'' का स्वतंत्रता संकुल, जिसे I(''G'') द्वारा निरूपित किया जाता है, एक [[सार सरल जटिल]] है (अर्थात, उपसमुच्चय लेने के संचालन के अंतर्गत परिमित सम्मुच्चय का एक वर्ग), गठित 'G' के [[स्वतंत्र सेट (ग्राफ सिद्धांत)|स्वतंत्र सम्मुच्चय (लेखाचित्र सिद्धांत)]] में लम्बवत के सम्मुच्चय द्वारा है। एक स्वतंत्र सम्मुच्चय का कोई भी उपसमुच्चय स्वयं एक स्वतंत्र सम्मुच्चय है, इसलिए I(''G'') वास्तव में उपसमुच्चय लेने के अंतर्गत बंद है। | |||
लेखाचित्र में प्रत्येक स्वतंत्र सम्मुच्चय अपने [[पूरक ग्राफ|पूरक लेखाचित्र]] में एक [[क्लिक (ग्राफ सिद्धांत)|गुट (लेखाचित्र सिद्धांत)]], और इसके विपरीत है। इसलिए, एक लेखाचित्र का स्वतंत्रता संकुल उसके पूरक लेखाचित्र के [[क्लिक कॉम्प्लेक्स|गुट संकुल]] के बराबर, और इसके विपरीत होता है। | |||
== [[समरूपता समूह]] == | == [[समरूपता समूह]] == | ||
कई लेखकों ने एक | कई लेखकों ने एक लेखाचित्र G = (V, I) के गुणों और इसके स्वतंत्रता संकुल I (G) के सजातीय समूहों के बीच संबंधों का अध्ययन किया।<ref name=":0">{{Cite journal|last=Meshulam|first=Roy|date=2003-05-01|title=वर्चस्व संख्या और समरूपता|journal=Journal of Combinatorial Theory, Series A|language=en|volume=102|issue=2|pages=321–330|doi=10.1016/S0097-3165(03)00045-1|issn=0097-3165|doi-access=free}}</ref> विशेष रूप से, G में [[हावी सेट|हावी सम्मुच्चय]] से संबंधित कई गुण प्रत्याभुति देते हैं कि I (G) के कुछ कम सजातीय समूह तुच्छ हैं। | ||
1. | 1. G की कुल वर्चस्व संख्या, निरूपित <math>\gamma_0(G)</math>, G - एक सम्मुच्चय S के कुल प्रभुत्व वाले सम्मुच्चय की न्यूनतम गणनांक है, जैसे कि V का प्रत्येक शीर्ष S के शीर्ष के निकट है। यदि <math>\gamma_0(G)>k</math> तब <math>\tilde{H}_{k-1}(I(G))=0</math> है। <ref>{{Cite book|last=Chudnovsky|first=Maria|title=विसंधित प्रतिनिधियों की प्रणाली (M.Sc. थीसिस)|publisher=Technion, department of mathematics|year=2000|location=Haifa, Israel}}</ref> | ||
2. G में V के उपसमुच्चय A की कुल वर्चस्व संख्या, निरूपित <math>\gamma_0(G,A)</math>, एक सम्मुच्चय S की न्यूनतम गणनांक है जैसे कि A का प्रत्येक शीर्ष S के शीर्ष के समीप है। G की स्वतंत्रता प्रभुत्व संख्या, निरूपित <math>i \gamma(G)</math>, G में सभी स्वतंत्र समुच्चयों A का अधिकतम <math>\gamma_0(G,A)</math> है। अगर <math>i \gamma(G) > k</math>, तब <math>\tilde{H}_{k-1}(I(G))=0</math> है। <ref name=":0" /><ref>{{Cite journal|last1=Aharoni|first1=Ron|last2=Haxell|first2=Penny|date=2000|title=हाइपरग्राफ के लिए हॉल की प्रमेय|journal=Journal of Graph Theory|volume=35|issue=2|pages=83–88|doi=10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v|issn=0364-9024}}</ref> | |||
6. G का भिन्नात्मक | 3. G की वर्चस्व संख्या, निरूपित <math>\gamma(G)</math>, G के एक प्रभावशाली सम्मुच्चय की न्यूनतम गणनांक है - एक सम्मुच्चय S ऐसा कि V \ S का प्रत्येक शीर्ष S के एक शीर्ष के निकट है। ध्यान दें कि <math> \gamma_0(G)\geq \gamma(G) </math>। अगर G एक [[कॉर्डल ग्राफ|पृष्ठरज्जु लेखाचित्र]] है और <math>\gamma(G)>k</math> तब <math>\tilde{H}_{k-1}(I(G))=0</math> है। <ref>{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Ziv|first3=Ran|date=2002-07-01|title=A Tree Version of Kőnig's Theorem|journal=Combinatorica|volume=22|issue=3|pages=335–343|doi=10.1007/s004930200016|s2cid=38277360|issn=0209-9683}}</ref> | ||
4. G की प्रेरित मिलान संख्या, निरूपित <math>\mu(G)</math>, G में एक [[प्रेरित मिलान]] की सबसे बड़ी गणनांक है - एक मिलान जिसमें उपसमुच्चय में किसी भी दो कोने को जोड़ने वाला हर किनारा सम्मिलित है। यदि V का एक उपसमुच्चय A उपस्थित है जैसे कि <math>\gamma_0(G,A)>k+\min[k, \mu(G[A])]</math> तब <math>\tilde{H}_{k-1}(I(G))=0</math> है। <ref name=":3">{{Cite journal|last=Meshulam|first=Roy|date=2001-01-01|title=क्लिक कॉम्प्लेक्स और हाइपरग्राफ मिलान|journal=Combinatorica|language=en|volume=21|issue=1|pages=89–94|doi=10.1007/s004930170006|s2cid=207006642|issn=1439-6912}}</ref> यह उपरोक्त 1 और 2 दोनों गुणों का सामान्यीकरण है। | |||
5. G का गैर-प्रभुत्व स्वतंत्रता संकुल, जिसे I'(G) के रूप में दर्शाया गया है, स्वतंत्र सम्मुच्चयों का सार सरल जटिल है जो G के प्रभावी सम्मुच्चय नहीं हैं। स्पष्ट रुप से I'(G) I(G) में निहित है; <math>i: I'(G)\to I(G)</math> द्वारा समावेशन मानचित्र को निरूपित करें। यदि G एक तारकीय लेखाचित्र है तो प्रेरित मानचित्र <math>i_*: \tilde{H}_k(I'(G))\to \tilde{H}_k(I(G))</math> सभी <math>k\geq -1</math> के लिए शून्य है। <ref name=":0" />{{Rp|Thm.1.4}} यह उपरोक्त संपत्ति 3 का सामान्यीकरण है। | |||
6. G का भिन्नात्मक तारक-प्राबल्य संख्या, निरूपित <math>\gamma^*_s(G)</math>, G में एक भिन्नात्मक तारक-बाध्यकारी वाले सम्मुच्चय का न्यूनतम आकार है। यदि <math>\gamma^*_s(G)>k</math> तब <math>\tilde{H}_{k-1}(I(G))=0</math> है। <ref name=":0" />{{Rp|Thm.1.5}} | |||
== संबंधित अवधारणाएँ == | == संबंधित अवधारणाएँ == | ||
मेशुलम का खेल एक | मेशुलम का खेल एक लेखाचित्र 'G' पर खेला जाने वाला खेल है, जिसका उपयोग 'G' के स्वतंत्रता संकुल की [[होमोलॉजिकल कनेक्टिविटी|समजाततः अनुयोजकता]] पर निचली सीमा की गणना के लिए किया जा सकता है। | ||
एक लेखाचित्र ''G'' का मिलान संकुल, जिसे M(''G'') के रूप में दर्शाया गया है, ''G'' में [[ मिलान (ग्राफ सिद्धांत) |मिलान (लेखाचित्र सिद्धांत)]] का संक्षेप प्रतिसमुच्चीय संकुल है। यह 'G' के [[लाइन ग्राफ|रेखा लेखाचित्र]] का स्वतंत्रता संकुल है।<ref>{{Cite journal|last1=Björner|first1=A.|last2=Lovász|first2=L.|last3=Vrećica|first3=S. T.|last4=Živaljević|first4=R. T.|date=1994|title=चेसबोर्ड कॉम्प्लेक्स और मैचिंग कॉम्प्लेक्स|journal=Journal of the London Mathematical Society|language=en|volume=49|issue=1|pages=25–39|doi=10.1112/jlms/49.1.25|issn=1469-7750}}</ref><ref>{{Cite journal|last1=Reiner|first1=Victor|last2=Roberts|first2=Joel|date=2000-03-01|title=न्यूनतम संकल्प और मिलान और शतरंज परिसरों की समरूपता|journal=Journal of Algebraic Combinatorics|language=en|volume=11|issue=2|pages=135–154|doi=10.1023/A:1008728115910|issn=1572-9192|doi-access=free}}</ref> | |||
(''m'',n)-बिसात संकुल पूर्ण द्विदलीय लेखाचित्र ''K<sub>m</sub>,<sub>n</sub>. पर मिलान संकुल है यह एक m-से-n बिसात पर पदों के सभी सम्मुच्चयों का सार सरल जटिल है, जिस पर उनमें से प्रत्येक के बिना दूसरे को धमकी दिए बिना [[रूक (शतरंज)|हाथी (शतरंज)]] को रखना संभव है।<ref>{{Cite journal|last1=Friedman|first1=Joel|last2=Hanlon|first2=Phil|date=1998-09-01|title=शतरंज की बिसात के बेट्टी नंबरों पर|journal=Journal of Algebraic Combinatorics|language=en|volume=8|issue=2|pages=193–203|doi=10.1023/A:1008693929682|issn=1572-9192|doi-access=free}}</ref><ref>{{Cite journal|last=Ziegler|first=Günter M.|authorlink=Günter M. Ziegler|date=1994-02-01|title=शतरंज की बिसात परिसरों की शेलबिलिटी|journal=[[Israel Journal of Mathematics]]|language=en|volume=87|issue=1|pages=97–110|doi=10.1007/BF02772986|doi-access=free|s2cid=59040033|issn=1565-8511}}</ref>'' | |||
G का गुट संकुल ''G'' के पूरक लेखाचित्र का स्वतंत्रता संकुल है। | |||
G का | |||
== यह भी देखें == | == यह भी देखें == | ||
* [[इंद्रधनुष-स्वतंत्र सेट]] | * [[इंद्रधनुष-स्वतंत्र सेट|इंद्रधनुष-स्वतंत्र सम्मुच्चय]] | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 09:41, 15 May 2023
लेखाचित्र (लेखाचित्र सिद्धांत) का स्वतंत्रता संकुल एक गणितीय वस्तु है जो लेखाचित्र के स्वतंत्र सम्मुच्चय (लेखाचित्र सिद्धांत) का वर्णन करता है। औपचारिक रूप से, एक अप्रत्यक्ष लेखाचित्र G का स्वतंत्रता संकुल, जिसे I(G) द्वारा निरूपित किया जाता है, एक सार सरल जटिल है (अर्थात, उपसमुच्चय लेने के संचालन के अंतर्गत परिमित सम्मुच्चय का एक वर्ग), गठित 'G' के स्वतंत्र सम्मुच्चय (लेखाचित्र सिद्धांत) में लम्बवत के सम्मुच्चय द्वारा है। एक स्वतंत्र सम्मुच्चय का कोई भी उपसमुच्चय स्वयं एक स्वतंत्र सम्मुच्चय है, इसलिए I(G) वास्तव में उपसमुच्चय लेने के अंतर्गत बंद है।
लेखाचित्र में प्रत्येक स्वतंत्र सम्मुच्चय अपने पूरक लेखाचित्र में एक गुट (लेखाचित्र सिद्धांत), और इसके विपरीत है। इसलिए, एक लेखाचित्र का स्वतंत्रता संकुल उसके पूरक लेखाचित्र के गुट संकुल के बराबर, और इसके विपरीत होता है।
समरूपता समूह
कई लेखकों ने एक लेखाचित्र G = (V, I) के गुणों और इसके स्वतंत्रता संकुल I (G) के सजातीय समूहों के बीच संबंधों का अध्ययन किया।[1] विशेष रूप से, G में हावी सम्मुच्चय से संबंधित कई गुण प्रत्याभुति देते हैं कि I (G) के कुछ कम सजातीय समूह तुच्छ हैं।
1. G की कुल वर्चस्व संख्या, निरूपित , G - एक सम्मुच्चय S के कुल प्रभुत्व वाले सम्मुच्चय की न्यूनतम गणनांक है, जैसे कि V का प्रत्येक शीर्ष S के शीर्ष के निकट है। यदि तब है। [2]
2. G में V के उपसमुच्चय A की कुल वर्चस्व संख्या, निरूपित , एक सम्मुच्चय S की न्यूनतम गणनांक है जैसे कि A का प्रत्येक शीर्ष S के शीर्ष के समीप है। G की स्वतंत्रता प्रभुत्व संख्या, निरूपित , G में सभी स्वतंत्र समुच्चयों A का अधिकतम है। अगर , तब है। [1][3]
3. G की वर्चस्व संख्या, निरूपित , G के एक प्रभावशाली सम्मुच्चय की न्यूनतम गणनांक है - एक सम्मुच्चय S ऐसा कि V \ S का प्रत्येक शीर्ष S के एक शीर्ष के निकट है। ध्यान दें कि । अगर G एक पृष्ठरज्जु लेखाचित्र है और तब है। [4]
4. G की प्रेरित मिलान संख्या, निरूपित , G में एक प्रेरित मिलान की सबसे बड़ी गणनांक है - एक मिलान जिसमें उपसमुच्चय में किसी भी दो कोने को जोड़ने वाला हर किनारा सम्मिलित है। यदि V का एक उपसमुच्चय A उपस्थित है जैसे कि तब है। [5] यह उपरोक्त 1 और 2 दोनों गुणों का सामान्यीकरण है।
5. G का गैर-प्रभुत्व स्वतंत्रता संकुल, जिसे I'(G) के रूप में दर्शाया गया है, स्वतंत्र सम्मुच्चयों का सार सरल जटिल है जो G के प्रभावी सम्मुच्चय नहीं हैं। स्पष्ट रुप से I'(G) I(G) में निहित है; द्वारा समावेशन मानचित्र को निरूपित करें। यदि G एक तारकीय लेखाचित्र है तो प्रेरित मानचित्र सभी के लिए शून्य है। [1]: Thm.1.4 यह उपरोक्त संपत्ति 3 का सामान्यीकरण है।
6. G का भिन्नात्मक तारक-प्राबल्य संख्या, निरूपित , G में एक भिन्नात्मक तारक-बाध्यकारी वाले सम्मुच्चय का न्यूनतम आकार है। यदि तब है। [1]: Thm.1.5
संबंधित अवधारणाएँ
मेशुलम का खेल एक लेखाचित्र 'G' पर खेला जाने वाला खेल है, जिसका उपयोग 'G' के स्वतंत्रता संकुल की समजाततः अनुयोजकता पर निचली सीमा की गणना के लिए किया जा सकता है।
एक लेखाचित्र G का मिलान संकुल, जिसे M(G) के रूप में दर्शाया गया है, G में मिलान (लेखाचित्र सिद्धांत) का संक्षेप प्रतिसमुच्चीय संकुल है। यह 'G' के रेखा लेखाचित्र का स्वतंत्रता संकुल है।[6][7]
(m,n)-बिसात संकुल पूर्ण द्विदलीय लेखाचित्र Km,n. पर मिलान संकुल है यह एक m-से-n बिसात पर पदों के सभी सम्मुच्चयों का सार सरल जटिल है, जिस पर उनमें से प्रत्येक के बिना दूसरे को धमकी दिए बिना हाथी (शतरंज) को रखना संभव है।[8][9]
G का गुट संकुल G के पूरक लेखाचित्र का स्वतंत्रता संकुल है।
यह भी देखें
संदर्भ
- ↑ 1.0 1.1 1.2 1.3 Meshulam, Roy (2003-05-01). "वर्चस्व संख्या और समरूपता". Journal of Combinatorial Theory, Series A (in English). 102 (2): 321–330. doi:10.1016/S0097-3165(03)00045-1. ISSN 0097-3165.
- ↑ Chudnovsky, Maria (2000). विसंधित प्रतिनिधियों की प्रणाली (M.Sc. थीसिस). Haifa, Israel: Technion, department of mathematics.
- ↑ Aharoni, Ron; Haxell, Penny (2000). "हाइपरग्राफ के लिए हॉल की प्रमेय". Journal of Graph Theory. 35 (2): 83–88. doi:10.1002/1097-0118(200010)35:2<83::aid-jgt2>3.0.co;2-v. ISSN 0364-9024.
- ↑ Aharoni, Ron; Berger, Eli; Ziv, Ran (2002-07-01). "A Tree Version of Kőnig's Theorem". Combinatorica. 22 (3): 335–343. doi:10.1007/s004930200016. ISSN 0209-9683. S2CID 38277360.
- ↑ Meshulam, Roy (2001-01-01). "क्लिक कॉम्प्लेक्स और हाइपरग्राफ मिलान". Combinatorica (in English). 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.
- ↑ Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994). "चेसबोर्ड कॉम्प्लेक्स और मैचिंग कॉम्प्लेक्स". Journal of the London Mathematical Society (in English). 49 (1): 25–39. doi:10.1112/jlms/49.1.25. ISSN 1469-7750.
- ↑ Reiner, Victor; Roberts, Joel (2000-03-01). "न्यूनतम संकल्प और मिलान और शतरंज परिसरों की समरूपता". Journal of Algebraic Combinatorics (in English). 11 (2): 135–154. doi:10.1023/A:1008728115910. ISSN 1572-9192.
- ↑ Friedman, Joel; Hanlon, Phil (1998-09-01). "शतरंज की बिसात के बेट्टी नंबरों पर". Journal of Algebraic Combinatorics (in English). 8 (2): 193–203. doi:10.1023/A:1008693929682. ISSN 1572-9192.
- ↑ Ziegler, Günter M. (1994-02-01). "शतरंज की बिसात परिसरों की शेलबिलिटी". Israel Journal of Mathematics (in English). 87 (1): 97–110. doi:10.1007/BF02772986. ISSN 1565-8511. S2CID 59040033.
