क्लिक कॉम्प्लेक्स: Difference between revisions

Revision as of 10:40, 10 May 2023

एक ग्राफ का समूह प्रणाली। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।

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

समूह प्रणाली

गिरोह प्रणाली $X (G)$ एक अप्रत्यक्ष ग्राफ का $G$ एक सार सरल जटिल है (अर्थात, उपसमुच्चय लेने के संचालन के तहत परिमित समुच्चय का एक परिवार), वर्टेक्स (ग्राफ सिद्धांत) के समुच्चय (गणित) द्वारा गठित समूहों में $G$ . समूह का कोई भी उपसमुच्चय अपने आप में समूह है, इसलिए उपसमुच्चयों का यह परिवार एक सार सरल प्रणाली की आवश्यकता को पूरा करता है कि परिवार में एक समुच्चय का प्रत्येक उपसमुच्चय भी परिवार में होना चाहिए।

समूह प्रणाली को एक टोपोलॉजिकल स्पेस के रूप में भी देखा जा सकता है जिसमें प्रत्येक समूह $k$ कोने को आयाम के संकेतन द्वारा दर्शाया गया है $k - 1$ . एन-कंकाल|1-कंकाल का $X (G)$ (प्रणाली के अंतर्निहित ग्राफ के रूप में भी जाना जाता है) परिवार में प्रत्येक 1-तत्व समुच्चय के लिए एक शीर्ष के साथ एक अप्रत्यक्ष ग्राफ है और परिवार में प्रत्येक 2-तत्व समुच्चय के लिए बढ़त है; यह समरूप है $G$ .^[1]

नकारात्मक उदाहरण

हर समूह प्रणाली एक सार सरल जटिल है, लेकिन विपरीत सच नहीं है। उदाहरण के लिए, अमूर्त सरल जटिल पर विचार करें ${1,2,3,4}$ अधिकतम समुच्चय के साथ ${1,2,3},$ ${2,3,4},$ ${4,1}.$ अगर यह थे $X (G)$ कुछ ग्राफ का $G$ , तब $G$ किनारों का होना आवश्यक था ${1,2},$ ${1,3},$ ${2,3},$ ${2,4},$ ${3,4},$ ${4,1},$ इसलिए $X (G)$ में समूह भी होना चाहिए ${1,2,3,4}.$

स्वतंत्रता जटिल

स्वतंत्रता प्रणाली $I (G)$ एक अप्रत्यक्ष ग्राफ का $G$ वर्टेक्स (ग्राफ थ्योरी) के समुच्चय (गणित) द्वारा स्वतंत्र समुच्चयों में गठित एक सार सरल जटिल है $G$ . का समूह प्रणाली $G$ के पूरक ग्राफ के स्वतंत्रता प्रणाली के बराबर है $G$ .

संकेत प्रणाली

एक ध्वज प्रणाली 2-निर्धारित नामक एक अतिरिक्त संपत्ति के साथ एक सार सरल जटिल है: प्रत्येक उपसमूह एस के कोने के लिए, यदि एस में कोने की हर जोड़ी प्रणाली में है, तो एस खुद भी प्रणाली में है।

प्रत्येक समूह प्रणाली एक फ़्लैग प्रणाली है: यदि S में प्रत्येक जोड़ी का आकार 2 का एक समूह है, तो उनके बीच एक किनारा है, इसलिए S एक समूह है।

हर फ़्लैग प्रणाली एक समूह प्रणाली है: एक फ़्लैग प्रणाली दिया गया है, सभी वर्टिकल के समुच्चय पर एक ग्राफ़ G को परिभाषित करें, जहाँ दो कोने u,v G iff {u,v} में आसन्न हैं प्रणाली (इस ग्राफ को प्रणाली का 1-कंकाल कहा जाता है)। फ़्लैग प्रणाली की परिभाषा के अनुसार, वर्टिकल का हर समुच्चय जो जोड़े से जुड़ा हुआ है, प्रणाली में है। इसलिए, ध्वज प्रणाली 'जी' पर समूह प्रणाली के बराबर है।

इस प्रकार, संकेत प्रणाली और समूह प्रणाली अनिवार्य रूप से एक ही चीज हैं। हालांकि, कई मामलों में किसी ग्राफ के अलावा किसी अन्य डेटा से सीधे संकेत प्रणाली को परिभाषित करना सुविधाजनक होता है, बजाय अप्रत्यक्ष रूप से उस डेटा से प्राप्त ग्राफ के समूह प्रणाली के रूप में।^[2]

मिखाइल लियोनिदोविच ग्रोमोव ने संकेत प्रणाली होने की स्थिति के रूप में नो-Δ स्थिति को परिभाषित किया।

व्हिटनी प्रणाली

हस्लर व्हिटनी के बाद समूह प्रणालीों को व्हिटनी प्रणालीों के रूप में भी जाना जाता है। एक त्रिभुज (टोपोलॉजी) या द्वि-आयामी कई गुना का स्वच्छ त्रिभुज एक ग्राफ का एक ग्राफ एम्बेडिंग है $G$ कई गुना पर इस तरह से कि हर चेहरा एक त्रिकोण है और हर त्रिकोण एक चेहरा है। यदि कोई ग्राफ $G$ में व्हिटनी त्रिभुज है, इसे एक सेल प्रणाली बनाना चाहिए जो कि व्हिटनी प्रणाली के समरूपी है $G$ . इस मामले में, जटिल (स्थलीय स्थान के रूप में देखा जाता है) अंतर्निहित कई गुना होमियोमोर्फिज्म है। एक ग्राफ $G$ में 2-गुना समूह प्रणाली है, और इसे व्हिटनी त्रिभुज के रूप में एम्बेड किया जा सकता है, अगर और केवल अगर $G$ पड़ोस (ग्राफ सिद्धांत) है; इसका मतलब है कि, हर शीर्ष के लिए $v$ ग्राफ में, के पड़ोसियों द्वारा गठित प्रेरित उपग्राफ $v$ एक चक्र बनाता है।^[3]

