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

From Vigyanwiki
mNo edit summary
No edit summary
 
(16 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Abstract simplicial complex describing a graph's cliques}}
{{Short description|Abstract simplicial complex describing a graph's cliques}}
[[File:VR complex.svg|thumb|300px|एक ग्राफ का समूह प्रणाली। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।]]समूह प्रणाली, स्वतंत्र प्रणाली, संकेत प्रणाली, व्हिटनी प्रणाली और कंफर्मल हाइपरग्राफ [[ग्राफ सिद्धांत]] और [[ज्यामितीय टोपोलॉजी]] में निकटता से संबंधित [[गणितीय वस्तु]]एं हैं जो प्रत्येक एक [[अप्रत्यक्ष ग्राफ]] के [[क्लिक (ग्राफ सिद्धांत)|समूह (ग्राफ सिद्धांत)]] (पूर्ण उपग्राफ) का वर्णन करती हैं।
[[File:VR complex.svg|thumb|300px|एक ग्राफ का समूह प्रणाली। आकार एक के समूह छोटे लाल डिस्क के रूप में दिखाए जाते हैं; आकार दो के समूहों को काली रेखा खंडों के रूप में दिखाया गया है; आकार तीन के समूहों को हल्के नीले त्रिकोण के रूप में दिखाया गया है; और आकार चार के समूहों को गहरे नीले रंग के टेट्राहेड्रा के रूप में दिखाया गया है।]]समूह प्रणाली, स्वतंत्र प्रणाली, संकेत प्रणाली, व्हिटनी प्रणाली और अनुरूप हाइपरग्राफ [[ज्यामितीय टोपोलॉजी|रेखागणितीय टोपोलॉजी]] और ग्राफ [[ग्राफ सिद्धांत|सिद्धांत]] में निकटता से संबंधित [[गणितीय वस्तु]]एं हैं जो प्रत्येक [[अप्रत्यक्ष ग्राफ]] के [[क्लिक (ग्राफ सिद्धांत)|समूह (ग्राफ सिद्धांत)]] का वर्णन करती हैं।


== समूह प्रणाली ==
== समूह प्रणाली ==
गिरोह प्रणाली {{math|''X''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} एक [[सार सरल जटिल]] है (अर्थात, उपसमुच्चय लेने के संचालन के तहत परिमित समुच्चय का एक परिवार), वर्टेक्स (ग्राफ सिद्धांत) के [[सेट (गणित)|समुच्चय (गणित)]] द्वारा गठित समूहों में {{mvar|G}}. समूह का कोई भी उपसमुच्चय अपने आप में समूह है, इसलिए [[सबसेट|उपसमुच्चय]]ों का यह परिवार एक सार सरल प्रणाली की आवश्यकता को पूरा करता है कि परिवार में एक समुच्चय का प्रत्येक उपसमुच्चय भी परिवार में होना चाहिए।
अप्रत्यक्ष ग्राफ G की समूह प्रणाली {{math|''X''(''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}} के [[संकेतन]] द्वारा दर्शाया गया है। {{math|''X''(''G'')}} जिसे प्रणाली के अंतर्निहित ग्राफ के रूप में भी जाना जाता है वो [[एन-कंकाल|1- रूप-रेखा]] श्रेणी में प्रत्येक 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},}} {{math|{2,3,4},}} {{math|{4,1<nowiki>}</nowiki>}} के साथ {{math|{1,2,3,4} }}संक्षिप्त सरल प्रणाली पर विचार करें। यदि यह किसी ग्राफ़ G का ''X'' ( ''G'' ) होता तो G के ''शीर्ष''  {1,2}, {1,3}, {2,3}, {2,4}, {3,4}, {4,1} होते इसलिए ''X'' ( ''G'' ) में भी समूह {1,2,3,4} होना चाहिए।


== स्वतंत्रता जटिल ==
 
[[स्वतंत्रता परिसर|स्वतंत्रता प्रणाली]] {{math|''I''(''G'')}} एक अप्रत्यक्ष ग्राफ का {{mvar|G}} वर्टेक्स (ग्राफ थ्योरी) के समुच्चय (गणित) द्वारा स्वतंत्र समुच्चयों में गठित एक सार सरल जटिल है {{mvar|G}}. का समूह प्रणाली {{mvar|G}} के [[पूरक ग्राफ]] के स्वतंत्रता प्रणाली के बराबर है {{mvar|G}}.
 
'''<big>स्वतंत्र प्रणाली</big>'''
 
अप्रत्यक्ष ग्राफ {{mvar|G}} की [[स्वतंत्रता परिसर|स्वतंत्र प्रणाली]] {{math|''I''(''G'')}} है जो स्वतंत्र समुच्चयों {{mvar|G}} के शीर्ष (ग्राफ सिद्धांत) के समुच्चय द्वारा निर्मित एक संक्षिप्त सरल प्रणाली है। समूह प्रणाली का {{mvar|G}} [[पूरक ग्राफ]] के स्वतंत्रता प्रणाली {{mvar|G}} के बराबर होता है।


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


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


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


इस प्रकार, संकेत प्रणाली और समूह प्रणाली अनिवार्य रूप से एक ही चीज हैं। हालांकि, कई मामलों में किसी ग्राफ के अलावा किसी अन्य डेटा से सीधे संकेत प्रणाली को परिभाषित करना सुविधाजनक होता है, बजाय अप्रत्यक्ष रूप से उस डेटा से प्राप्त ग्राफ के समूह प्रणाली के रूप में।<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>
 


'''<big><br />अनुरूप [[ hypergraph |हाइपरग्राफ]]</big>'''


== अनुरूप [[ hypergraph ]] ==
हाइपरग्राफ का [[प्राइमल ग्राफ (हाइपरग्राफ)|प्राथमिक ग्राफ]] ''G'' (''H'') एक ही शीर्ष समुच्चय पर ग्राफ है, जिसके किनारों के रूप में एक ही [[ hyperedge |अत्यंत किनारें ]]में एक साथ दिखाई देने वाले जोड़े हैं। एक हाइपरग्राफ को 'अनुरूप' कहा जाता है, यदि इसके [[प्राइमल ग्राफ (हाइपरग्राफ)|प्राथमिक]] ग्राफ का प्रत्येक अधिकतम समूह एक अत्यंत किनारा है या समकक्ष है यदि इसके [[प्राइमल ग्राफ (हाइपरग्राफ)|प्राथमिक]] ग्राफ का प्रत्येक समूह कुछ [[ hyperedge |अत्यंत]] [[ 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-मेनिफोल्ड पर एक सेल प्रणाली का बैरीसेंट्रिक उपखंड कई गुना के व्हिटनी त्रिभुज को जन्म देता है।
किसी भी कोशिका प्रणाली 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'' शतरंज [[शतरंज की बिसात|की]] [[शतरंज की बिसात|बिसात]] पर हाथी की नियुक्ति का प्रतिनिधित्व करता है जैसे कि कोई भी दो हाथी एक दूसरे पर हमला नहीं करते हैं। तब m = n ± 1, शतरंज की बिसात पर एक [[छद्म-कई गुना|आभासी-]][[ कई गुना |बहुखण्ड]] बनाता है।


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


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


ग्रोमोव ने दिखाया कि एक क्यूबिकल प्रणाली (यानी, आमने-सामने प्रतिच्छेद करने वाले [[hypercubes]] का एक परिवार) एक कैट (के) स्पेस बनाता है। सीएटी (0) स्पेस अगर और केवल अगर प्रणाली बस जुड़ा हुआ है और हर वर्टेक्स रूपों का लिंक एक ध्वज प्रणाली। इन स्थितियों को पूरा करने वाले एक क्यूबिकल प्रणाली को कभी-कभी [[क्यूबिंग (टोपोलॉजी)]] या दीवारों के साथ स्पेस कहा जाता है।<ref name="bc"/><ref>{{harvtxt|Chatterji|Niblo|2005}}.</ref>
ग्रोमोव ने दिखाया कि एक घनाकृतिक प्रणाली (यानी, आमने-सामने प्रतिच्छेद करने वाले [[hypercubes|हाइपरक्यूब]] की एक श्रेणी) एक CAT(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>, में ग्राफ ''G''  <math>P(l,t)</math> नामक गुणों को संतुष्ट करता है, जिसका अर्थ है कि:


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


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


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


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 162: Line 164:
  | year = 1992| doi-access = free
  | year = 1992| doi-access = free
  }}.
  }}.
[[Category: बीजगणितीय टोपोलॉजी]] [[Category: साधारण सेट]] [[Category: हाइपरग्राफ]]


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 01/05/2023]]
[[Category:Created On 01/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:बीजगणितीय टोपोलॉजी]]
[[Category:साधारण सेट]]
[[Category:हाइपरग्राफ]]