अनुरूप hypergraph

हाइपरग्राफ का प्राइमल ग्राफ (हाइपरग्राफ) जी (एच) एक ही शीर्ष समुच्चय पर ग्राफ है, जिसके किनारों के रूप में एक ही hyperedge में एक साथ दिखाई देने वाले जोड़े हैं। एक हाइपरग्राफ को 'अनुरूप' कहा जाता है, यदि इसके प्राइमल ग्राफ का प्रत्येक अधिकतम समूह एक हाइपरेज है, या समकक्ष, यदि इसके प्राइमल ग्राफ का प्रत्येक समूह कुछ हाइपरेज में समाहित है।^[4] यदि हाइपरग्राफ को नीचे की ओर बंद करने की आवश्यकता होती है (इसलिए इसमें सभी हाइपरेज होते हैं जो कुछ हाइपरेज में समाहित होते हैं) तो हाइपरग्राफ सटीक रूप से अनुरूप होता है जब यह एक संकेत प्रणाली होता है। यह हाइपरग्राफ की भाषा को साधारण प्रणालीों की भाषा से संबंधित करता है।

उदाहरण और अनुप्रयोग

किसी भी CW प्रणाली C का बैरीसेंट्रिक उपखंड एक सीडब्ल्यू प्रणाली है जिसमें C की प्रति सेल में एक वर्टेक्स होता है। बेरिसेंट्रिक उपडिवीज़न के वर्टिकल का एक संग्रह एक सिम्प्लेक्स बनाता है अगर और केवल अगर C की कोशिकाओं का संबंधित संग्रह एक फ़्लैग (ज्यामिति) बनाता है (ए कोशिकाओं के समावेशन क्रम में श्रृंखला)।^[2]विशेष रूप से, 2-मेनिफोल्ड पर एक सेल प्रणाली का बैरीसेंट्रिक उपखंड कई गुना के व्हिटनी त्रिभुज को जन्म देता है।

आंशिक रूप से ऑर्डर किए गए समुच्चय के आदेश जटिल में आंशिक ऑर्डर के चेन (कुल ऑर्डर उपसमुच्चय) होते हैं। यदि कुछ उपसमुच्चय की प्रत्येक जोड़ी स्वयं आदेशित है, तो संपूर्ण उपसमुच्चय एक श्रृंखला है, इसलिए क्रम प्रणाली नो-Δ स्थिति को संतुष्ट करता है। इसे आंशिक क्रम के तुलनात्मक ग्राफ के समूह प्रणाली के रूप में व्याख्या किया जा सकता है।^[2]

एक ग्राफ़ के मिलान प्रणाली में किनारों के समुच्चय होते हैं जिनमें से दो एक समापन बिंदु साझा करते हैं; फिर से, समुच्चय का यह परिवार नो-Δ शर्त को पूरा करता है। इसे दिए गए ग्राफ के लाइन ग्राफ के पूरक ग्राफ के समूह प्रणाली के रूप में देखा जा सकता है। जब मिलान जटिल को बिना किसी विशेष ग्राफ के संदर्भ के रूप में संदर्भित किया जाता है, तो इसका मतलब है कि एक पूर्ण ग्राफ का मैचिंग प्रणाली। एक पूर्ण द्विदलीय ग्राफ K का मिलान प्रणाली_m,n शतरंज की बिसात के रूप में जाना जाता है। यह एक हाथी के ग्राफ के पूरक ग्राफ का समूह ग्राफ है,^[5] और इसका प्रत्येक सरलीकरण एम × एन शतरंज बोर्ड पर बदमाशों की नियुक्ति का प्रतिनिधित्व करता है जैसे कि कोई भी दो बदमाश एक दूसरे पर हमला नहीं करते हैं। जब m = n ± 1, शतरंज की बिसात एक छद्म-कई गुना बनाती है।

मीट्रिक स्थान में बिंदुओं के एक समूह का विएटोरिस-रिप्स प्रणाली एक समूह प्रणाली का एक विशेष मामला है, जो बिंदुओं के यूनिट डिस्क ग्राफ़ से बनता है; हालांकि, प्रत्येक समूह प्रणाली एक्स (जी) को अंतर्निहित ग्राफ जी पर सबसे कम पथ मीट्रिक के वीटोरिस-रिप्स प्रणाली के रूप में व्याख्या किया जा सकता है।

Hodkinson & Otto (2003) संबंधपरक संरचनाओं के तर्कशास्त्र में अनुरूप हाइपरग्राफ के अनुप्रयोग का वर्णन करें। उस संदर्भ में, एक संबंधपरक संरचना का बाधा ग्राफ संरचना का प्रतिनिधित्व करने वाले हाइपरग्राफ के अंतर्निहित ग्राफ के समान होता है, और एक संरचना संरक्षित तर्क है यदि यह एक अनुरूप हाइपरग्राफ से मेल खाती है।

ग्रोमोव ने दिखाया कि एक क्यूबिकल प्रणाली (यानी, आमने-सामने प्रतिच्छेद करने वाले hypercubes का एक परिवार) एक कैट (के) स्पेस बनाता है। सीएटी (0) स्पेस अगर और केवल अगर प्रणाली बस जुड़ा हुआ है और हर वर्टेक्स रूपों का लिंक एक ध्वज प्रणाली। इन स्थितियों को पूरा करने वाले एक क्यूबिकल प्रणाली को कभी-कभी क्यूबिंग (टोपोलॉजी) या दीवारों के साथ स्पेस कहा जाता है।^[1]^[6]

समरूपता समूह

मेशुलम^[7] समूह प्रणाली के होमोलॉजी पर निम्नलिखित प्रमेय को सिद्ध करता है। दिए गए पूर्णांक $l\geq 1,t\geq 0$ , मान लीजिए कि एक ग्राफ जी नामक संपत्ति को संतुष्ट करता है $P(l,t)$ , जिसका अर्थ है कि:

का हर समुच्चय $l$ G में शीर्षों का एक उभयनिष्ठ पड़ोसी है;
शीर्षों का एक समुच्चय मौजूद है, जिसमें प्रत्येक समुच्चय के लिए एक सामान्य पड़ोसी होता है $l$ शिखर, और इसके अलावा, प्रेरित ग्राफ जी [ए] में एक प्रेरित उपग्राफ के रूप में, टी-आयामी ऑक्टाहेड्रल क्षेत्र के 1-कंकाल की एक प्रति शामिल नहीं है।

फिर समूह प्रणाली एक्स (जी) की जे-वें कम होमोलोजी 0 और के बीच किसी भी जे के लिए तुच्छ है $\max(l-t,\lfloor {l}/{2}\rfloor )-1$ .

यह भी देखें

सिम्पलेक्स ग्राफ, एक प्रकार का ग्राफ जिसमें अंतर्निहित ग्राफ के प्रत्येक समूह के लिए एक नोड होता है
विभाजन मेट्रॉइड#समूह प्रणाली, एक प्रकार का मैट्रोइड जिसका [[matroid चौराहा]] समूह प्रणाली बना सकता है

↑ ^1.0 ^1.1 Bandelt & Chepoi (2008).
↑ ^2.0 ^2.1 ^2.2 Davis (2002).
↑ Hartsfeld & Ringel (1991); Larrión, Neumann-Lara & Pizaña (2002); Malnič & Mohar (1992).
↑ Berge (1989); Hodkinson & Otto (2003).
↑ Dong & Wachs (2002).
↑ Chatterji & Niblo (2005).
↑ Meshulam, Roy (2001-01-01). "क्लिक कॉम्प्लेक्स और हाइपरग्राफ मिलान". Combinatorica (in English). 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

संदर्भ