Latest revision as of 10:58, 18 May 2023

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

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

समूह प्रणाली

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

समूह प्रणाली को एक रेखागणितीय स्पेस के रूप में भी देखा जा सकता है जिसमें प्रत्येक समूह शीर्ष k को आकार k – 1 के संकेतन द्वारा दर्शाया गया है। X(G) जिसे प्रणाली के अंतर्निहित ग्राफ के रूप में भी जाना जाता है वो 1- रूप-रेखा श्रेणी में प्रत्येक 1-तत्व समुच्चय के लिए एक शीर्ष के साथ एक अप्रत्यक्ष ग्राफ है और श्रेणी में प्रत्येक 2-तत्व समुच्चय के लिए परिधि है जहाँ G समरूप है।[1]


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

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


स्वतंत्र प्रणाली

अप्रत्यक्ष ग्राफ G की स्वतंत्र प्रणाली I(G) है जो स्वतंत्र समुच्चयों G के शीर्ष (ग्राफ सिद्धांत) के समुच्चय द्वारा निर्मित एक संक्षिप्त सरल प्रणाली है। समूह प्रणाली का G पूरक ग्राफ के स्वतंत्रता प्रणाली G के बराबर होता है।

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

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

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

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

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

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

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

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


अनुरूप हाइपरग्राफ

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

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

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

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

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

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

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

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


समरूपता समूह

मेशुलम[7] समूह प्रणाली के समरूप पर निम्नलिखित सिद्धांत को सिद्ध करता है। मान लीजिए कि दिए गए पूर्णांक , में ग्राफ G नामक गुणों को संतुष्ट करता है, जिसका अर्थ है कि:

  • शीर्षों के प्रत्येक समुच्चय G में एक सामान्य आसन्न है;
  • शीर्षों का एक समुच्चय A उपलब्ध है, जिसमें शीर्षों के प्रत्येक समुच्चय के लिए एक सामान्य आसन्न होता है, और इसके अतिरिक्त, प्रेरित ग्राफ G[A] में एक प्रेरित उपग्राफ के रूप में, टी-आकारीय अष्टभुजाकार वृत्त के 1-रूप-रेखा की प्रति उपलब्ध नहीं है।

फिर समूह प्रणाली X(G) की जे-वें कम होमोलोजी j के बीच 0 और के लिए निम्न है।

यह भी देखें

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

टिप्पणियाँ

  1. 1.0 1.1 Bandelt & Chepoi (2008).
  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).
  7. Meshulam, Roy (2001-01-01). "क्लिक कॉम्प्लेक्स और हाइपरग्राफ मिलान". Combinatorica (in English). 21 (1): 89–94. doi:10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.


संदर्भ