Bandelt, H.-J.; Chepoi, V. (2008), "Metric graph theory and geometry: a survey", in Goodman, J. E.; Pach, J.; Pollack, R. (eds.), Surveys on Discrete and Computational Geometry: Twenty Years Later (PDF), Contemporary Mathematics, vol. 453, Providence, RI: AMS, pp. 49–86.
Berge, C. (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland, ISBN 0-444-87489-5.
Chatterji, I.; Niblo, G. (2005), "From wall spaces to CAT(0) cube complexes", International Journal of Algebra and Computation, 15 (5–6): 875–885, arXiv:math.GT/0309036, doi:10.1142/S0218196705002669, S2CID 2786607.
Davis, M. W. (2002), "Nonpositive curvature and reflection groups", in Daverman, R. J.; Sher, R. B. (eds.), Handbook of Geometric Topology, Elsevier, pp. 373–422.
Dong, X.; Wachs, M. L. (2002), "Combinatorial Laplacian of the matching complex", Electronic Journal of Combinatorics, 9: R17, doi:10.37236/1634.
Hartsfeld, N.; Ringel, Gerhard (1991), "Clean triangulations", Combinatorica, 11 (2): 145–155, doi:10.1007/BF01206358, S2CID 28144260.
Hodkinson, I.; Otto, M. (2003), "Finite conformal hypergraph covers and Gaifman cliques in finite structures", The Bulletin of Symbolic Logic, 9 (3): 387–405, CiteSeerX 10.1.1.107.5000, doi:10.2178/bsl/1058448678.
Larrión, F.; Neumann-Lara, V.; Pizaña, M. A. (2002), "Whitney triangulations, local girth and iterated clique graphs", Discrete Mathematics, 258 (1–3): 123–135, doi:10.1016/S0012-365X(02)00266-2.
Malnič, A.; Mohar, B. (1992), "Generating locally cyclic triangulations of surfaces", Journal of Combinatorial Theory, Series B, 56 (2): 147–164, doi:10.1016/0095-8956(92)90015-P.

[bc-1] 1.0 ^1.1 Bandelt & Chepoi (2008).

[davis-2] 2.0 ^2.1 ^2.2 Davis (2002).

[3] Hartsfeld & Ringel (1991); Larrión, Neumann-Lara & Pizaña (2002); Malnič & Mohar (1992).

[4] Berge (1989); Hodkinson & Otto (2003).

[5] Dong & Wachs (2002).

[6] Chatterji & Niblo (2005).

[:3-7] Meshulam, Roy (2001-01-01). "क्लिक कॉम्प्लेक्स और हाइपरग्राफ मिलान". Combinatorica (in English). 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{Short description|Abstract simplicial complex describing a graph's cliques}}
-{{redirect|Whitney complex|the Mississippi sports facility|Davey Whitney Complex}}
+[[File:VR complex.svg|thumb|300px|एक ग्राफ का समूह प्रणाली। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।]]समूह प्रणाली, स्वतंत्र प्रणाली, संकेत प्रणाली, व्हिटनी प्रणाली और कंफर्मल हाइपरग्राफ [[ग्राफ सिद्धांत]] और [[ज्यामितीय टोपोलॉजी]] में निकटता से संबंधित [[गणितीय वस्तु]]एं हैं जो प्रत्येक एक [[अप्रत्यक्ष ग्राफ]] के [[क्लिक (ग्राफ सिद्धांत)|समूह (ग्राफ सिद्धांत)]] (पूर्ण उपग्राफ) का वर्णन करती हैं।
-[[File:VR complex.svg|thumb|300px|एक ग्राफ का क्लिक परिसर। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।]]क्लिक कॉम्प्लेक्स, इंडिपेंडेंस कॉम्प्लेक्स, फ्लैग कॉम्प्लेक्स, व्हिटनी कॉम्प्लेक्स और कंफर्मल हाइपरग्राफ [[ग्राफ सिद्धांत]] और [[ज्यामितीय टोपोलॉजी]] में निकटता से संबंधित [[गणितीय वस्तु]]एं हैं जो प्रत्येक एक [[अप्रत्यक्ष ग्राफ]] के [[क्लिक (ग्राफ सिद्धांत)]] (पूर्ण उपग्राफ) का वर्णन करती हैं।
-== क्लिक कॉम्प्लेक्स ==
+== समूह प्रणाली ==
-गिरोह परिसर {{math|''X''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} एक [[सार सरल जटिल]] है (अर्थात, उपसमुच्चय लेने के संचालन के तहत परिमित सेट का एक परिवार), वर्टेक्स (ग्राफ सिद्धांत) के [[सेट (गणित)]] द्वारा गठित समूहों में {{mvar|G}}. गुट का कोई भी उपसमुच्चय अपने आप में गुट है, इसलिए [[सबसेट]]ों का यह परिवार एक सार सरल परिसर की आवश्यकता को पूरा करता है कि परिवार में एक सेट का प्रत्येक उपसमुच्चय भी परिवार में होना चाहिए।
+गिरोह प्रणाली {{math|''X''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} एक [[सार सरल जटिल]] है (अर्थात, उपसमुच्चय लेने के संचालन के तहत परिमित समुच्चय का एक परिवार), वर्टेक्स (ग्राफ सिद्धांत) के [[सेट (गणित)|समुच्चय (गणित)]] द्वारा गठित समूहों में {{mvar|G}}. समूह का कोई भी उपसमुच्चय अपने आप में समूह है, इसलिए [[सबसेट|उपसमुच्चय]]ों का यह परिवार एक सार सरल प्रणाली की आवश्यकता को पूरा करता है कि परिवार में एक समुच्चय का प्रत्येक उपसमुच्चय भी परिवार में होना चाहिए।
-क्लिक कॉम्प्लेक्स को एक [[टोपोलॉजिकल स्पेस]] के रूप में भी देखा जा सकता है जिसमें प्रत्येक क्लिक {{mvar|k}} कोने को आयाम के [[संकेतन]] द्वारा दर्शाया गया है {{math|''k'' – 1}}. [[एन-कंकाल]]|1-कंकाल का {{math|''X''(''G'')}} (कॉम्प्लेक्स के अंतर्निहित ग्राफ के रूप में भी जाना जाता है) परिवार में प्रत्येक 1-तत्व सेट के लिए एक शीर्ष के साथ एक अप्रत्यक्ष ग्राफ है और परिवार में प्रत्येक 2-तत्व सेट के लिए बढ़त है; यह [[ समरूप ]] है {{mvar|G}}.<ref name="bc">{{harvtxt|Bandelt|Chepoi|2008}}.</ref>
+समूह प्रणाली को एक [[टोपोलॉजिकल स्पेस]] के रूप में भी देखा जा सकता है जिसमें प्रत्येक समूह {{mvar|k}} कोने को आयाम के [[संकेतन]] द्वारा दर्शाया गया है {{math|''k'' – 1}}. [[एन-कंकाल]]|1-कंकाल का {{math|''X''(''G'')}} (प्रणाली के अंतर्निहित ग्राफ के रूप में भी जाना जाता है) परिवार में प्रत्येक 1-तत्व समुच्चय के लिए एक शीर्ष के साथ एक अप्रत्यक्ष ग्राफ है और परिवार में प्रत्येक 2-तत्व समुच्चय के लिए बढ़त है; यह [[ समरूप ]] है {{mvar|G}}.<ref name="bc">{{harvtxt|Bandelt|Chepoi|2008}}.</ref>
 === नकारात्मक उदाहरण ===
-हर क्लिक कॉम्प्लेक्स एक सार सरल जटिल है, लेकिन विपरीत सच नहीं है। उदाहरण के लिए, अमूर्त सरल जटिल पर विचार करें {{math|{1,2,3,4} }} अधिकतम सेट के साथ {{math|{1,2,3},}} {{math|{2,3,4},}} {{math|{4,1}.}} अगर यह थे {{math|''X''(''G'')}} कुछ ग्राफ का {{mvar|G}}, तब {{mvar|G}} किनारों का होना आवश्यक था {{math|{1,2},}} {{math|{1,3},}} {{math|{2,3},}} {{math|{2,4},}} {{math|{3,4},}} {{math|{4,1},}} इसलिए {{math|''X''(''G'')}} में गुट भी होना चाहिए {{math|{1,2,3,4}.}}
+हर समूह प्रणाली एक सार सरल जटिल है, लेकिन विपरीत सच नहीं है। उदाहरण के लिए, अमूर्त सरल जटिल पर विचार करें {{math|{1,2,3,4} }} अधिकतम समुच्चय के साथ {{math|{1,2,3},}} {{math|{2,3,4},}} {{math|{4,1}.}} अगर यह थे {{math|''X''(''G'')}} कुछ ग्राफ का {{mvar|G}}, तब {{mvar|G}} किनारों का होना आवश्यक था {{math|{1,2},}} {{math|{1,3},}} {{math|{2,3},}} {{math|{2,4},}} {{math|{3,4},}} {{math|{4,1},}} इसलिए {{math|''X''(''G'')}} में समूह भी होना चाहिए {{math|{1,2,3,4}.}}
 == स्वतंत्रता जटिल ==
-[[स्वतंत्रता परिसर]] {{math|''I''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} वर्टेक्स (ग्राफ थ्योरी) के सेट (गणित) द्वारा स्वतंत्र सेटों में गठित एक सार सरल जटिल है {{mvar|G}}. का गुट परिसर {{mvar|G}} के [[पूरक ग्राफ]] के स्वतंत्रता परिसर के बराबर है {{mvar|G}}.
+[[स्वतंत्रता परिसर|स्वतंत्रता प्रणाली]] {{math|''I''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} वर्टेक्स (ग्राफ थ्योरी) के समुच्चय (गणित) द्वारा स्वतंत्र समुच्चयों में गठित एक सार सरल जटिल है {{mvar|G}}. का समूह प्रणाली {{mvar|G}} के [[पूरक ग्राफ]] के स्वतंत्रता प्रणाली के बराबर है {{mvar|G}}.
-== फ्लैग कॉम्प्लेक्स ==
+== संकेत प्रणाली ==
-एक ध्वज परिसर 2-निर्धारित नामक एक अतिरिक्त संपत्ति के साथ एक सार सरल जटिल है: प्रत्येक उपसमूह ''एस'' के कोने के लिए, यदि ''एस'' में कोने की हर जोड़ी परिसर में है, तो ''एस'' खुद भी कॉम्प्लेक्स में है।
+एक ध्वज प्रणाली 2-निर्धारित नामक एक अतिरिक्त संपत्ति के साथ एक सार सरल जटिल है: प्रत्येक उपसमूह ''एस'' के कोने के लिए, यदि ''एस'' में कोने की हर जोड़ी प्रणाली में है, तो ''एस'' खुद भी प्रणाली में है।
-प्रत्येक क्लिक कॉम्प्लेक्स एक फ़्लैग कॉम्प्लेक्स है: यदि ''S'' में प्रत्येक जोड़ी का आकार 2 का एक समूह है, तो उनके बीच एक किनारा है, इसलिए ''S'' एक गुट है।
+प्रत्येक समूह प्रणाली एक फ़्लैग प्रणाली है: यदि ''S'' में प्रत्येक जोड़ी का आकार 2 का एक समूह है, तो उनके बीच एक किनारा है, इसलिए ''S'' एक समूह है।
-हर फ़्लैग कॉम्प्लेक्स एक क्लिक कॉम्प्लेक्स है: एक फ़्लैग कॉम्प्लेक्स दिया गया है, सभी वर्टिकल के सेट पर एक ग्राफ़ ''G'' को परिभाषित करें, जहाँ दो कोने u,v ''G'' iff {u,v} में आसन्न हैं कॉम्प्लेक्स (इस ग्राफ को कॉम्प्लेक्स का ''[[1-कंकाल]]'' कहा जाता है)। फ़्लैग कॉम्प्लेक्स की परिभाषा के अनुसार, वर्टिकल का हर सेट जो जोड़े से जुड़ा हुआ है, कॉम्प्लेक्स में है। इसलिए, ध्वज परिसर 'जी' पर समूह परिसर के बराबर है।
+हर फ़्लैग प्रणाली एक समूह प्रणाली है: एक फ़्लैग प्रणाली दिया गया है, सभी वर्टिकल के समुच्चय पर एक ग्राफ़ ''G'' को परिभाषित करें, जहाँ दो कोने u,v ''G'' iff {u,v} में आसन्न हैं प्रणाली (इस ग्राफ को प्रणाली का ''[[1-कंकाल]]'' कहा जाता है)। फ़्लैग प्रणाली की परिभाषा के अनुसार, वर्टिकल का हर समुच्चय जो जोड़े से जुड़ा हुआ है, प्रणाली में है। इसलिए, ध्वज प्रणाली 'जी' पर समूह प्रणाली के बराबर है।
-इस प्रकार, फ्लैग कॉम्प्लेक्स और क्लिक कॉम्प्लेक्स अनिवार्य रूप से एक ही चीज हैं। हालांकि, कई मामलों में किसी ग्राफ के अलावा किसी अन्य डेटा से सीधे फ्लैग कॉम्प्लेक्स को परिभाषित करना सुविधाजनक होता है, बजाय अप्रत्यक्ष रूप से उस डेटा से प्राप्त ग्राफ के क्लिक कॉम्प्लेक्स के रूप में।<ref name="davis">{{harvtxt|Davis|2002}}.</ref>
+इस प्रकार, संकेत प्रणाली और समूह प्रणाली अनिवार्य रूप से एक ही चीज हैं। हालांकि, कई मामलों में किसी ग्राफ के अलावा किसी अन्य डेटा से सीधे संकेत प्रणाली को परिभाषित करना सुविधाजनक होता है, बजाय अप्रत्यक्ष रूप से उस डेटा से प्राप्त ग्राफ के समूह प्रणाली के रूप में।<ref name="davis">{{harvtxt|Davis|2002}}.</ref>
-[[मिखाइल लियोनिदोविच ग्रोमोव]] ने फ्लैग कॉम्प्लेक्स होने की स्थिति के रूप में नो-Δ स्थिति को परिभाषित किया।
+[[मिखाइल लियोनिदोविच ग्रोमोव]] ने संकेत प्रणाली होने की स्थिति के रूप में नो-Δ स्थिति को परिभाषित किया।
+== व्हिटनी प्रणाली ==
+[[हस्लर व्हिटनी]] के बाद समूह प्रणालीों को व्हिटनी प्रणालीों के रूप में भी जाना जाता है। एक त्रिभुज (टोपोलॉजी) या द्वि-आयामी [[ कई गुना | कई गुना]] का स्वच्छ त्रिभुज एक ग्राफ का एक [[ग्राफ एम्बेडिंग]] है {{mvar|G}} कई गुना पर इस तरह से कि हर चेहरा एक त्रिकोण है और हर त्रिकोण एक चेहरा है। यदि कोई ग्राफ {{mvar|G}} में व्हिटनी त्रिभुज है, इसे एक सेल प्रणाली बनाना चाहिए जो कि व्हिटनी प्रणाली के समरूपी है {{mvar|G}}. इस मामले में, जटिल (स्थलीय स्थान के रूप में देखा जाता है) अंतर्निहित कई गुना [[होमियोमोर्फिज्म]] है। एक ग्राफ {{mvar|G}} में 2-गुना समूह प्रणाली है, और इसे व्हिटनी त्रिभुज के रूप में एम्बेड किया जा सकता है, अगर और केवल अगर {{mvar|G}} [[पड़ोस (ग्राफ सिद्धांत)]] है; इसका मतलब है कि, हर शीर्ष के लिए {{mvar|v}} ग्राफ में, के पड़ोसियों द्वारा गठित [[प्रेरित सबग्राफ|प्रेरित उपग्राफ]] {{mvar|v}} एक चक्र बनाता है।<ref>{{harvtxt|Hartsfeld|Ringel|1991}}; {{harvtxt|Larrión|Neumann-Lara|Pizaña|2002}}; {{harvtxt|Malnič|Mohar|1992}}.</ref>
-== व्हिटनी कॉम्प्लेक्स ==
-[[हस्लर व्हिटनी]] के बाद क्लिक परिसरों को व्हिटनी परिसरों के रूप में भी जाना जाता है। एक त्रिभुज (टोपोलॉजी) या द्वि-आयामी [[ कई गुना ]] का स्वच्छ त्रिभुज एक ग्राफ का एक [[ग्राफ एम्बेडिंग]] है {{mvar|G}} कई गुना पर इस तरह से कि हर चेहरा एक त्रिकोण है और हर त्रिकोण एक चेहरा है। यदि कोई ग्राफ {{mvar|G}} में व्हिटनी त्रिभुज है, इसे एक सेल कॉम्प्लेक्स बनाना चाहिए जो कि व्हिटनी कॉम्प्लेक्स के आइसोमोर्फिक है {{mvar|G}}. इस मामले में, जटिल (स्थलीय स्थान के रूप में देखा जाता है) अंतर्निहित कई गुना [[होमियोमोर्फिज्म]] है। एक ग्राफ {{mvar|G}} में 2-गुना क्लिक कॉम्प्लेक्स है, और इसे व्हिटनी त्रिभुज के रूप में एम्बेड किया जा सकता है, अगर और केवल अगर {{mvar|G}} [[पड़ोस (ग्राफ सिद्धांत)]] है; इसका मतलब है कि, हर शीर्ष के लिए {{mvar|v}} ग्राफ में, के पड़ोसियों द्वारा गठित [[प्रेरित सबग्राफ]] {{mvar|v}} एक चक्र बनाता है।<ref>{{harvtxt|Hartsfeld|Ringel|1991}}; {{harvtxt|Larrión|Neumann-Lara|Pizaña|2002}}; {{harvtxt|Malnič|Mohar|1992}}.</ref>
 == अनुरूप [[ hypergraph ]] ==
-हाइपरग्राफ का [[प्राइमल ग्राफ (हाइपरग्राफ)]] जी (एच) एक ही शीर्ष सेट पर ग्राफ है, जिसके किनारों के रूप में एक ही [[ hyperedge ]] में एक साथ दिखाई देने वाले जोड़े हैं। एक हाइपरग्राफ को 'अनुरूप' कहा जाता है, यदि इसके प्राइमल ग्राफ का प्रत्येक अधिकतम क्लिक एक हाइपरेज है, या समकक्ष, यदि इसके प्राइमल ग्राफ का प्रत्येक क्लिक कुछ हाइपरेज में समाहित है।<ref>{{harvtxt|Berge|1989}}; {{harvtxt|Hodkinson|Otto|2003}}.</ref> यदि हाइपरग्राफ को नीचे की ओर बंद करने की आवश्यकता होती है (इसलिए इसमें सभी हाइपरेज होते हैं जो कुछ हाइपरेज में समाहित होते हैं) तो हाइपरग्राफ सटीक रूप से अनुरूप होता है जब यह एक फ्लैग कॉम्प्लेक्स होता है। यह हाइपरग्राफ की भाषा को साधारण परिसरों की भाषा से संबंधित करता है।
+हाइपरग्राफ का [[प्राइमल ग्राफ (हाइपरग्राफ)]] जी (एच) एक ही शीर्ष समुच्चय पर ग्राफ है, जिसके किनारों के रूप में एक ही [[ hyperedge ]] में एक साथ दिखाई देने वाले जोड़े हैं। एक हाइपरग्राफ को 'अनुरूप' कहा जाता है, यदि इसके प्राइमल ग्राफ का प्रत्येक अधिकतम समूह एक हाइपरेज है, या समकक्ष, यदि इसके प्राइमल ग्राफ का प्रत्येक समूह कुछ हाइपरेज में समाहित है।<ref>{{harvtxt|Berge|1989}}; {{harvtxt|Hodkinson|Otto|2003}}.</ref> यदि हाइपरग्राफ को नीचे की ओर बंद करने की आवश्यकता होती है (इसलिए इसमें सभी हाइपरेज होते हैं जो कुछ हाइपरेज में समाहित होते हैं) तो हाइपरग्राफ सटीक रूप से अनुरूप होता है जब यह एक संकेत प्रणाली होता है। यह हाइपरग्राफ की भाषा को साधारण प्रणालीों की भाषा से संबंधित करता है।
 == उदाहरण और अनुप्रयोग ==
-किसी भी CW कॉम्प्लेक्स C का [[बैरीसेंट्रिक उपखंड]] एक [[सीडब्ल्यू कॉम्प्लेक्स]] है जिसमें C की प्रति सेल में एक वर्टेक्स होता है। बेरिसेंट्रिक सबडिवीज़न के वर्टिकल का एक संग्रह एक सिम्प्लेक्स बनाता है अगर और केवल अगर C की कोशिकाओं का संबंधित संग्रह एक फ़्लैग (ज्यामिति) बनाता है (ए कोशिकाओं के समावेशन क्रम में श्रृंखला)।<ref name="davis"/>विशेष रूप से, 2-मेनिफोल्ड पर एक सेल कॉम्प्लेक्स का बैरीसेंट्रिक उपखंड कई गुना के व्हिटनी त्रिभुज को जन्म देता है।
+किसी भी CW प्रणाली C का [[बैरीसेंट्रिक उपखंड]] एक [[सीडब्ल्यू कॉम्प्लेक्स|सीडब्ल्यू प्रणाली]] है जिसमें C की प्रति सेल में एक वर्टेक्स होता है। बेरिसेंट्रिक उपडिवीज़न के वर्टिकल का एक संग्रह एक सिम्प्लेक्स बनाता है अगर और केवल अगर C की कोशिकाओं का संबंधित संग्रह एक फ़्लैग (ज्यामिति) बनाता है (ए कोशिकाओं के समावेशन क्रम में श्रृंखला)।<ref name="davis"/>विशेष रूप से, 2-मेनिफोल्ड पर एक सेल प्रणाली का बैरीसेंट्रिक उपखंड कई गुना के व्हिटनी त्रिभुज को जन्म देता है।
-आंशिक रूप से ऑर्डर किए गए सेट के [[ आदेश जटिल ]] में आंशिक ऑर्डर के चेन (कुल ऑर्डर सबसेट) होते हैं। यदि कुछ उपसमुच्चय की प्रत्येक जोड़ी स्वयं आदेशित है, तो संपूर्ण उपसमुच्चय एक श्रृंखला है, इसलिए क्रम परिसर नो-Δ स्थिति को संतुष्ट करता है। इसे आंशिक क्रम के [[तुलनात्मक ग्राफ]] के क्लिक परिसर के रूप में व्याख्या किया जा सकता है।<ref name="davis"/>
+आंशिक रूप से ऑर्डर किए गए समुच्चय के [[ आदेश जटिल ]] में आंशिक ऑर्डर के चेन (कुल ऑर्डर उपसमुच्चय) होते हैं। यदि कुछ उपसमुच्चय की प्रत्येक जोड़ी स्वयं आदेशित है, तो संपूर्ण उपसमुच्चय एक श्रृंखला है, इसलिए क्रम प्रणाली नो-Δ स्थिति को संतुष्ट करता है। इसे आंशिक क्रम के [[तुलनात्मक ग्राफ]] के समूह प्रणाली के रूप में व्याख्या किया जा सकता है।<ref name="davis"/>
-एक ग्राफ़ के मिलान परिसर में किनारों के सेट होते हैं जिनमें से दो एक समापन बिंदु साझा करते हैं; फिर से, सेट का यह परिवार नो-Δ शर्त को पूरा करता है। इसे दिए गए ग्राफ के [[लाइन ग्राफ]] के पूरक ग्राफ के क्लिक कॉम्प्लेक्स के रूप में देखा जा सकता है। जब [[ मिलान जटिल ]] को बिना किसी विशेष ग्राफ के संदर्भ के रूप में संदर्भित किया जाता है, तो इसका मतलब है कि एक पूर्ण ग्राफ का मैचिंग कॉम्प्लेक्स। एक [[पूर्ण द्विदलीय ग्राफ]] K का मिलान परिसर<sub>''m'',''n''</sub> [[शतरंज की बिसात]] के रूप में जाना जाता है। यह एक हाथी के ग्राफ के पूरक ग्राफ का क्लिक ग्राफ है,<ref>{{harvtxt|Dong|Wachs|2002}}.</ref> और इसका प्रत्येक सरलीकरण एम × एन शतरंज बोर्ड पर बदमाशों की नियुक्ति का प्रतिनिधित्व करता है जैसे कि कोई भी दो बदमाश एक दूसरे पर हमला नहीं करते हैं। जब m = n ± 1, शतरंज की बिसात एक [[छद्म-कई गुना]] बनाती है।
+एक ग्राफ़ के मिलान प्रणाली में किनारों के समुच्चय होते हैं जिनमें से दो एक समापन बिंदु साझा करते हैं; फिर से, समुच्चय का यह परिवार नो-Δ शर्त को पूरा करता है। इसे दिए गए ग्राफ के [[लाइन ग्राफ]] के पूरक ग्राफ के समूह प्रणाली के रूप में देखा जा सकता है। जब [[ मिलान जटिल ]] को बिना किसी विशेष ग्राफ के संदर्भ के रूप में संदर्भित किया जाता है, तो इसका मतलब है कि एक पूर्ण ग्राफ का मैचिंग प्रणाली। एक [[पूर्ण द्विदलीय ग्राफ]] K का मिलान प्रणाली<sub>''m'',''n''</sub> [[शतरंज की बिसात]] के रूप में जाना जाता है। यह एक हाथी के ग्राफ के पूरक ग्राफ का समूह ग्राफ है,<ref>{{harvtxt|Dong|Wachs|2002}}.</ref> और इसका प्रत्येक सरलीकरण एम × एन शतरंज बोर्ड पर बदमाशों की नियुक्ति का प्रतिनिधित्व करता है जैसे कि कोई भी दो बदमाश एक दूसरे पर हमला नहीं करते हैं। जब m = n ± 1, शतरंज की बिसात एक [[छद्म-कई गुना]] बनाती है।
-मीट्रिक स्थान में बिंदुओं के एक समूह का विएटोरिस-रिप्स कॉम्प्लेक्स एक क्लिक कॉम्प्लेक्स का एक विशेष मामला है, जो बिंदुओं के [[यूनिट डिस्क ग्राफ]]़ से बनता है; हालांकि, प्रत्येक क्लिक कॉम्प्लेक्स एक्स (जी) को अंतर्निहित ग्राफ जी पर सबसे कम पथ मीट्रिक के वीटोरिस-रिप्स कॉम्प्लेक्स के रूप में व्याख्या किया जा सकता है।
+मीट्रिक स्थान में बिंदुओं के एक समूह का विएटोरिस-रिप्स प्रणाली एक समूह प्रणाली का एक विशेष मामला है, जो बिंदुओं के [[यूनिट डिस्क ग्राफ]]़ से बनता है; हालांकि, प्रत्येक समूह प्रणाली एक्स (जी) को अंतर्निहित ग्राफ जी पर सबसे कम पथ मीट्रिक के वीटोरिस-रिप्स प्रणाली के रूप में व्याख्या किया जा सकता है।
 {{harvtxt|Hodkinson|Otto|2003}} संबंधपरक संरचनाओं के तर्कशास्त्र में अनुरूप हाइपरग्राफ के अनुप्रयोग का वर्णन करें। उस संदर्भ में, एक संबंधपरक संरचना का [[बाधा ग्राफ]] संरचना का प्रतिनिधित्व करने वाले हाइपरग्राफ के अंतर्निहित ग्राफ के समान होता है, और एक संरचना [[संरक्षित तर्क]] है यदि यह एक अनुरूप हाइपरग्राफ से मेल खाती है।
-ग्रोमोव ने दिखाया कि एक क्यूबिकल कॉम्प्लेक्स (यानी, आमने-सामने प्रतिच्छेद करने वाले [[hypercubes]] का एक परिवार) एक कैट (के) स्पेस बनाता है। सीएटी (0) स्पेस अगर और केवल अगर कॉम्प्लेक्स बस जुड़ा हुआ है और हर वर्टेक्स रूपों का लिंक एक ध्वज परिसर। इन स्थितियों को पूरा करने वाले एक क्यूबिकल कॉम्प्लेक्स को कभी-कभी [[क्यूबिंग (टोपोलॉजी)]] या दीवारों के साथ स्पेस कहा जाता है।<ref name="bc"/><ref>{{harvtxt|Chatterji|Niblo|2005}}.</ref>
+ग्रोमोव ने दिखाया कि एक क्यूबिकल प्रणाली (यानी, आमने-सामने प्रतिच्छेद करने वाले [[hypercubes]] का एक परिवार) एक कैट (के) स्पेस बनाता है। सीएटी (0) स्पेस अगर और केवल अगर प्रणाली बस जुड़ा हुआ है और हर वर्टेक्स रूपों का लिंक एक ध्वज प्रणाली। इन स्थितियों को पूरा करने वाले एक क्यूबिकल प्रणाली को कभी-कभी [[क्यूबिंग (टोपोलॉजी)]] या दीवारों के साथ स्पेस कहा जाता है।<ref name="bc"/><ref>{{harvtxt|Chatterji|Niblo|2005}}.</ref>
 == समरूपता समूह ==
-मेशुलम<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> क्लिक कॉम्प्लेक्स के होमोलॉजी पर निम्नलिखित प्रमेय को सिद्ध करता है। दिए गए पूर्णांक <math>l\geq 1, t\geq 0</math>, मान लीजिए कि एक ग्राफ जी नामक संपत्ति को संतुष्ट करता है <math>P(l,t)</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> समूह प्रणाली के होमोलॉजी पर निम्नलिखित प्रमेय को सिद्ध करता है। दिए गए पूर्णांक <math>l\geq 1, t\geq 0</math>, मान लीजिए कि एक ग्राफ जी नामक संपत्ति को संतुष्ट करता है <math>P(l,t)</math>, जिसका अर्थ है कि:
-* का हर सेट <math>l</math> G में शीर्षों का एक उभयनिष्ठ पड़ोसी है;
+* का हर समुच्चय <math>l</math> G में शीर्षों का एक उभयनिष्ठ पड़ोसी है;
-* शीर्षों का एक सेट मौजूद है, जिसमें प्रत्येक सेट के लिए एक सामान्य पड़ोसी होता है <math>l</math> शिखर, और इसके अलावा, प्रेरित ग्राफ जी [ए] में एक प्रेरित उपग्राफ के रूप में, टी-आयामी ऑक्टाहेड्रल क्षेत्र के 1-कंकाल की एक प्रति शामिल नहीं है।
+* शीर्षों का एक समुच्चय मौजूद है, जिसमें प्रत्येक समुच्चय के लिए एक सामान्य पड़ोसी होता है <math>l</math> शिखर, और इसके अलावा, प्रेरित ग्राफ जी [ए] में एक प्रेरित उपग्राफ के रूप में, टी-आयामी ऑक्टाहेड्रल क्षेत्र के 1-कंकाल की एक प्रति शामिल नहीं है।
-फिर क्लिक कॉम्प्लेक्स एक्स (जी) की जे-वें कम होमोलोजी 0 और के बीच किसी भी जे के लिए तुच्छ है <math>\max(l-t, \lfloor {l}/{2}\rfloor)-1</math>.
+फिर समूह प्रणाली एक्स (जी) की जे-वें कम होमोलोजी 0 और के बीच किसी भी जे के लिए तुच्छ है <math>\max(l-t, \lfloor {l}/{2}\rfloor)-1</math>.
 == यह भी देखें ==
 * [[सिम्पलेक्स ग्राफ]], एक प्रकार का ग्राफ जिसमें अंतर्निहित ग्राफ के प्रत्येक समूह के लिए एक नोड होता है
-*विभाजन मेट्रॉइड#क्लिक कॉम्प्लेक्स, एक प्रकार का मैट्रोइड जिसका [[[[ matroid ]] चौराहा]] क्लिक कॉम्प्लेक्स बना सकता है
+*विभाजन मेट्रॉइड#समूह प्रणाली, एक प्रकार का मैट्रोइड जिसका [[[[ matroid ]] चौराहा]] समूह प्रणाली बना सकता है
 ==टिप्पणियाँ==

Anonymous

Search

क्लिक कॉम्प्लेक्स: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:40, 10 May 2023

Contents

समूह प्रणाली

नकारात्मक उदाहरण

स्वतंत्रता जटिल

संकेत प्रणाली

व्हिटनी प्रणाली

अनुरूप hypergraph

उदाहरण और अनुप्रयोग

समरूपता समूह

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

क्लिक कॉम्प्लेक्स: Difference between revisions

Revision as of 10:40, 10 May 2023

समूह प्रणाली

नकारात्मक उदाहरण

स्वतंत्रता जटिल

संकेत प्रणाली

व्हिटनी प्रणाली

अनुरूप hypergraph

उदाहरण और अनुप्रयोग

समरूपता समूह

यह भी देखें

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories