सांकेतिक ग्राफ: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Graph with sign-labeled edges}} File:Pox.jpg|thumb|एक त्रिकोण की भुजाओं के लिए चिन्हों को...")
 
No edit summary
 
(10 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Graph with sign-labeled edges}}
{{Short description|Graph with sign-labeled edges}}
[[File:Pox.jpg|thumb|एक त्रिकोण की भुजाओं के लिए चिन्हों को आठ तरीकों से निर्दिष्ट किया जा सकता है। [[फ्रिट्ज हैडर]] के सिद्धांत के अनुसार, विषम संख्या में नकारात्मक चिह्न एक असंतुलित त्रिभुज बनाते हैं।]]गणित में ग्राफ़ सिद्धांत के क्षेत्र में, एक हस्ताक्षरित ग्राफ़ एक ग्राफ़ होता है जिसमें प्रत्येक किनारे पर एक सकारात्मक या नकारात्मक चिह्न होता है।
[[File:Pox.jpg|thumb|एक त्रिकोण की भुजाओं के लिए चिन्हों को आठ प्रकार से निर्दिष्ट किया जा सकता है। [[फ्रिट्ज हैडर]] के सिद्धांत के अनुसार, विषम संख्या में ऋणात्मक चिह्न एक असंतुलित त्रिभुज बनाते हैं।]]गणित में आलेख सिद्धांत के क्षेत्र में, सांकेतिक आलेख एक आलेख होता है जिसमें प्रत्येक किनारे पर एक धनात्मक या ऋणात्मक चिह्न होता है।


एक हस्ताक्षरित ग्राफ संतुलित होता है यदि हर [[चक्र ([[ग्राफ सिद्धांत]])]] के किनारे के किनारे का उत्पाद सकारात्मक है। नाम हस्ताक्षरित ग्राफ और संतुलन की धारणा पहली बार 1953 में [[फ्रैंक हैरिस]] के एक गणितीय पेपर में दिखाई दी।<ref name=harnb>{{citation|last=Harary |first=Frank |author-link=Frank Harary |journal=[[Michigan Mathematical Journal]] |mr=0067468 |pages=143–146 |title=On the notion of balance of a signed graph |url=http://projecteuclid.org/getRecord?id=euclid.mmj/1028989917 |archive-url=https://archive.today/20130415153307/http://projecteuclid.org/getRecord?id=euclid.mmj/1028989917 |url-status=dead |archive-date=2013-04-15 |volume=2 |year=1955}}</ref> डेन्स कोनिग ने पहले से ही 1936 में एक अलग शब्दावली के तहत समकक्ष धारणाओं का अध्ययन किया था, लेकिन साइन समूह की प्रासंगिकता को पहचाने बिना।<ref name=koenig>{{citation | last = Kőnig | first = Dénes | author-link = Dénes Kőnig | editor = [[Akademische Verlagsgesellschaft]] | title = Theorie der endlichen und unendlichen Graphen | year = 1936 }}</ref>
सांकेतिक आलेख संतुलित होता है यदि प्रत्येक चक्र के किनारे के संकेतों का उत्पाद धनात्मक होता है। <nowiki>''सांकेतिक आलेख''</nowiki> नाम और संतुलन की धारणा पहली बार 1953 में [[फ्रैंक हैरिस|फ्रैंक हैरी]] के एक गणितीय लेख में दिखाई गई है।<ref name=harnb>{{citation|last=Harary |first=Frank |author-link=Frank Harary |journal=[[Michigan Mathematical Journal]] |mr=0067468 |pages=143–146 |title=On the notion of balance of a signed graph |url=http://projecteuclid.org/getRecord?id=euclid.mmj/1028989917 |archive-url=https://archive.today/20130415153307/http://projecteuclid.org/getRecord?id=euclid.mmj/1028989917 |url-status=dead |archive-date=2013-04-15 |volume=2 |year=1955}}</ref> डेन्स कोनिग ने पहले से ही 1936 में एक अलग शब्दावली के अंतर्गत समतुल्य धारणाओं का अध्ययन किया था, लेकिन चिन्ह समूह की प्रासंगिकता को पहचाने बिना किया था।<ref name=koenig>{{citation | last = Kőnig | first = Dénes | author-link = Dénes Kőnig | editor = [[Akademische Verlagsgesellschaft]] | title = Theorie der endlichen und unendlichen Graphen | year = 1936 }}</ref> मिशिगन विश्वविद्यालय में समूह गतिशीलता के केंद्र में, [[डोरविन कार्टराईट]] और हैरी ने फ्रिट्ज हैडर के मनोवैज्ञानिक सिद्धांत के त्रिकोण में संतुलन के मनोवैज्ञानिक सिद्धांत को सांकेतिक रेखांकन में [[संतुलन सिद्धांत|संतुलन]] के मनोवैज्ञानिक सिद्धांत के रूप में सामान्यीकृत किया था।<ref name=carhar>{{cite journal |last1=Cartwright |first1=D. |first2=Frank |last2=Harary |year=1956 |title=Structural balance: a generalization of Heider's theory |journal=[[Psychological Review]] |volume=63 |issue=5 |pages=277–293 |doi=10.1037/h0046049 |pmid=13359597 |url=https://snap.stanford.edu/class/cs224w-readings/cartwright56balance.pdf }}</ref><ref>[[Steven Strogatz]] (2010), [http://opinionator.blogs.nytimes.com/2010/02/14/the-enemy-of-my-enemy/?ref=opinion&_r=0 The enemy of my enemy], The [[New York Times]], February 14, 2010</ref>
मिशिगन विश्वविद्यालय में सेंटर फॉर ग्रुप डायनेमिक्स में, [[डोरविन कार्टराईट]] और हैरी ने फ्रिट्ज हैडर के मनोवैज्ञानिक सिद्धांत के [[संतुलन सिद्धांत]] को भावनाओं के त्रिकोण में हस्ताक्षर किए गए रेखांकन में संतुलन के मनोवैज्ञानिक सिद्धांत के लिए सामान्यीकृत किया।<ref name=carhar>{{cite journal |last1=Cartwright |first1=D. |first2=Frank |last2=Harary |year=1956 |title=Structural balance: a generalization of Heider's theory |journal=[[Psychological Review]] |volume=63 |issue=5 |pages=277–293 |doi=10.1037/h0046049 |pmid=13359597 |url=https://snap.stanford.edu/class/cs224w-readings/cartwright56balance.pdf }}</ref><ref>[[Steven Strogatz]] (2010), [http://opinionator.blogs.nytimes.com/2010/02/14/the-enemy-of-my-enemy/?ref=opinion&_r=0 The enemy of my enemy], The [[New York Times]], February 14, 2010</ref>
 
हस्ताक्षरित रेखांकन कई बार फिर से खोजे गए हैं क्योंकि वे कई असंबद्ध क्षेत्रों में स्वाभाविक रूप से सामने आते हैं।<ref>{{citation
सांकेतिक रेखांकन बहुत बार पुनः खोजे गए हैं क्योंकि वे कई असंबद्ध क्षेत्रों में स्वाभाविक रूप से सामने आते हैं।<ref>{{citation
  | last = Zaslavsky | first = Thomas
  | last = Zaslavsky | first = Thomas
  | journal = Electronic Journal of Combinatorics
  | journal = Electronic Journal of Combinatorics
Line 12: Line 12:
  | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS8
  | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS8
  | volume = 5
  | volume = 5
  | year = 1998}}.</ref> उदाहरण के लिए, वे क्लासिकल [[ मूल प्रक्रिया ]] के सबसेट की ज्यामिति का वर्णन और विश्लेषण करने में सक्षम बनाते हैं। वे [[ टोपोलॉजिकल ग्राफ सिद्धांत ]] और [[ समूह सिद्धांत ]] में दिखाई देते हैं। वे रेखांकन में विषम और सम चक्र (ग्राफ सिद्धांत) के बारे में प्रश्नों के लिए एक स्वाभाविक संदर्भ हैं। वे गैर-फेरोमैग्नेटिक [[आइसिंग मॉडल]] में जमीनी अवस्था ऊर्जा की गणना में दिखाई देते हैं; इसके लिए Σ में सबसे बड़ा संतुलित किनारा सेट खोजने की जरूरत है। उन्हें [[सहसंबंध क्लस्टरिंग]] में डेटा वर्गीकरण पर लागू किया गया है।
  | year = 1998}}.</ref> उदाहरण के लिए, वे प्राचीन[[ मूल प्रक्रिया | मूल प्रक्रिया]] के उपसमुच्चय की ज्यामिति का वर्णन और विश्लेषण करने में सक्षम होते हैं। वे [[ टोपोलॉजिकल ग्राफ सिद्धांत |सांस्थितिक मानचित्र सिद्धांत]] और[[ समूह सिद्धांत | समूह सिद्धांत]] में दिखाई देते हैं। वे आलेख में विषम और सम चक्रों के बारे में प्रश्नों के लिए एक स्वाभाविक संदर्भ देते हैं। वे अलोहचुंबकीय [[आइसिंग मॉडल|आइसिंग निदर्श]] में आधार अवस्था ऊर्जा की गणना में दिखाई देते हैं; इसके लिए Σ में सबसे बड़ा संतुलित कोर समुच्चय खोजने की आवश्यकता है। उन्हें [[सहसंबंध क्लस्टरिंग|सहसंबंध गुच्छन]] में डेटा वर्गीकरण पर उपयोजित किया गया है।
 
== मूलभूत प्रमेय ==
एक पथ का चिह्न किनारों के चिह्नों का गुणनफल होता है। इस प्रकार एक पथ तभी धनात्मक होता है जब उसमें सम संख्या में ऋणात्मक किनारे (जहाँ शून्य सम है) होते है। फ्श्रेणी हैरी के गणितीय संतुलन सिद्धांत में, प्रत्येक चक्र सकारात्मक होने पर सांकेतिक आलेख संतुलित होता है। हैरी सिद्ध करता है कि एक सांकेतिक आलेख संतुलित होता है जब (1) नोड्स के प्रत्येक जोड़े के लिए, उनके मध्य के सभी पंथ का एक ही चिह्न होता है, या (2) शीर्षों को उपसमुच्चय (संभवतः रिक्त) की एक जोड़ी में विभाजित किया जाता है, प्रत्येक में केवल धनात्मक किनारे होते हैं, लेकिन ऋणात्मक किनारों से जुड़े होते हैं।<ref name="harnb" /> यह प्रमेय का सामान्यीकरण करता है कि एक साधारण (असांकेतिक) आरेख द्विभाज्य होता है यदि और केवल यदि प्रत्येक चक्र की लंबाई समान होती है।
 
एक साधारण प्रमाण स्विचिंग की विधि का उपयोग करता है। एक सांकेतिक आलेख को स्विच करने का अर्थ है शीर्ष उपसमुच्चय और उसके पूरक के मध्य सभी किनारों के संकेतों को प्रतिलोम कर देना है। हैरी के प्रमेय को सिद्ध करने के लिए, प्रेरण द्वारा दिखाया गया है कि Σ को सभी धनात्मक होने के लिए स्विच किया जा सकता है अगर यह संतुलित है।


== मौलिक प्रमेय ==
एक मंद प्रमेय, लेकिन एक सरल प्रमाण के साथ, यह है कि यदि सांकेतिक पूर्ण आलेख में प्रत्येक 3-चक्र धनात्मक है, तो आलेख संतुलित है। प्रमाण के लिए, एक स्वेच्छाचारी नोड ''n'' का चयन करे और उन सभी नोड्स को रखें जो ''n'' से एक समूह में धनात्मक किनारो से शृंखलित होते हैं, जिन्हें ''A'' कहा जाता है, और वे सभी जो n से दूसरे में एक ऋणात्मक किनारो से शृंखलित होते हैं, जिन्हें ''B'' कहा जाता है। यह एक पूर्ण आरेख है, ''A'' में प्रत्येक दो नोड मित्र होने चाहिए और ''B'' में प्रत्येक दो नोड मित्र होने चाहिए, अन्यथा एक 3-चक्र होगा जो असंतुलित होगा। (क्योंकि यह एक पूर्ण आरेख है, कोई भी ऋणात्मक किनारा असंतुलित 3-चक्र का कारण होगा।) इसी तरह, सभी ऋणात्मक किनारों को दो समूहों के मध्य जाना चाहिए।<ref>[http://www.scienceoftheweb.org/15-396/lectures/lecture03.pdf Luis Von Ahn Science of the Web Lecture 3 p. 28]</ref>
एक पथ का चिह्न (ग्राफ़ सिद्धांत) इसके किनारों के चिह्नों का गुणनफल है। इस प्रकार एक पथ तभी धनात्मक होता है जब उसमें सम संख्या में ऋणात्मक किनारे हों (जहाँ शून्य सम है)। फ्रैंक हैरी के गणितीय संतुलन सिद्धांत में, प्रत्येक चक्र (ग्राफ सिद्धांत) सकारात्मक होने पर एक हस्ताक्षरित ग्राफ संतुलित होता है। हैरी साबित करता है कि एक हस्ताक्षरित ग्राफ संतुलित होता है जब (1) नोड्स के प्रत्येक जोड़े के लिए, उनके बीच के सभी रास्तों का एक ही चिह्न होता है, या (2) वर्टिकल विभाजन उपसमुच्चय (संभवतः खाली) की एक जोड़ी में होता है, प्रत्येक में केवल सकारात्मक किनारे होते हैं, लेकिन नकारात्मक किनारों से जुड़ा हुआ है।<ref name=harnb/>यह प्रमेय का सामान्यीकरण करता है कि एक साधारण (अहस्ताक्षरित) ग्राफ द्विदलीय ग्राफ है यदि और केवल यदि प्रत्येक चक्र की लंबाई समान है।
== कुंठा ==


एक साधारण प्रमाण स्विचिंग की विधि का उपयोग करता है। एक हस्ताक्षरित ग्राफ़ को स्विच करने का अर्थ है शीर्ष उपसमुच्चय और उसके पूरक के बीच सभी किनारों के संकेतों को उलट देना। हैरी के प्रमेय को साबित करने के लिए, प्रेरण द्वारा दिखाया गया है कि Σ को सभी सकारात्मक होने के लिए स्विच किया जा सकता है अगर यह संतुलित है।
=== कुंठा सूचकांक ===
Σ का कुंठा सूचकांक (प्रारंभिक रूप से संतुलन की रेखा सूचकांक कहा जाता है)<ref name="measurement">Harary, Frank (1959), On the measurement of structural balance, ''Behavioral Science'' 4, 316–323.</ref> किनारों की सबसे छोटी संख्या है जिसका विलोपन, या समतुल्य जिसका चिन्ह उत्क्रमण (हैरी का एक प्रमेय<ref name="measurement" />), Σ को संतुलित बनाता है। तुल्यता का कारण यह है कि कुंठा सूचकांक किनारों की सबसे छोटी संख्या के समान होता है जिसका निषेध या, समतुल्य, विलोपन; Σ संतुलित बनाता है।


एक कमजोर प्रमेय, लेकिन एक सरल प्रमाण के साथ, यह है कि यदि हस्ताक्षरित पूर्ण ग्राफ़ में प्रत्येक 3-चक्र धनात्मक है, तो ग्राफ़ संतुलित है। प्रमाण के लिए, एक मनमाना नोड ''n'' चुनें और इसे और उन सभी नोड्स को रखें जो ''n'' से एक समूह में सकारात्मक किनारे से जुड़े हैं, जिन्हें ''A'' कहा जाता है, और वे सभी जो 'n' से जुड़े हैं 'एन' दूसरे में एक नकारात्मक किनारे से, जिसे 'बी' कहा जाता है। चूंकि यह एक पूर्ण ग्राफ है, इसलिए ''ए'' में हर दो नोड दोस्त होने चाहिए और ''बी'' में हर दो नोड दोस्त होने चाहिए, अन्यथा एक 3-चक्र होगा जो असंतुलित था। (चूंकि यह एक पूर्ण ग्राफ है, कोई भी नकारात्मक किनारा असंतुलित 3-चक्र का कारण होगा।) इसी तरह, सभी नकारात्मक किनारों को दो समूहों के बीच जाना चाहिए।<ref>[http://www.scienceoftheweb.org/15-396/lectures/lecture03.pdf Luis Von Ahn Science of the Web Lecture 3 p. 28]</ref>
कुंठा सूचकांक का वर्णन करने का दूसरा प्रकार यह है कि यह किनारों की सबसे छोटी संख्या है जो सभी ऋणात्मक चक्रों को समाविष्ट करती है। इस मात्रा को ऋणात्मक चक्र आवरण संख्या कहा गया है।


एक और समतुल्य परिभाषा है (जिसे स्विच करके आसानी से सिद्ध किया जा सकता है)। प्रत्येक शीर्ष को +1 या -1 का मान दें; हम इसे Σ की अवस्था कहते हैं। एक किनारे को संतुष्ट कहा जाता है यदि यह धनात्मक है और दोनों समापन बिंदुओं का मान समान है, या यह ऋणात्मक है और अंत बिंदुओं के विपरीत मान हैं। एक किनारा जो संतुष्ट नहीं होता है उसे कुंठा कहा जाता है। सभी अवस्था में कुंठित किनारों की सबसे छोटी संख्या कुंठा सूचकांक है। यह परिभाषा पहली बार एबेलसन और रोसेनबर्ग द्वारा (अप्रचलित) सम्मिश्रता के अंतर्गत एक अलग संकेतन में प्रस्तावित की गई थी।<ref>Robert P. Abelson; Milton J. Rosenberg (1958), Symbolic psycho-logic: a model of attitudinal cognition,  ''Behavioral Science'' 3, 1–13.</ref> ऐसे समुच्चय का पूरक सबसे संभावित किनारों के साथ Σ का संतुलित उपआरेख है।


== हताशा ==
कुंठा सूचकांक खोजना एक [[NP-कठिन]] समस्या है। अरेफ एट अल द्विआधारी क्रमादेश निदर्श का सुझाव देते हैं जो उचित समय में 105 किनारों तक आरेख के कुंठा सूचकांक की गणना करने में सक्षम हैं।<ref>{{cite arXiv|last1=Aref|first1=Samin|last2=Mason|first2=Andrew J.|last3=Wilson|first3=Mark C.|date=2019|title=हस्ताक्षरित नेटवर्क में हताशा सूचकांक का एक मॉडलिंग और कम्प्यूटेशनल अध्ययन|eprint=1611.09030|class=cs.SI}}</ref><ref>{{Citation|last1=Aref|first1=Samin|title=Computing the Line Index of Balance Using Integer Programming Optimisation|date=2018|work=Optimization Problems in Graph Theory: In Honor of Gregory Z. Gutin's 60th Birthday|pages=65–84|editor-last=Goldengorin|editor-first=Boris|series=Springer Optimization and Its Applications|publisher=Springer International Publishing|language=en|doi=10.1007/978-3-319-94830-0_3|isbn=9783319948300|last2=Mason|first2=Andrew J.|last3=Wilson|first3=Mark C.|arxiv=1710.09876|s2cid=27936778}}</ref><ref>{{Cite journal|last1=Aref|first1=Samin|last2=Wilson|first2=Mark C|date=2019-04-01|editor-last=Estrada|editor-first=Ernesto|title=हस्ताक्षरित नेटवर्क में संतुलन और हताशा|journal=Journal of Complex Networks|language=en|volume=7|issue=2|pages=163–189|doi=10.1093/comnet/cny015|issn=2051-1329|arxiv=1712.04628}}</ref> कोई भी [[NP-कठिन]] सम्मिश्रता देख सकता है कि सभी-ऋणात्मक सांकेतिक आलेख की कुंठा सूचकांक आलेख सिद्धांत में [[मैक्सकट|अधिकतम]] कम समस्या के समान है, जो [[NP-कठिन]] है।


=== निराशा सूचकांक ===
[[स्पिन ग्लास|प्रचक्रण ग्लास]] के निदर्श, मिश्रित आइसिंग निदर्श में कुंठा सूचकांक महत्वपूर्ण है। इस निदर्श में, सांकेतिक आलेख निश्चित है। एक स्थिति में प्रत्येक शीर्ष पर "प्रचक्रण", या तो "ऊपर" या "नीचे" सम्मलित है। हम प्रचक्रण ऊपर को +1 और प्रचक्रण नीचे को -1 मानते हैं। इस प्रकार, प्रत्येक अवस्था में कई कुंठित किनारे हैं। एक अवस्था की ऊर्जा तब बड़ी होती है जब उसके पास अधिक कुंठित किनारे होते हैं, इसलिए एक मूल अवस्था सबसे कम कुंठित ऊर्जा वाली अवस्था होती है। इस प्रकार, $$\ $ की मूल अवस्था ऊर्जा का पता लगाने के लिए किसी को कुंठा सूचकांक का पता लगाना होता है।
हताशा सूचकांक (प्रारंभिक रूप से संतुलन की रेखा सूचकांक कहा जाता है<ref name="measurement">Harary, Frank (1959), On the measurement of structural balance, ''Behavioral Science'' 4, 316–323.</ref>Σ की सबसे छोटी संख्या किनारों की है जिसका विलोपन, या समतुल्य जिसका साइन रिवर्सल (हैरी का एक प्रमेय<ref name="measurement" />), Σ को संतुलित बनाता है। तुल्यता का कारण यह है कि हताशा सूचकांक किनारों की सबसे छोटी संख्या के बराबर होता है जिसका निषेध (या, समतुल्य, विलोपन; Σ संतुलित बनाता है।


हताशा सूचकांक का वर्णन करने का दूसरा तरीका यह है कि यह किनारों की सबसे छोटी संख्या है जो सभी नकारात्मक चक्रों को कवर करती है। इस मात्रा को ऋणात्मक चक्र आवरण संख्या कहा गया है।
=== कुंठा संख्या ===
अनुरूप शीर्ष संख्या कुंठा संख्या है, जिसे सबसे छोटी संख्या के रूप में परिभाषित किया गया है जिसका Σ से विलोपन संतुलन में होता है। समतुल्य रूप से, कोई Σ के संतुलित प्रेरित उपआरेख का सबसे बड़ा क्रम है।


एक और समतुल्य परिभाषा है (जिसे स्विच करके आसानी से सिद्ध किया जा सकता है)। प्रत्येक शीर्ष को +1 या -1 का मान दें; हम इसे Σ की स्थिति कहते हैं। एक बढ़त को संतुष्ट कहा जाता है यदि यह सकारात्मक है और दोनों समापन बिंदुओं का मान समान है, या यह ऋणात्मक है और अंत बिंदुओं के विपरीत मान हैं। एक किनारा जो संतुष्ट नहीं होता है उसे निराश कहा जाता है। सभी राज्यों में कुंठित किनारों की सबसे छोटी संख्या हताशा सूचकांक है। यह परिभाषा पहली बार एबेलसन और रोसेनबर्ग द्वारा (अप्रचलित) नाम जटिलता के तहत एक अलग संकेतन में पेश की गई थी।<ref>Robert P. Abelson; Milton J. Rosenberg (1958), Symbolic psycho-logic: a model of attitudinal cognition,  ''Behavioral Science'' 3, 1–13.</ref> ऐसे सेट का पूरक सबसे संभावित किनारों के साथ Σ का संतुलित सबग्राफ है।
== कलनविधीय समस्याएं ==
सांकेतिक आलेख के विषय में तीन मूलभूत प्रश्न हैं: क्या यह संतुलित है? इसमें समुच्चय किए गए संतुलित किनारो का सबसे बड़ा आकार क्या है? इसे संतुलित करने के लिए हटाए जाने वाले[[ शीर्ष (ग्राफ सिद्धांत) | शीर्षों]] की सबसे छोटी संख्या क्या है? बहुपद काल में पहले प्रश्न का समाधान करना आसान है। दूसरे प्रश्न को कुंठा सूचकांक या अधिकतम संतुलित उपआरेख समस्या कहा जाता है। यह NP-कठिन है क्योंकि इसका विशेष प्रकरण (जब आरेख के सभी किनारे ऋणात्मक हैं) NP-कठिन समस्या की अधिकतम कटौती है। तीसरे प्रश्न को कुंठा संख्या या अधिकतम संतुलित प्रेरित उपआरेख समस्या कहा जाता है, यह NP-कठिन भी है; उदाहरण देखें<ref name=ggmz>{{cite journal |last1=Gülpinar |first1=N. |first2=G. |last2=Gutin |author-link2=Gregory Gutin|first3=G. |last3=Mitra |first4=A. |last4=Zverovitch |year=2004 |title=हस्ताक्षरित रेखांकन का उपयोग करके रैखिक कार्यक्रमों में शुद्ध नेटवर्क सबमैट्रिसेस निकालना|journal=[[Discrete Appl. Math.]] |volume=137 |issue=3 |pages=359–372|doi=10.1016/S0166-218X(03)00361-5 }}</ref>
== मैट्रोइड सिद्धांत ==
एक सांकेतिक आलेख से जुड़े दो मैट्रोइड्स हैं, जिन्हें चिन्ह-आलेखिक [[ matroid |मैट्रॉइड]] कहा जाता है (जिसे फ़्रेम मैट्रॉइड या कभी-कभी अभिनति मैट्रोइड भी कहा जाता है) और लिफ्ट मैट्रोइड, जो दोनों एक आलेख के चक्र मैट्रॉइड को सामान्य करते हैं। वे [[पक्षपाती ग्राफ|अभिनत आरेख]] के समान मैट्रोइड्स के विशेष प्रकरण हैं।


हताशा सूचकांक ढूँढना एक एनपी-कठिन समस्या है। अरेफ एट अल। बाइनरी प्रोग्रामिंग मॉडल सुझाएं जो 10 तक के ग्राफ के फ्रस्ट्रेशन इंडेक्स की गणना करने में सक्षम हैं<sup>उचित समय में 5 किनारे।<ref>{{cite arXiv|last1=Aref|first1=Samin|last2=Mason|first2=Andrew J.|last3=Wilson|first3=Mark C.|date=2019|title=हस्ताक्षरित नेटवर्क में हताशा सूचकांक का एक मॉडलिंग और कम्प्यूटेशनल अध्ययन|eprint=1611.09030|class=cs.SI}}</ref><ref>{{Citation|last1=Aref|first1=Samin|title=Computing the Line Index of Balance Using Integer Programming Optimisation|date=2018|work=Optimization Problems in Graph Theory: In Honor of Gregory Z. Gutin's 60th Birthday|pages=65–84|editor-last=Goldengorin|editor-first=Boris|series=Springer Optimization and Its Applications|publisher=Springer International Publishing|language=en|doi=10.1007/978-3-319-94830-0_3|isbn=9783319948300|last2=Mason|first2=Andrew J.|last3=Wilson|first3=Mark C.|arxiv=1710.09876|s2cid=27936778}}</ref>
'फ़्रेम मेट्रॉइड' (या 'चिन्ह-आलेखिक मैट्रॉइड') M(G) ने इसके आधार समुच्चय कोर समुच्चय E के लिए है।<ref>{{citation | last = Zaslavsky | first = Thomas|author-link=Thomas Zaslavsky| doi = 10.1016/0166-218X(82)90033-6 | issue = 1 | journal = [[Discrete Applied Mathematics]] | mr = 676405 | pages = 47–74 | title = Signed graphs | volume = 4 | year = 1982| hdl = 10338.dmlcz/127957 | hdl-access = free }}. Erratum.  ''Discrete Applied Mathematics'', '''5''' (1983), 248</ref> एक कोर समुच्चय स्वतंत्र होता है यदि प्रत्येक घटक में या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। ([[ मैट्रोइड सिद्धांत |मैट्रोइड सिद्धांत]] में एक अर्ध-कोर यथार्थत: ऋणात्मक लूप की तरह काम करता है।) मैट्रॉइड का एक परिपथ या तो एक धनात्मक वृत्त होता है, या एक संयोजक सामान्य पथ के साथ ऋणात्मक वृत्त का एक जोड़ होता है, जैसे कि दो वृत्त या तो अलग हो जाते हैं (फिर संयोजक पथ में प्रत्येक वृत्त के साथ सामान्य एक अंत होता है और अन्यथा दोनों से अलग होता है) या केवल एक सामान्य शीर्ष अनुकरण (इस प्रकरण में संयोजक पथ वह एकल शीर्ष है) करते है। कोर समुच्चय S की कोटि n - b है, जहाँ n, G के शीर्षों की संख्या है और b, S के संतुलित घटकों की संख्या है, पृथक शीर्षों को संतुलित घटकों के रूप में गिना जाता है। यह मेट्रॉइड सांकेतिक आलेख के आपतन आव्यूह का स्तंभ मेट्रॉइड है। यही कारण है कि यह प्राचीन मूल तंत्र की मूलांश की रैखिक निर्भरताओं का वर्णन करता है।
<ref>{{Cite journal|last1=Aref|first1=Samin|last2=Wilson|first2=Mark C|date=2019-04-01|editor-last=Estrada|editor-first=Ernesto|title=हस्ताक्षरित नेटवर्क में संतुलन और हताशा|journal=Journal of Complex Networks|language=en|volume=7|issue=2|pages=163–189|doi=10.1093/comnet/cny015|issn=2051-1329|arxiv=1712.04628}}</ref> कोई भी एनपी-हार्ड जटिलता देख सकता है कि सभी-नकारात्मक हस्ताक्षरित ग्राफ़ की हताशा सूचकांक ग्राफ़ सिद्धांत में [[मैक्सकट]] समस्या के समान है, जो एनपी-हार्ड है।


[[स्पिन ग्लास]]ेस के एक मॉडल, आइसिंग मॉडल#मिश्रित में फ्रस्ट्रेशन इंडेक्स महत्वपूर्ण है। इस मॉडल में, हस्ताक्षरित ग्राफ निश्चित है। एक राज्य में प्रत्येक शीर्ष पर ऊपर या नीचे स्पिन देना शामिल है। हम स्पिन अप को +1 और स्पिन डाउन को -1 मानते हैं। इस प्रकार, प्रत्येक राज्य में कई कुंठित किनारे हैं। एक राज्य की ऊर्जा तब बड़ी होती है जब उसके पास अधिक कुंठित किनारे होते हैं, इसलिए एक जमीनी राज्य सबसे कम कुंठित ऊर्जा वाला राज्य होता है। इस प्रकार, $$\ $ की जमीनी स्थिति ऊर्जा का पता लगाने के लिए किसी को निराशा सूचकांक का पता लगाना होगा।
'विस्तारित लिफ्ट मैट्रॉइड' ''L''<sub>0</sub>(''G'') ने अपने आधार के लिए समुच्चय ''E''<sub>0</sub> को कोर समुच्चय E के एक अतिरिक्त बिंदु के साथ समुच्चय किया है, जिसे हम ''e''<sub>0</sub> से निरूपित करते है। लिफ्ट मैट्रॉइड ''L''(''G'') ''E'' तक सीमित विस्तारित लिफ्ट मैट्रॉइड है। अतिरिक्त बिंदु यथार्थत: ऋणात्मक लूप की तरह फलन करता है, इसलिए हम केवल लिफ्ट मैट्रॉइड का वर्णन करते हैं। एक कोर का समुच्चय स्वतंत्र होता है यदि इसमें या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। (यह वही नियम है जो सांकेतिक-आलेखिक मैट्रोइड में प्रत्येक घटक के लिए अलग से उपयोजित होता है।) एक मैट्रॉइड परिपथ या तो एक धनात्मक वृत्त या ऋणात्मक वृत्तों का एक जोड़ होता है जो या तो अलग हैं या केवल सामान्य शीर्ष है। कोर समुच्चय ''S'' की श्रेणी ''n'' - ''c'' + ε है, जहां ''c'' वियुक्त शीर्षों की गणना करते हुए ''S'' के घटकों की संख्या है, और ε 0 है यदि S संतुलित है और 1 यदि यह संतुलित नहीं है।


=== निराशा संख्या ===
== अन्य प्रकार के सांकेतिक आलेख ==
अनुरूप शीर्ष संख्या हताशा संख्या है, जिसे सबसे छोटी संख्या के रूप में परिभाषित किया गया है जिसका Σ से विलोपन संतुलन में होता है। समतुल्य रूप से, कोई Σ के संतुलित प्रेरित सबग्राफ का सबसे बड़ा क्रम चाहता है।
कभी-कभी संकेतों को +1 और -1 मान लिया जाता है। यह केवल अंकन का अंतर है, यदि संकेतों को अभी भी एक वृत्त के चारों ओर गुणा किया जाता है और गुणनफल का चिह्न महत्वपूर्ण है। हालांकि, किनारो के लेबल का उपचारण करने के दो अन्य प्रकार हैं जो सांकेतिक आलेख सिद्धांत में उपयुक्त नहीं होते हैं।


== एल्गोरिथम समस्याएं ==
सांकेतिक आलेख शब्द को कभी-कभी आलेख पर उपयोजित किया जाता है जिसमें प्रत्येक किनारे का भार, w(e) = +1 या -1 होता है। ये एक ही प्रकार के सांकेतिक आलेख नहीं हैं; वे एक प्रतिबंधित भार समुच्चय के साथ भारित [[ग्राफ (असतत गणित)|आरेख (असतत गणित)]] हैं। अंतर यह है कि भार जोड़ा जाता है, गुणा नहीं किया जाता है। समस्याएं और प्रकार पूरी तरह से अलग हैं।
हस्ताक्षरित ग्राफ़ के बारे में तीन मूलभूत प्रश्न हैं: क्या यह संतुलित है? इसमें सेट किए गए संतुलित किनारे का सबसे बड़ा आकार क्या है? [[ शीर्ष (ग्राफ सिद्धांत) ]] की सबसे छोटी संख्या क्या है जिसे संतुलित करने के लिए हटाया जाना चाहिए? बहुपद समय में पहला प्रश्न हल करना आसान है। दूसरे प्रश्न को फ्रस्ट्रेशन इंडेक्स या मैक्सिमम बैलेंस्ड सबग्राफ समस्या कहा जाता है। यह एनपी-हार्ड है क्योंकि इसका विशेष मामला (जब ग्राफ के सभी किनारे नकारात्मक हैं) एनपी-हार्ड प्रॉब्लम मैक्सिमम कट है। तीसरे प्रश्न को निराशा संख्या या अधिकतम संतुलित प्रेरित सबग्राफ समस्या कहा जाता है, यह एनपी-हार्ड भी है; उदाहरण देखें<ref name=ggmz>{{cite journal |last1=Gülpinar |first1=N. |first2=G. |last2=Gutin |author-link2=Gregory Gutin|first3=G. |last3=Mitra |first4=A. |last4=Zverovitch |year=2004 |title=हस्ताक्षरित रेखांकन का उपयोग करके रैखिक कार्यक्रमों में शुद्ध नेटवर्क सबमैट्रिसेस निकालना|journal=[[Discrete Appl. Math.]] |volume=137 |issue=3 |pages=359–372|doi=10.1016/S0166-218X(03)00361-5 }}</ref>


नाम उन आलेखों पर भी उपयोजित होता है जिनमें संकेत किनारों पर रंगों के रूप में फलन करते हैं। रंग का महत्व यह है कि यह किनारे पर लगाए गए विभिन्न भारों को निर्धारित करता है, और ऐसा नहीं है कि इसका चिन्ह आंतरिक रूप से महत्वपूर्ण है। [[गाँठ सिद्धांत|ग्रंथि सिद्धांत]] में यह स्थिति है, जहाँ संकेतों का केवल महत्व यह है कि उन्हें द्वि-तत्व समूह द्वारा परस्पर बदला जा सकता है, लेकिन धनात्मक और ऋणात्मक के मध्य कोई आंतरिक अंतर नहीं है। सांकेतिक रंग के आलेख का मैट्रोइड अंतर्निहित आलेख का चक्र मैट्रोइड है; यह सांकेतिक आलेख का फ्रेम या लिफ्ट मैट्रॉइड नहीं है। चिन्ह लेबल, मैट्रोइड को बदलने के बदले, मैट्रोइड के तत्वों पर संकेत बन जाता हैं।


== मैट्रोइड सिद्धांत ==
इस लेख में हम यथार्थ अर्थों में केवल सांकेतिक आलेख सिद्धांत पर विचार करते हैं। सांकेतिक रंग के आलेख के लिए [[रंगीन मैट्रोइड|रंगीन मैट्रोइड्]] देखें।
एक हस्ताक्षरित ग्राफ़ से जुड़े दो मैट्रोइड्स हैं, जिन्हें साइन-ग्राफ़िक [[ matroid ]] कहा जाता है (जिसे फ़्रेम मैट्रॉइड या कभी-कभी बायस मैट्रोइड भी कहा जाता है) और लिफ्ट मैट्रोइड, जो दोनों एक ग्राफ़ के चक्र मैट्रॉइड को सामान्य करते हैं। वे [[पक्षपाती ग्राफ]] के समान मैट्रोइड्स के विशेष मामले हैं।
 
===सांकेतिक दिशा आरेख ===
एक सांकेतिक दिशा आरेख सांकेतिक चाप के साथ एक [[निर्देशित ग्राफ|निर्देशित आरेख]] है। सांकेतिक दिशा आरेख  सांकेतिक आलेख की तुलना में कहीं अधिक सम्मिश्र हैं, क्योंकि केवल निर्देशित चक्रों के संकेत ही महत्वपूर्ण हैं। उदाहरण के लिए, संतुलन की कई परिभाषाएँ हैं, जिनमें से प्रत्येक को चित्रित करना कठिन है, सांकेतिक अप्रत्यक्ष रेखांकन की स्थिति के विपरीत हैं।
 
सांकेतिक द्विलेखों को अभिविन्यस्त के साथ अस्पष्ट नहीं होना चाहिए। उत्तरार्द्ध द्विदिश रेखांकन हैं, निर्देशित रेखांकन नहीं (सभी धनात्मक संकेतों के तुच्छ प्रकरण को छोड़कर) हैं।
 
== शीर्ष संकेत ==
एक शीर्ष-सांकेतिक आलेख, जिसे कभी-कभी चिह्नित आलेख कहा जाता है, एक आलेख होता है जिसके शीर्षों को संकेत दिए जाते हैं। एक वृत्त को संगत कहा जाता है (लेकिन यह तार्किक स्थिरता से असंबंधित है) या सामंजस्यपूर्ण कहा जाता है यदि इसके शीर्ष संकेतों का गुणनफल धनात्मक है, और भिन्न या असंगत है यदि उत्पाद ऋणात्मक है। हरारी के संतुलन प्रमेय के अनुरूप सामंजस्यपूर्ण शीर्ष-सांकेतिक रेखांकन का कोई सरल लक्षण वर्णन नहीं है; इसके बदले, अभिलक्षण एक कठिन समस्या रही है, जोगलेकर, शाह और दीवान (2012) द्वारा सबसे अच्छा समाधान (और भी सामान्यतः) किया गया है।<ref name="JSD">Manas Joglekar, Nisarg Shah, and Ajit A. Diwan (2012), "Balanced group labeled graphs", ''Discrete Mathematics'', vol. 312, no. 9, pp. 1542–1549.</ref>
 
प्रमुख परिवर्तन के बिना शीर्ष संकेतों के सिद्धांत में किनारो के संकेतों को जोड़ना प्रायः आसान होता है; इस प्रकार, शीर्ष-सांकेतिक आलेख (या चिह्नित सांकेतिक आलेख) के लिए कई परिणाम स्वाभाविक रूप से शीर्ष-और-किनारे-सांकेतिक आलेख तक विस्तारित होते हैं। जोगलेकर, शाह और दीवान (2012) द्वारा सद्भाव के अभिलक्षणन वर्णन के लिए यह विशेष रूप से सत्य है।


'फ़्रेम मेट्रॉइड' (या 'साइन-ग्राफ़िक मैट्रॉइड') M(G) ने अपने ग्राउंड सेट के लिए एज सेट E किया है।<ref>{{citation | last = Zaslavsky | first = Thomas|author-link=Thomas Zaslavsky| doi = 10.1016/0166-218X(82)90033-6 | issue = 1 | journal = [[Discrete Applied Mathematics]] | mr = 676405 | pages = 47–74 | title = Signed graphs | volume = 4 | year = 1982| hdl = 10338.dmlcz/127957 | hdl-access = free }}. Erratum.  ''Discrete Applied Mathematics'', '''5''' (1983), 248</ref> एक एज सेट स्वतंत्र होता है यदि प्रत्येक घटक में या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। ([[ मैट्रोइड सिद्धांत ]] में एक हाफ-एज बिल्कुल नेगेटिव लूप की तरह काम करता है।) मैट्रॉइड का एक सर्किट या तो एक पॉजिटिव सर्कल होता है, या एक कनेक्टिंग सिंपल पाथ के साथ नेगेटिव सर्किल का एक जोड़ा होता है, जैसे कि दो सर्कल या तो डिसजॉइंट होते हैं (फिर कनेक्टिंग पथ का प्रत्येक सर्कल के साथ एक छोर आम है और अन्यथा दोनों से अलग है) या केवल एक सामान्य शीर्ष साझा करें (इस मामले में कनेक्टिंग पथ वह एकल शीर्ष है)। एज सेट S की कोटि n - b है, जहाँ n, G के शीर्षों की संख्या है और b, S के संतुलित घटकों की संख्या है, पृथक शीर्षों को संतुलित घटकों के रूप में गिनते हुए।
एक चिह्नित सांकेतिक आलेख और एक अवस्था फलन के साथ एक सांकेतिक आलेख के मध्य का अंतर (§ कुंठा के रूप में) यह है कि पूर्व में शीर्ष संकेत आवश्यक संरचना का भाग हैं, जबकि एक अवस्था फलन सांकेतिक आलेख पर एक चर फलन है।
यह matroid हस्ताक्षरित ग्राफ़ के घटना मैट्रिक्स का matroid सिद्धांत है।
यही कारण है कि यह शास्त्रीय रूट सिस्टम की जड़ों की रैखिक निर्भरताओं का वर्णन करता है।


'विस्तारित लिफ्ट मैट्रॉइड' एल<sub>0</sub>(जी) ने इसके आधार के लिए सेट ई सेट किया है<sub>0</sub> एज सेट E का एक 'अतिरिक्त बिंदु' के साथ मिलन, जिसे हम e से निरूपित करते हैं<sub>0</sub>. लिफ्ट मैट्रॉइड ''एल''(''जी'') ''ई'' तक सीमित विस्तारित लिफ्ट मैट्रॉइड है। अतिरिक्त बिंदु बिल्कुल नकारात्मक पाश की तरह कार्य करता है, इसलिए हम केवल लिफ्ट मैट्रॉइड का वर्णन करते हैं। एक किनारे का सेट स्वतंत्र होता है यदि इसमें या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। (यह वही नियम है जो हस्ताक्षरित-ग्राफ़िक मैट्रोइड में प्रत्येक घटक के लिए अलग से लागू होता है।) एक मैट्रॉइड सर्किट या तो एक सकारात्मक सर्कल या नकारात्मक सर्किलों की एक जोड़ी है जो या तो अलग हैं या केवल एक सामान्य शीर्ष है। एज सेट ''S'' की रैंक ''n'' - ''c'' + ε है, जहां ''c'' ''S'' के घटकों की संख्या है, अलग-अलग शीर्षों की गणना, और ε यदि 'S' संतुलित है तो 0 है और यदि नहीं है तो 1 है।
ध्यान दें कि <nowiki>''</nowiki>[[चिह्नित ग्राफ|चिह्नित आरेख<nowiki>''</nowiki>]] शब्द का व्यापक रूप से [[पेट्री नेट]] में पूरी तरह से अलग अर्थ में उपयोग किया जाता है; चिह्नित रेखांकन पर लेख देखें।


== अन्य प्रकार के हस्ताक्षरित ग्राफ ==
== रंग ==
कभी-कभी संकेतों को +1 और -1 मान लिया जाता है। यह केवल अंकन का अंतर है, यदि संकेतों को अभी भी एक वृत्त के चारों ओर गुणा किया जाता है और गुणनफल का चिह्न महत्वपूर्ण है। हालांकि, किनारे के लेबल का इलाज करने के दो अन्य तरीके हैं जो हस्ताक्षरित ग्राफ सिद्धांत में फिट नहीं होते हैं।
असांकेतिक आलेख सिद्धांत के साथ, सांकेतिक आलेख रंग की एक धारणा है। जहाँ आलेख का [[ग्राफ रंग|रंग]] शीर्ष समुच्चय से प्राकृतिक संख्याओं तक मानचित्रण होता है, एक सांकेतिक आलेख का रंग शीर्ष समुच्चय से पूर्णांकों तक मानचित्रण होता है। उचित रंगों पर प्रतिबंध सांकेतिक आलेख के किनारों से आते हैं। दो शीर्षों के निर्दिष्ट पूर्णांक भिन्न होने चाहिए यदि वे एक धनात्मक किनारो से जुड़े होते है। यदि कोने ऋणात्मक किनारे से जुड़े हुए हैं, तो आसन्न कोने पर लेबल योगात्मक व्युत्क्रम नहीं होना चाहिए। धनात्मक लूप के साथ सांकेतिक आलेख का कोई उचित रंग नहीं हो सकता है।


हस्ताक्षरित ग्राफ़ शब्द को कभी-कभी ग्राफ़ पर लागू किया जाता है जिसमें प्रत्येक किनारे का भार होता है, w(e) = +1 या -1। ये एक ही प्रकार के हस्ताक्षरित ग्राफ़ नहीं हैं; वे प्रतिबंधित वजन सेट के साथ [[ग्राफ (असतत गणित)]] हैं। अंतर यह है कि वज़न जोड़ा जाता है, गुणा नहीं किया जाता है। समस्याएं और तरीके पूरी तरह से अलग हैं।
अधिकतम प्राकृतिक संख्या k पर परिमाण के साथ पूर्णांक के समुच्चय पर शीर्ष लेबल को प्रतिबंधित करते समय, एक सांकेतिक आलेख के उचित रंगों का समुच्चय परिमित होता है। ऐसे उचित रंगों की संख्या और k के मध्य का संबंध k में एक बहुपद है; जब इसे <math>2k+1</math> के संदर्भ में व्यक्त किया गया है तो इसे सांकेतिक आलेख का [[रंगीन बहुपद]] कहा जाता है। यह एक असांकेतिक आलेख के रंगीन बहुपद के अनुरूप है।


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


इस लेख में हम सख्त अर्थों में केवल हस्ताक्षरित ग्राफ सिद्धांत पर चर्चा करते हैं। सांकेतिक रंग के ग्राफ़ के लिए [[रंगीन मैट्रोइड]]्स देखें।
===[[सामाजिक मनोविज्ञान]]===
सामाजिक मनोविज्ञान में, सांकेतिक रेखांकन का उपयोग सामाजिक स्थितियों को निदर्श करने के लिए किया गया है, धनात्मक किनारों के साथ दोस्ती का प्रतिनिधित्व करते हैं और नोड्स के मध्य ऋणात्मक किनारों के द्वेष, जो लोगों का प्रतिनिधित्व करते हैं।<ref name=carhar/> फिर, उदाहरण के लिए, एक धनात्मक 3-चक्र या तो तीन परस्पर मित्र हैं, या एक सामान्य शत्रु वाले दो मित्र हैं; जबकि एक ऋणात्मक 3-चक्र या तो तीन परस्पर शत्रु हैं, या दो शत्रु हैं जो एक अन्योन्य मित्र अनुकरण करते हैं। संतुलन सिद्धांत के अनुसार, धनात्मक चक्र संतुलित होते हैं और इन्हें स्थिर सामाजिक स्थिति माना जाता है, जबकि ऋणात्मक चक्र असंतुलित होते हैं और इन्हें अस्थिर माना जाता है। सिद्धांत के अनुसार, तीन अन्योन्य शत्रुओं के प्रकरण में, ऐसा इसलिए है क्योंकि एक सामान्य शत्रु को अनुकरण करने से दो शत्रुओं के मित्र बनने की संभावना होती है। एक मित्र को अनुकरण करने वाले दो शत्रुओं के प्रकरण में, अनुकरण मित्र एक दूसरे को चयन करने की संभावना रखते है और अपनी दोस्ती में से एक को शत्रु में बदल देते है।


===हस्ताक्षरित डिग्राफ ===
एंटल, क्रैपीव्स्की और रेडर [[सामाजिक गतिशीलता]] को एक सांकेतिक आलेख के किनारे पर चिन्ह इन परिवर्तन के रूप में मानते हैं।<ref>T. Antal, P.L. Krapivsky & S. Redner (2006) [https://arxiv.org/abs/physics/0605183 Social Balance on Networks: The Dynamics of Friendship and Enmity]</ref> एक तलाकशुदा जोड़े के पिछले दोस्तों के साथ सामाजिक संबंधों का उपयोग समाज में एक सांकेतिक आलेख के विकास को दर्शाने के लिए किया जाता है। एक अन्य दृष्टांत [[प्रथम विश्व युद्ध]] से पहले के दशकों में यूरोपीय शक्तियों के मध्य बदलते अंतरराष्ट्रीय समझौते का वर्णन करता है। वे स्थानीय त्रय गतिकी और विवश त्रय गतिकी पर विचार करते हैं, जहां बाद वाले प्रकरण में एक संबंध परिवर्तन तभी किया जाता है जब असंतुलित त्रय की कुल संख्या कम हो जाती है। अनुकरण ने परिवर्तन के लिए चयन किए गए यादृच्छिक असंतुलित त्रिभुज वाले यादृच्छिक संबंधों के साथ एक पूर्ण आरेख माना जाता है। इस प्रक्रिया के अंतर्गत ''N'' नोड्स के साथ सांकेतिक आलेख के विकास का अध्ययन किया जाता है और उपयोगी लिंक के स्थिर घनत्व का वर्णन करने के लिए अनुकरण किया जाता है।
एक हस्ताक्षरित डिग्राफ हस्ताक्षरित चाप के साथ एक [[निर्देशित ग्राफ]] है। हस्ताक्षरित डिग्राफ हस्ताक्षरित ग्राफ़ की तुलना में कहीं अधिक जटिल हैं, क्योंकि केवल निर्देशित चक्रों के संकेत ही महत्वपूर्ण हैं। उदाहरण के लिए, संतुलन की कई परिभाषाएँ हैं, जिनमें से प्रत्येक को चित्रित करना कठिन है, हस्ताक्षरित अप्रत्यक्ष रेखांकन की स्थिति के विपरीत।


हस्ताक्षरित द्विलेखों को #अभिविन्यास के साथ भ्रमित नहीं होना चाहिए। उत्तरार्द्ध द्विदिश रेखांकन हैं, निर्देशित रेखांकन नहीं (सभी सकारात्मक संकेतों के तुच्छ मामले को छोड़कर)।
संतुलन सिद्धांत को गंभीर रूप से चुनौती दी गई है, विशेष रूप से बड़ी प्रणालियों के लिए इसके आवेदन में, सैद्धांतिक आधार पर कि उपयोगी संबंध समाज को एक साथ बांधते हैं, जबकि शत्रु के दो कैंप में विभाजित समाज अत्यधिक अस्थिर होते है।<ref>B. Anderson, in ''Perspectives on Social Network Research'', ed. P.W. Holland and S. Leinhardt. New York: Academic Press, 1979.</ref> प्रायोगिक अध्ययनों ने भी संरचनात्मक संतुलन सिद्धांत की भविष्यवाणियों की केवल कमजोर पुष्टि प्रदान की है।<ref>{{cite journal | last1 = Morrissette | first1 = Julian O. | last2 = Jahnke | first2 = John C. | year = 1967 | title = संरचनात्मक संतुलन के सिद्धांत में शक्ति शून्य का कोई संबंध और संबंध नहीं| journal = Human Relations | volume = 20 | issue = 2| pages = 189–195 | doi = 10.1177/001872676702000207 | s2cid = 143210382 }}</ref>
=== प्रचक्रण ग्लास ===
भौतिकी में, सांकेतिक रेखांकन अलोहचुंबकीय आइसिंग निदर्श के लिए एक प्राकृतिक संदर्भ है, जो प्रचक्रण ग्लास के अध्ययन के लिए उपयोजित होता है।


== वर्टेक्स संकेत ==
=== सम्मिश्र पद्धति ===
एक शीर्ष-हस्ताक्षरित ग्राफ़, जिसे कभी-कभी चिह्नित ग्राफ़ कहा जाता है, एक ग्राफ़ होता है जिसके शीर्षों को संकेत दिए जाते हैं। एक वृत्त को संगत कहा जाता है (लेकिन यह तार्किक स्थिरता से असंबंधित है) या सामंजस्यपूर्ण कहा जाता है यदि इसके शीर्ष संकेतों का गुणनफल सकारात्मक है, और असंगत या धार्मिक है यदि उत्पाद ऋणात्मक है। हरारी के संतुलन प्रमेय के अनुरूप सामंजस्यपूर्ण शीर्ष-हस्ताक्षरित रेखांकन का कोई सरल लक्षण वर्णन नहीं है; इसके बजाय, चरित्र-चित्रण एक कठिन समस्या रही है, जोगलेकर, शाह और दीवान (2012) द्वारा सबसे अच्छा हल किया गया है (और भी आम तौर पर)।<ref name="JSD">Manas Joglekar, Nisarg Shah, and Ajit A. Diwan (2012), "Balanced group labeled graphs", ''Discrete Mathematics'', vol. 312, no. 9, pp. 1542–1549.</ref>
[[File:Simple 3-level trophic system.png|thumb|right|एक साधारण पोषी स्तर का प्रतिनिधित्व करने वाला एक तीन-चर सांकेतिक दिशा आरेख ]]प्रारंभिक रूप से जनसंख्या जीव विज्ञान और पारिस्थितिकी में विकसित एक विश्लेषणात्मक पद्धति का उपयोग करना, लेकिन अब कई वैज्ञानिक विषयों में उपयोग किया जाता है, सांकेतिक दिशा आरेख ने सम्मिश्र कारण प्रणालियों के व्यवहार के तर्क में आवेदन पाया है।<ref>Puccia, Charles J. and [[Richard Levins|Levins, Richard]] (1986). ''[http://www.hup.harvard.edu/catalog.php?isbn=9780674435070 Qualitative Modeling of Complex Systems: An Introduction to Loop Analysis and Time Averaging]''. Harvard University Press, Cambridge, MA.</ref><ref>{{cite journal | last1 = Dambacher | first1 = Jeffrey M. | last2 = Li | first2 = Hiram W. | last3 = Rossignol | first3 = Philippe A. | year = 2002 | title = पारिस्थितिक भविष्यवाणियों की अनिश्चितता का आकलन करने में सामुदायिक संरचना की प्रासंगिकता| journal = Ecology | volume = 83 | issue = 5| pages = 1372–1385 | doi = 10.1890/0012-9658(2002)083[1372:rocsia]2.0.co;2 | jstor = 3071950 }}</ref> इस तरह के विश्लेषण पद्धति के दिए गए स्तरों पर प्रतिक्रिया के बारे में प्रश्नो के उत्तर देते हैं, और एक या एक से अधिक बिंदुओं पर एक पद्धति को दी गई चर प्रतिक्रियाओं की दिशा के बारे में, इस तरह के क्षोभ के चर सहसंबंध, पद्धति में विचरण का वितरण, और संवेदनशीलता या पद्धति क्षोभ के लिए विशेष चर की असंवेदनशीलता देते हैं।
बड़े बदलाव के बिना वर्टेक्स संकेतों के सिद्धांत में किनारे के संकेतों को जोड़ना अक्सर आसान होता है; इस प्रकार, शीर्ष-हस्ताक्षरित ग्राफ़ (या चिह्नित हस्ताक्षरित ग्राफ़) के लिए कई परिणाम स्वाभाविक रूप से शीर्ष-और-किनारे-हस्ताक्षरित ग्राफ़ तक विस्तारित होते हैं। जोगलेकर, शाह और दीवान (2012) द्वारा सद्भाव के लक्षण वर्णन के लिए यह विशेष रूप से सच है।


एक चिह्नित हस्ताक्षरित ग्राफ और एक राज्य समारोह के साथ एक हस्ताक्षरित ग्राफ के बीच का अंतर (जैसा कि § हस्ताक्षरित ग्राफ # हताशा में है) यह है कि पूर्व में वर्टेक्स संकेत आवश्यक संरचना का हिस्सा हैं, जबकि एक राज्य फ़ंक्शन हस्ताक्षरित पर एक चर फ़ंक्शन है ग्राफ।
=== डेटा गुच्छन ===
सहसंबंध गुच्छन समानता द्वारा डेटा के प्राकृतिक गुच्छन के रूप में है। डेटा बिंदुओं को एक आलेख के कोने के रूप में दर्शाया जाता है, जिसमें समान वस्तुओं को जोड़ने वाले एक धनात्मक किनारे और असमान वस्तुओं को जोड़ने वाले एक ऋणात्मक किनारे होते है।


ध्यान दें कि [[चिह्नित ग्राफ]] शब्द [[पेट्री नेट]] में व्यापक रूप से एक पूरी तरह से अलग अर्थ में उपयोग किया जाता है; चिह्नित रेखांकन पर लेख देखें।
===तंत्रिका विज्ञान===
मस्तिष्क को एक सांकेतिक आलेख के रूप में माना जा सकता है जहां मस्तिष्क क्षेत्रों के गतिविधि प्रतिरुप के मध्य एककालता और प्रति एककालता धनात्मक और ऋणात्मक किनारों को निर्धारित करते हैं। इस संबंध में, मस्तिष्क संजाल की स्थिरता और ऊर्जा का पता लगाया जा सकता है।<ref name= 10.1038/s41598-021-81767-7>{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = रेस्टिंग-स्टेट ब्रेन नेटवर्क की स्थिरता पर नकारात्मक लिंक का सामयिक प्रभाव| journal = Scientific Reports | date = January 2021 | volume = 11 | issue = 1 | page = 2176 | pmid = 33500525 | pmc = 7838299 | doi = 10.1038/s41598-021-81767-7 | bibcode = 2021NatSR..11.2176S | url = }</ref> इसके अलावा, हाल ही में, तंत्रिका संयोजन के गैर-तुच्छ संयोजन की पहचान करने और मस्तिष्क के समायोज्य तत्वों को उजागर करने के लिए मस्तिष्क संजाल विश्लेषण में कुंठा की अवधारणा का उपयोग किया गया है।<ref name="https://doi.org/10.1162/netn_a_00268">{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = Pattern of frustration formation in the functional brain network | journal = Network Neuroscience | date = October 2022 | volume = 6 | issue = 4 | page = 1334-1356 | doi = 10.1162/netn_a_00268 | url = https://direct.mit.edu/netn/article/6/4/1334/112207/Pattern-of-frustration-formation-in-the-functional| doi-access = free }}</ref>


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


अधिकतम प्राकृतिक संख्या k पर परिमाण के साथ पूर्णांक के सेट पर वर्टेक्स लेबल को प्रतिबंधित करते समय, एक हस्ताक्षरित ग्राफ़ के उचित रंगों का सेट परिमित होता है। ऐसे उचित रंगों की संख्या और k के बीच का संबंध k में एक बहुपद है; जब के संदर्भ में व्यक्त किया गया <math>2k+1</math> इसे हस्ताक्षरित ग्राफ का [[रंगीन बहुपद]] कहा जाता है। यह एक अहस्ताक्षरित ग्राफ के रंगीन बहुपद के अनुरूप है।


== अनुप्रयोग ==


===[[सामाजिक मनोविज्ञान]]===
सामाजिक मनोविज्ञान में, हस्ताक्षरित रेखांकन का उपयोग सामाजिक स्थितियों को मॉडल करने के लिए किया गया है, सकारात्मक किनारों के साथ दोस्ती का प्रतिनिधित्व करते हैं और नोड्स के बीच नकारात्मक किनारों की दुश्मनी, जो लोगों का प्रतिनिधित्व करते हैं।<ref name=carhar/>फिर, उदाहरण के लिए, एक सकारात्मक 3-चक्र या तो तीन परस्पर मित्र हैं, या एक सामान्य शत्रु वाले दो मित्र हैं; जबकि एक नकारात्मक 3-चक्र या तो तीन परस्पर शत्रु हैं, या दो शत्रु हैं जो एक पारस्परिक मित्र साझा करते हैं। संतुलन सिद्धांत के अनुसार, सकारात्मक चक्र संतुलित होते हैं और इन्हें स्थिर सामाजिक स्थिति माना जाता है, जबकि नकारात्मक चक्र असंतुलित होते हैं और इन्हें अस्थिर माना जाता है। सिद्धांत के अनुसार, तीन पारस्परिक शत्रुओं के मामले में, ऐसा इसलिए है क्योंकि एक साझा शत्रु को साझा करने से मेरे शत्रु का शत्रु मेरा मित्र है। एक दोस्त को साझा करने वाले दो दुश्मनों के मामले में, साझा दोस्त एक दूसरे को चुनने की संभावना रखता है और अपनी दोस्ती में से एक को दुश्मन में बदल देता है।


एंटल, क्रैपीव्स्की और रेडर [[सामाजिक गतिशीलता]] को एक हस्ताक्षरित ग्राफ के किनारे पर साइन इन परिवर्तन के रूप में मानते हैं।<ref>T. Antal, P.L. Krapivsky & S. Redner (2006) [https://arxiv.org/abs/physics/0605183 Social Balance on Networks: The Dynamics of Friendship and Enmity]</ref> एक तलाकशुदा जोड़े के पिछले दोस्तों के साथ सामाजिक संबंधों का उपयोग समाज में एक हस्ताक्षरित ग्राफ के विकास को दर्शाने के लिए किया जाता है। एक अन्य दृष्टांत [[प्रथम विश्व युद्ध]] से पहले के दशकों में यूरोपीय शक्तियों के बीच बदलते अंतरराष्ट्रीय गठजोड़ का वर्णन करता है। वे स्थानीय त्रय गतिकी और विवश त्रय गतिकी पर विचार करते हैं, जहां बाद वाले मामले में एक संबंध परिवर्तन तभी किया जाता है जब असंतुलित त्रय की कुल संख्या कम हो जाती है। सिमुलेशन ने परिवर्तन के लिए चुने गए यादृच्छिक असंतुलित त्रिभुज वाले यादृच्छिक संबंधों के साथ एक पूर्ण ग्राफ माना। इस प्रक्रिया के तहत एन नोड्स के साथ हस्ताक्षरित ग्राफ के विकास का अध्ययन किया जाता है और मैत्रीपूर्ण लिंक के स्थिर घनत्व का वर्णन करने के लिए अनुकरण किया जाता है।


संतुलन सिद्धांत को गंभीर रूप से चुनौती दी गई है, विशेष रूप से बड़ी प्रणालियों के लिए इसके आवेदन में, सैद्धांतिक आधार पर कि मैत्रीपूर्ण संबंध समाज को एक साथ बांधते हैं, जबकि दुश्मनों के दो शिविरों में विभाजित समाज अत्यधिक अस्थिर होगा।<ref>B. Anderson, in ''Perspectives on Social Network Research'', ed. P.W. Holland and S. Leinhardt. New York: Academic Press, 1979.</ref>
प्रायोगिक अध्ययनों ने भी संरचनात्मक संतुलन सिद्धांत की भविष्यवाणियों की केवल कमजोर पुष्टि प्रदान की है।<ref>{{cite journal | last1 = Morrissette | first1 = Julian O. | last2 = Jahnke | first2 = John C. | year = 1967 | title = संरचनात्मक संतुलन के सिद्धांत में शक्ति शून्य का कोई संबंध और संबंध नहीं| journal = Human Relations | volume = 20 | issue = 2| pages = 189–195 | doi = 10.1177/001872676702000207 | s2cid = 143210382 }}</ref>




=== स्पिन चश्मा ===
भौतिकी में, हस्ताक्षरित रेखांकन नॉनफेरोमैग्नेटिक आइसिंग मॉडल के लिए एक प्राकृतिक संदर्भ है, जो स्पिन ग्लास के अध्ययन के लिए लागू होता है।


=== जटिल प्रणाली ===
[[File:Simple 3-level trophic system.png|thumb|right|एक साधारण ट्रॉफिक स्तर का प्रतिनिधित्व करने वाला एक तीन-चर हस्ताक्षरित डिग्राफ]]प्रारंभिक रूप से जनसंख्या जीव विज्ञान और पारिस्थितिकी में विकसित एक विश्लेषणात्मक पद्धति का उपयोग करना, लेकिन अब कई वैज्ञानिक विषयों में उपयोग किया जाता है, हस्ताक्षरित डिग्राफ ने जटिल कारण प्रणालियों के व्यवहार के तर्क में आवेदन पाया है।<ref>Puccia, Charles J. and [[Richard Levins|Levins, Richard]] (1986). ''[http://www.hup.harvard.edu/catalog.php?isbn=9780674435070 Qualitative Modeling of Complex Systems: An Introduction to Loop Analysis and Time Averaging]''. Harvard University Press, Cambridge, MA.</ref><ref>{{cite journal | last1 = Dambacher | first1 = Jeffrey M. | last2 = Li | first2 = Hiram W. | last3 = Rossignol | first3 = Philippe A. | year = 2002 | title = पारिस्थितिक भविष्यवाणियों की अनिश्चितता का आकलन करने में सामुदायिक संरचना की प्रासंगिकता| journal = Ecology | volume = 83 | issue = 5| pages = 1372–1385 | doi = 10.1890/0012-9658(2002)083[1372:rocsia]2.0.co;2 | jstor = 3071950 }}</ref> इस तरह के विश्लेषण सिस्टम के दिए गए स्तरों पर प्रतिक्रिया के बारे में सवालों के जवाब देते हैं, और एक या एक से अधिक बिंदुओं पर एक प्रणाली को दी गई चर प्रतिक्रियाओं की दिशा के बारे में, इस तरह के गड़बड़ी के चर सहसंबंध, सिस्टम में विचरण का वितरण, और संवेदनशीलता या सिस्टम गड़बड़ी के लिए विशेष चर की असंवेदनशीलता।


=== डेटा क्लस्टरिंग ===
सहसंबंध क्लस्टरिंग समानता द्वारा डेटा के प्राकृतिक क्लस्टरिंग की तलाश में है। डेटा बिंदुओं को एक ग्राफ़ के कोने के रूप में दर्शाया जाता है, जिसमें समान वस्तुओं को जोड़ने वाला एक सकारात्मक किनारा और असमान वस्तुओं को जोड़ने वाला एक नकारात्मक किनारा होता है।


===तंत्रिका विज्ञान===
मस्तिष्क को एक हस्ताक्षरित ग्राफ के रूप में माना जा सकता है जहां मस्तिष्क क्षेत्रों के गतिविधि पैटर्न के बीच तुल्यकालन और विरोधी तुल्यकालन सकारात्मक और नकारात्मक किनारों को निर्धारित करते हैं। इस संबंध में, मस्तिष्क नेटवर्क की स्थिरता और ऊर्जा का पता लगाया जा सकता है।<ref name= 10.1038/s41598-021-81767-7>{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = रेस्टिंग-स्टेट ब्रेन नेटवर्क की स्थिरता पर नकारात्मक लिंक का सामयिक प्रभाव| journal = Scientific Reports | date = January 2021 | volume = 11 | issue = 1 | page = 2176 | pmid = 33500525 | pmc = 7838299 | doi = 10.1038/s41598-021-81767-7 | bibcode = 2021NatSR..11.2176S | url = }</ref> साथ ही, हाल ही में, तंत्रिका कनेक्शन के गैर-तुच्छ संयोजन की पहचान करने और मस्तिष्क के समायोज्य तत्वों को उजागर करने के लिए मस्तिष्क नेटवर्क विश्लेषण में हताशा की अवधारणा का उपयोग किया गया है।<ref name= https://doi.org /10.1162/netn_a_00268 >{{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = कार्यात्मक मस्तिष्क नेटवर्क में हताशा गठन का पैटर्न| journal = Network Neuroscience | date = October 2022 | volume = 6 | issue = 4 | page = 1334-1356 | doi = 10.1162/netn_a_00268 | url = https://direct.mit.edu/netn/article/6/4/1334/112207/Pattern-of-frustration-formation-in-the-functional| doi-access = free }}</ref>


== सामान्यीकरण ==
== सामान्यीकरण ==
एक हस्ताक्षरित ग्राफ एक विशेष प्रकार का [[लाभ ग्राफ]] है जिसमें लाभ समूह का क्रम 2 होता है। एक हस्ताक्षरित ग्राफ द्वारा निर्धारित जोड़ी (जी, 'बी' (Σ)) एक विशेष प्रकार का पक्षपाती ग्राफ है। साइन ग्रुप के पास विशेष संपत्ति है, जो बड़े लाभ समूहों द्वारा साझा नहीं की जाती है, कि किनारे के संकेत संतुलित चक्रों के सेट 'बी' (Σ) द्वारा स्विच करने के लिए निर्धारित किए जाते हैं।<ref>{{cite journal
एक सांकेतिक आलेख एक विशेष प्रकार का [[लाभ ग्राफ|लाभ आरेख]] है जिसमें लाभ समूह का क्रम 2 होता है। जोड़ी (''G'', '''''B'''''(Σ)) एक सांकेतिक आलेख Σ द्वारा निर्धारित एक विशेष प्रकार का अभिनत आरेख है। संकेत समूह का विशेष गुण है, जो बड़े लाभ समूहों द्वारा अनुकरण नहीं किया जाता है, संतुलित चक्रों के समुच्चय '''''B'''''(Σ) द्वारा स्विच करने के लिए किनारो के संकेत निर्धारित किए जाते हैं।<ref>{{cite journal
| last1=Zaslavsky | first1=Thomas | authorlink1=Thomas Zaslavsky
| last1=Zaslavsky | first1=Thomas | authorlink1=Thomas Zaslavsky
| title=Characterizations of signed graphs
| title=Characterizations of signed graphs
Line 113: Line 114:
| pages=401–406
| pages=401–406
| doi=10.1002/jgt.3190050409}}</ref>
| doi=10.1002/jgt.3190050409}}</ref>
==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist}}
{{reflist}}
Line 122: Line 121:
*{{citation
*{{citation
  | last1 = Cartwright | first1 = D.
  | last1 = Cartwright | first1 = D.
  | last2 = Harary | first2 = F. | author2-link = Frank Harary
  | last2 = हरारी | first2 = F. | author2-link = फ्रैंक हैरी
  | journal = Psychological Review
  | journal = मनोवैज्ञानिक समीक्षा
  | pages = 277–293
  | pages = 277–293
  | title = Structural balance: a generalization of Heider's theory
  | title = संरचनात्मक संतुलन: हीडर के सिद्धांत का एक सामान्यीकरण
  | volume = 63
  | volume = 63
  | issue = 5
  | issue = 5
Line 131: Line 130:
  }}.
  }}.
*{{citation
*{{citation
  | last = Seidel | first = J. J.
  | last = साइडेल | first = J. J.
  | contribution = A survey of two-graphs
  | contribution = दो-ग्राफ का एक सर्वेक्षण
  | location = Rome
  | location = रोम
  | mr = 0550136
  | mr = 0550136
  | pages = 481–511
  | pages = 481–511
  | series = Atti dei Convegni Lincei
  | series = अट्टी देई कन्वेग्नी लिंसी
  | volume = 17
  | volume = 17
  | publisher = [[Accademia Nazionale dei Lincei]]
  | publisher = [[एकेडेमिया नाजियोनेल देई लिंसी]]
  | title = Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I
  | title = Colloquio Internazionale sulle Teorie Combinatorie (रोम, 1973), टोमो I
  | year = 1976}}.
  | year = 1976}}.
*{{citation
*{{citation
  | last = Zaslavsky | first = Thomas
  | last = ज़स्लावस्की | first = थॉमस
  | journal = Electronic Journal of Combinatorics
  | journal = कॉम्बिनेटरिक्स का इलेक्ट्रॉनिक जर्नल
  | mr = 1744869
  | mr = 1744869
  | at = Dynamic Surveys 8, 124 pp.
  | at = गतिशील सर्वेक्षण 8, 124 पीपी।
  | title = A mathematical bibliography of signed and gain graphs and allied areas
  | title = हस्ताक्षरित और लाभ रेखांकन और संबद्ध क्षेत्रों की एक गणितीय ग्रंथ सूची
  | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS8
  | url = http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS8
  | volume = 5
  | volume = 5
  | year = 1998}}
  | year = 1998}}
[[Category: मैट्रोइड सिद्धांत]] [[Category: रेखांकन का विस्तार और सामान्यीकरण]] [[Category: ओरिएंटेड मैट्रोइड्स]]


[[Category: Machine Translated Page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 08/05/2023]]
[[Category:Created On 08/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with reference errors]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Template documentation pages|Short description/doc]]
[[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 18:04, 18 May 2023

एक त्रिकोण की भुजाओं के लिए चिन्हों को आठ प्रकार से निर्दिष्ट किया जा सकता है। फ्रिट्ज हैडर के सिद्धांत के अनुसार, विषम संख्या में ऋणात्मक चिह्न एक असंतुलित त्रिभुज बनाते हैं।

गणित में आलेख सिद्धांत के क्षेत्र में, सांकेतिक आलेख एक आलेख होता है जिसमें प्रत्येक किनारे पर एक धनात्मक या ऋणात्मक चिह्न होता है।

सांकेतिक आलेख संतुलित होता है यदि प्रत्येक चक्र के किनारे के संकेतों का उत्पाद धनात्मक होता है। ''सांकेतिक आलेख'' नाम और संतुलन की धारणा पहली बार 1953 में फ्रैंक हैरी के एक गणितीय लेख में दिखाई गई है।[1] डेन्स कोनिग ने पहले से ही 1936 में एक अलग शब्दावली के अंतर्गत समतुल्य धारणाओं का अध्ययन किया था, लेकिन चिन्ह समूह की प्रासंगिकता को पहचाने बिना किया था।[2] मिशिगन विश्वविद्यालय में समूह गतिशीलता के केंद्र में, डोरविन कार्टराईट और हैरी ने फ्रिट्ज हैडर के मनोवैज्ञानिक सिद्धांत के त्रिकोण में संतुलन के मनोवैज्ञानिक सिद्धांत को सांकेतिक रेखांकन में संतुलन के मनोवैज्ञानिक सिद्धांत के रूप में सामान्यीकृत किया था।[3][4]

सांकेतिक रेखांकन बहुत बार पुनः खोजे गए हैं क्योंकि वे कई असंबद्ध क्षेत्रों में स्वाभाविक रूप से सामने आते हैं।[5] उदाहरण के लिए, वे प्राचीन मूल प्रक्रिया के उपसमुच्चय की ज्यामिति का वर्णन और विश्लेषण करने में सक्षम होते हैं। वे सांस्थितिक मानचित्र सिद्धांत और समूह सिद्धांत में दिखाई देते हैं। वे आलेख में विषम और सम चक्रों के बारे में प्रश्नों के लिए एक स्वाभाविक संदर्भ देते हैं। वे अलोहचुंबकीय आइसिंग निदर्श में आधार अवस्था ऊर्जा की गणना में दिखाई देते हैं; इसके लिए Σ में सबसे बड़ा संतुलित कोर समुच्चय खोजने की आवश्यकता है। उन्हें सहसंबंध गुच्छन में डेटा वर्गीकरण पर उपयोजित किया गया है।

मूलभूत प्रमेय

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

एक साधारण प्रमाण स्विचिंग की विधि का उपयोग करता है। एक सांकेतिक आलेख को स्विच करने का अर्थ है शीर्ष उपसमुच्चय और उसके पूरक के मध्य सभी किनारों के संकेतों को प्रतिलोम कर देना है। हैरी के प्रमेय को सिद्ध करने के लिए, प्रेरण द्वारा दिखाया गया है कि Σ को सभी धनात्मक होने के लिए स्विच किया जा सकता है अगर यह संतुलित है।

एक मंद प्रमेय, लेकिन एक सरल प्रमाण के साथ, यह है कि यदि सांकेतिक पूर्ण आलेख में प्रत्येक 3-चक्र धनात्मक है, तो आलेख संतुलित है। प्रमाण के लिए, एक स्वेच्छाचारी नोड n का चयन करे और उन सभी नोड्स को रखें जो n से एक समूह में धनात्मक किनारो से शृंखलित होते हैं, जिन्हें A कहा जाता है, और वे सभी जो n से दूसरे में एक ऋणात्मक किनारो से शृंखलित होते हैं, जिन्हें B कहा जाता है। यह एक पूर्ण आरेख है, A में प्रत्येक दो नोड मित्र होने चाहिए और B में प्रत्येक दो नोड मित्र होने चाहिए, अन्यथा एक 3-चक्र होगा जो असंतुलित होगा। (क्योंकि यह एक पूर्ण आरेख है, कोई भी ऋणात्मक किनारा असंतुलित 3-चक्र का कारण होगा।) इसी तरह, सभी ऋणात्मक किनारों को दो समूहों के मध्य जाना चाहिए।[6]

कुंठा

कुंठा सूचकांक

Σ का कुंठा सूचकांक (प्रारंभिक रूप से संतुलन की रेखा सूचकांक कहा जाता है)[7] किनारों की सबसे छोटी संख्या है जिसका विलोपन, या समतुल्य जिसका चिन्ह उत्क्रमण (हैरी का एक प्रमेय[7]), Σ को संतुलित बनाता है। तुल्यता का कारण यह है कि कुंठा सूचकांक किनारों की सबसे छोटी संख्या के समान होता है जिसका निषेध या, समतुल्य, विलोपन; Σ संतुलित बनाता है।

कुंठा सूचकांक का वर्णन करने का दूसरा प्रकार यह है कि यह किनारों की सबसे छोटी संख्या है जो सभी ऋणात्मक चक्रों को समाविष्ट करती है। इस मात्रा को ऋणात्मक चक्र आवरण संख्या कहा गया है।

एक और समतुल्य परिभाषा है (जिसे स्विच करके आसानी से सिद्ध किया जा सकता है)। प्रत्येक शीर्ष को +1 या -1 का मान दें; हम इसे Σ की अवस्था कहते हैं। एक किनारे को संतुष्ट कहा जाता है यदि यह धनात्मक है और दोनों समापन बिंदुओं का मान समान है, या यह ऋणात्मक है और अंत बिंदुओं के विपरीत मान हैं। एक किनारा जो संतुष्ट नहीं होता है उसे कुंठा कहा जाता है। सभी अवस्था में कुंठित किनारों की सबसे छोटी संख्या कुंठा सूचकांक है। यह परिभाषा पहली बार एबेलसन और रोसेनबर्ग द्वारा (अप्रचलित) सम्मिश्रता के अंतर्गत एक अलग संकेतन में प्रस्तावित की गई थी।[8] ऐसे समुच्चय का पूरक सबसे संभावित किनारों के साथ Σ का संतुलित उपआरेख है।

कुंठा सूचकांक खोजना एक NP-कठिन समस्या है। अरेफ एट अल द्विआधारी क्रमादेश निदर्श का सुझाव देते हैं जो उचित समय में 105 किनारों तक आरेख के कुंठा सूचकांक की गणना करने में सक्षम हैं।[9][10][11] कोई भी NP-कठिन सम्मिश्रता देख सकता है कि सभी-ऋणात्मक सांकेतिक आलेख की कुंठा सूचकांक आलेख सिद्धांत में अधिकतम कम समस्या के समान है, जो NP-कठिन है।

प्रचक्रण ग्लास के निदर्श, मिश्रित आइसिंग निदर्श में कुंठा सूचकांक महत्वपूर्ण है। इस निदर्श में, सांकेतिक आलेख निश्चित है। एक स्थिति में प्रत्येक शीर्ष पर "प्रचक्रण", या तो "ऊपर" या "नीचे" सम्मलित है। हम प्रचक्रण ऊपर को +1 और प्रचक्रण नीचे को -1 मानते हैं। इस प्रकार, प्रत्येक अवस्था में कई कुंठित किनारे हैं। एक अवस्था की ऊर्जा तब बड़ी होती है जब उसके पास अधिक कुंठित किनारे होते हैं, इसलिए एक मूल अवस्था सबसे कम कुंठित ऊर्जा वाली अवस्था होती है। इस प्रकार, $$\ $ की मूल अवस्था ऊर्जा का पता लगाने के लिए किसी को कुंठा सूचकांक का पता लगाना होता है।

कुंठा संख्या

अनुरूप शीर्ष संख्या कुंठा संख्या है, जिसे सबसे छोटी संख्या के रूप में परिभाषित किया गया है जिसका Σ से विलोपन संतुलन में होता है। समतुल्य रूप से, कोई Σ के संतुलित प्रेरित उपआरेख का सबसे बड़ा क्रम है।

कलनविधीय समस्याएं

सांकेतिक आलेख के विषय में तीन मूलभूत प्रश्न हैं: क्या यह संतुलित है? इसमें समुच्चय किए गए संतुलित किनारो का सबसे बड़ा आकार क्या है? इसे संतुलित करने के लिए हटाए जाने वाले शीर्षों की सबसे छोटी संख्या क्या है? बहुपद काल में पहले प्रश्न का समाधान करना आसान है। दूसरे प्रश्न को कुंठा सूचकांक या अधिकतम संतुलित उपआरेख समस्या कहा जाता है। यह NP-कठिन है क्योंकि इसका विशेष प्रकरण (जब आरेख के सभी किनारे ऋणात्मक हैं) NP-कठिन समस्या की अधिकतम कटौती है। तीसरे प्रश्न को कुंठा संख्या या अधिकतम संतुलित प्रेरित उपआरेख समस्या कहा जाता है, यह NP-कठिन भी है; उदाहरण देखें[12]

मैट्रोइड सिद्धांत

एक सांकेतिक आलेख से जुड़े दो मैट्रोइड्स हैं, जिन्हें चिन्ह-आलेखिक मैट्रॉइड कहा जाता है (जिसे फ़्रेम मैट्रॉइड या कभी-कभी अभिनति मैट्रोइड भी कहा जाता है) और लिफ्ट मैट्रोइड, जो दोनों एक आलेख के चक्र मैट्रॉइड को सामान्य करते हैं। वे अभिनत आरेख के समान मैट्रोइड्स के विशेष प्रकरण हैं।

'फ़्रेम मेट्रॉइड' (या 'चिन्ह-आलेखिक मैट्रॉइड') M(G) ने इसके आधार समुच्चय कोर समुच्चय E के लिए है।[13] एक कोर समुच्चय स्वतंत्र होता है यदि प्रत्येक घटक में या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। (मैट्रोइड सिद्धांत में एक अर्ध-कोर यथार्थत: ऋणात्मक लूप की तरह काम करता है।) मैट्रॉइड का एक परिपथ या तो एक धनात्मक वृत्त होता है, या एक संयोजक सामान्य पथ के साथ ऋणात्मक वृत्त का एक जोड़ होता है, जैसे कि दो वृत्त या तो अलग हो जाते हैं (फिर संयोजक पथ में प्रत्येक वृत्त के साथ सामान्य एक अंत होता है और अन्यथा दोनों से अलग होता है) या केवल एक सामान्य शीर्ष अनुकरण (इस प्रकरण में संयोजक पथ वह एकल शीर्ष है) करते है। कोर समुच्चय S की कोटि n - b है, जहाँ n, G के शीर्षों की संख्या है और b, S के संतुलित घटकों की संख्या है, पृथक शीर्षों को संतुलित घटकों के रूप में गिना जाता है। यह मेट्रॉइड सांकेतिक आलेख के आपतन आव्यूह का स्तंभ मेट्रॉइड है। यही कारण है कि यह प्राचीन मूल तंत्र की मूलांश की रैखिक निर्भरताओं का वर्णन करता है।

'विस्तारित लिफ्ट मैट्रॉइड' L0(G) ने अपने आधार के लिए समुच्चय E0 को कोर समुच्चय E के एक अतिरिक्त बिंदु के साथ समुच्चय किया है, जिसे हम e0 से निरूपित करते है। लिफ्ट मैट्रॉइड L(G) E तक सीमित विस्तारित लिफ्ट मैट्रॉइड है। अतिरिक्त बिंदु यथार्थत: ऋणात्मक लूप की तरह फलन करता है, इसलिए हम केवल लिफ्ट मैट्रॉइड का वर्णन करते हैं। एक कोर का समुच्चय स्वतंत्र होता है यदि इसमें या तो कोई वृत्त नहीं होता है या केवल एक वृत्त होता है, जो ऋणात्मक होता है। (यह वही नियम है जो सांकेतिक-आलेखिक मैट्रोइड में प्रत्येक घटक के लिए अलग से उपयोजित होता है।) एक मैट्रॉइड परिपथ या तो एक धनात्मक वृत्त या ऋणात्मक वृत्तों का एक जोड़ होता है जो या तो अलग हैं या केवल सामान्य शीर्ष है। कोर समुच्चय S की श्रेणी n - c + ε है, जहां c वियुक्त शीर्षों की गणना करते हुए S के घटकों की संख्या है, और ε 0 है यदि S संतुलित है और 1 यदि यह संतुलित नहीं है।

अन्य प्रकार के सांकेतिक आलेख

कभी-कभी संकेतों को +1 और -1 मान लिया जाता है। यह केवल अंकन का अंतर है, यदि संकेतों को अभी भी एक वृत्त के चारों ओर गुणा किया जाता है और गुणनफल का चिह्न महत्वपूर्ण है। हालांकि, किनारो के लेबल का उपचारण करने के दो अन्य प्रकार हैं जो सांकेतिक आलेख सिद्धांत में उपयुक्त नहीं होते हैं।

सांकेतिक आलेख शब्द को कभी-कभी आलेख पर उपयोजित किया जाता है जिसमें प्रत्येक किनारे का भार, w(e) = +1 या -1 होता है। ये एक ही प्रकार के सांकेतिक आलेख नहीं हैं; वे एक प्रतिबंधित भार समुच्चय के साथ भारित आरेख (असतत गणित) हैं। अंतर यह है कि भार जोड़ा जाता है, गुणा नहीं किया जाता है। समस्याएं और प्रकार पूरी तरह से अलग हैं।

नाम उन आलेखों पर भी उपयोजित होता है जिनमें संकेत किनारों पर रंगों के रूप में फलन करते हैं। रंग का महत्व यह है कि यह किनारे पर लगाए गए विभिन्न भारों को निर्धारित करता है, और ऐसा नहीं है कि इसका चिन्ह आंतरिक रूप से महत्वपूर्ण है। ग्रंथि सिद्धांत में यह स्थिति है, जहाँ संकेतों का केवल महत्व यह है कि उन्हें द्वि-तत्व समूह द्वारा परस्पर बदला जा सकता है, लेकिन धनात्मक और ऋणात्मक के मध्य कोई आंतरिक अंतर नहीं है। सांकेतिक रंग के आलेख का मैट्रोइड अंतर्निहित आलेख का चक्र मैट्रोइड है; यह सांकेतिक आलेख का फ्रेम या लिफ्ट मैट्रॉइड नहीं है। चिन्ह लेबल, मैट्रोइड को बदलने के बदले, मैट्रोइड के तत्वों पर संकेत बन जाता हैं।

इस लेख में हम यथार्थ अर्थों में केवल सांकेतिक आलेख सिद्धांत पर विचार करते हैं। सांकेतिक रंग के आलेख के लिए रंगीन मैट्रोइड् देखें।

सांकेतिक दिशा आरेख

एक सांकेतिक दिशा आरेख सांकेतिक चाप के साथ एक निर्देशित आरेख है। सांकेतिक दिशा आरेख सांकेतिक आलेख की तुलना में कहीं अधिक सम्मिश्र हैं, क्योंकि केवल निर्देशित चक्रों के संकेत ही महत्वपूर्ण हैं। उदाहरण के लिए, संतुलन की कई परिभाषाएँ हैं, जिनमें से प्रत्येक को चित्रित करना कठिन है, सांकेतिक अप्रत्यक्ष रेखांकन की स्थिति के विपरीत हैं।

सांकेतिक द्विलेखों को अभिविन्यस्त के साथ अस्पष्ट नहीं होना चाहिए। उत्तरार्द्ध द्विदिश रेखांकन हैं, निर्देशित रेखांकन नहीं (सभी धनात्मक संकेतों के तुच्छ प्रकरण को छोड़कर) हैं।

शीर्ष संकेत

एक शीर्ष-सांकेतिक आलेख, जिसे कभी-कभी चिह्नित आलेख कहा जाता है, एक आलेख होता है जिसके शीर्षों को संकेत दिए जाते हैं। एक वृत्त को संगत कहा जाता है (लेकिन यह तार्किक स्थिरता से असंबंधित है) या सामंजस्यपूर्ण कहा जाता है यदि इसके शीर्ष संकेतों का गुणनफल धनात्मक है, और भिन्न या असंगत है यदि उत्पाद ऋणात्मक है। हरारी के संतुलन प्रमेय के अनुरूप सामंजस्यपूर्ण शीर्ष-सांकेतिक रेखांकन का कोई सरल लक्षण वर्णन नहीं है; इसके बदले, अभिलक्षण एक कठिन समस्या रही है, जोगलेकर, शाह और दीवान (2012) द्वारा सबसे अच्छा समाधान (और भी सामान्यतः) किया गया है।[14]

प्रमुख परिवर्तन के बिना शीर्ष संकेतों के सिद्धांत में किनारो के संकेतों को जोड़ना प्रायः आसान होता है; इस प्रकार, शीर्ष-सांकेतिक आलेख (या चिह्नित सांकेतिक आलेख) के लिए कई परिणाम स्वाभाविक रूप से शीर्ष-और-किनारे-सांकेतिक आलेख तक विस्तारित होते हैं। जोगलेकर, शाह और दीवान (2012) द्वारा सद्भाव के अभिलक्षणन वर्णन के लिए यह विशेष रूप से सत्य है।

एक चिह्नित सांकेतिक आलेख और एक अवस्था फलन के साथ एक सांकेतिक आलेख के मध्य का अंतर (§ कुंठा के रूप में) यह है कि पूर्व में शीर्ष संकेत आवश्यक संरचना का भाग हैं, जबकि एक अवस्था फलन सांकेतिक आलेख पर एक चर फलन है।

ध्यान दें कि ''चिह्नित आरेख'' शब्द का व्यापक रूप से पेट्री नेट में पूरी तरह से अलग अर्थ में उपयोग किया जाता है; चिह्नित रेखांकन पर लेख देखें।

रंग

असांकेतिक आलेख सिद्धांत के साथ, सांकेतिक आलेख रंग की एक धारणा है। जहाँ आलेख का रंग शीर्ष समुच्चय से प्राकृतिक संख्याओं तक मानचित्रण होता है, एक सांकेतिक आलेख का रंग शीर्ष समुच्चय से पूर्णांकों तक मानचित्रण होता है। उचित रंगों पर प्रतिबंध सांकेतिक आलेख के किनारों से आते हैं। दो शीर्षों के निर्दिष्ट पूर्णांक भिन्न होने चाहिए यदि वे एक धनात्मक किनारो से जुड़े होते है। यदि कोने ऋणात्मक किनारे से जुड़े हुए हैं, तो आसन्न कोने पर लेबल योगात्मक व्युत्क्रम नहीं होना चाहिए। धनात्मक लूप के साथ सांकेतिक आलेख का कोई उचित रंग नहीं हो सकता है।

अधिकतम प्राकृतिक संख्या k पर परिमाण के साथ पूर्णांक के समुच्चय पर शीर्ष लेबल को प्रतिबंधित करते समय, एक सांकेतिक आलेख के उचित रंगों का समुच्चय परिमित होता है। ऐसे उचित रंगों की संख्या और k के मध्य का संबंध k में एक बहुपद है; जब इसे के संदर्भ में व्यक्त किया गया है तो इसे सांकेतिक आलेख का रंगीन बहुपद कहा जाता है। यह एक असांकेतिक आलेख के रंगीन बहुपद के अनुरूप है।

अनुप्रयोग

सामाजिक मनोविज्ञान

सामाजिक मनोविज्ञान में, सांकेतिक रेखांकन का उपयोग सामाजिक स्थितियों को निदर्श करने के लिए किया गया है, धनात्मक किनारों के साथ दोस्ती का प्रतिनिधित्व करते हैं और नोड्स के मध्य ऋणात्मक किनारों के द्वेष, जो लोगों का प्रतिनिधित्व करते हैं।[3] फिर, उदाहरण के लिए, एक धनात्मक 3-चक्र या तो तीन परस्पर मित्र हैं, या एक सामान्य शत्रु वाले दो मित्र हैं; जबकि एक ऋणात्मक 3-चक्र या तो तीन परस्पर शत्रु हैं, या दो शत्रु हैं जो एक अन्योन्य मित्र अनुकरण करते हैं। संतुलन सिद्धांत के अनुसार, धनात्मक चक्र संतुलित होते हैं और इन्हें स्थिर सामाजिक स्थिति माना जाता है, जबकि ऋणात्मक चक्र असंतुलित होते हैं और इन्हें अस्थिर माना जाता है। सिद्धांत के अनुसार, तीन अन्योन्य शत्रुओं के प्रकरण में, ऐसा इसलिए है क्योंकि एक सामान्य शत्रु को अनुकरण करने से दो शत्रुओं के मित्र बनने की संभावना होती है। एक मित्र को अनुकरण करने वाले दो शत्रुओं के प्रकरण में, अनुकरण मित्र एक दूसरे को चयन करने की संभावना रखते है और अपनी दोस्ती में से एक को शत्रु में बदल देते है।

एंटल, क्रैपीव्स्की और रेडर सामाजिक गतिशीलता को एक सांकेतिक आलेख के किनारे पर चिन्ह इन परिवर्तन के रूप में मानते हैं।[15] एक तलाकशुदा जोड़े के पिछले दोस्तों के साथ सामाजिक संबंधों का उपयोग समाज में एक सांकेतिक आलेख के विकास को दर्शाने के लिए किया जाता है। एक अन्य दृष्टांत प्रथम विश्व युद्ध से पहले के दशकों में यूरोपीय शक्तियों के मध्य बदलते अंतरराष्ट्रीय समझौते का वर्णन करता है। वे स्थानीय त्रय गतिकी और विवश त्रय गतिकी पर विचार करते हैं, जहां बाद वाले प्रकरण में एक संबंध परिवर्तन तभी किया जाता है जब असंतुलित त्रय की कुल संख्या कम हो जाती है। अनुकरण ने परिवर्तन के लिए चयन किए गए यादृच्छिक असंतुलित त्रिभुज वाले यादृच्छिक संबंधों के साथ एक पूर्ण आरेख माना जाता है। इस प्रक्रिया के अंतर्गत N नोड्स के साथ सांकेतिक आलेख के विकास का अध्ययन किया जाता है और उपयोगी लिंक के स्थिर घनत्व का वर्णन करने के लिए अनुकरण किया जाता है।

संतुलन सिद्धांत को गंभीर रूप से चुनौती दी गई है, विशेष रूप से बड़ी प्रणालियों के लिए इसके आवेदन में, सैद्धांतिक आधार पर कि उपयोगी संबंध समाज को एक साथ बांधते हैं, जबकि शत्रु के दो कैंप में विभाजित समाज अत्यधिक अस्थिर होते है।[16] प्रायोगिक अध्ययनों ने भी संरचनात्मक संतुलन सिद्धांत की भविष्यवाणियों की केवल कमजोर पुष्टि प्रदान की है।[17]

प्रचक्रण ग्लास

भौतिकी में, सांकेतिक रेखांकन अलोहचुंबकीय आइसिंग निदर्श के लिए एक प्राकृतिक संदर्भ है, जो प्रचक्रण ग्लास के अध्ययन के लिए उपयोजित होता है।

सम्मिश्र पद्धति

एक साधारण पोषी स्तर का प्रतिनिधित्व करने वाला एक तीन-चर सांकेतिक दिशा आरेख

प्रारंभिक रूप से जनसंख्या जीव विज्ञान और पारिस्थितिकी में विकसित एक विश्लेषणात्मक पद्धति का उपयोग करना, लेकिन अब कई वैज्ञानिक विषयों में उपयोग किया जाता है, सांकेतिक दिशा आरेख ने सम्मिश्र कारण प्रणालियों के व्यवहार के तर्क में आवेदन पाया है।[18][19] इस तरह के विश्लेषण पद्धति के दिए गए स्तरों पर प्रतिक्रिया के बारे में प्रश्नो के उत्तर देते हैं, और एक या एक से अधिक बिंदुओं पर एक पद्धति को दी गई चर प्रतिक्रियाओं की दिशा के बारे में, इस तरह के क्षोभ के चर सहसंबंध, पद्धति में विचरण का वितरण, और संवेदनशीलता या पद्धति क्षोभ के लिए विशेष चर की असंवेदनशीलता देते हैं।

डेटा गुच्छन

सहसंबंध गुच्छन समानता द्वारा डेटा के प्राकृतिक गुच्छन के रूप में है। डेटा बिंदुओं को एक आलेख के कोने के रूप में दर्शाया जाता है, जिसमें समान वस्तुओं को जोड़ने वाले एक धनात्मक किनारे और असमान वस्तुओं को जोड़ने वाले एक ऋणात्मक किनारे होते है।

तंत्रिका विज्ञान

मस्तिष्क को एक सांकेतिक आलेख के रूप में माना जा सकता है जहां मस्तिष्क क्षेत्रों के गतिविधि प्रतिरुप के मध्य एककालता और प्रति एककालता धनात्मक और ऋणात्मक किनारों को निर्धारित करते हैं। इस संबंध में, मस्तिष्क संजाल की स्थिरता और ऊर्जा का पता लगाया जा सकता है।[20] इसके अलावा, हाल ही में, तंत्रिका संयोजन के गैर-तुच्छ संयोजन की पहचान करने और मस्तिष्क के समायोज्य तत्वों को उजागर करने के लिए मस्तिष्क संजाल विश्लेषण में कुंठा की अवधारणा का उपयोग किया गया है।[21]







सामान्यीकरण

एक सांकेतिक आलेख एक विशेष प्रकार का लाभ आरेख है जिसमें लाभ समूह का क्रम 2 होता है। जोड़ी (G, B(Σ)) एक सांकेतिक आलेख Σ द्वारा निर्धारित एक विशेष प्रकार का अभिनत आरेख है। संकेत समूह का विशेष गुण है, जो बड़े लाभ समूहों द्वारा अनुकरण नहीं किया जाता है, संतुलित चक्रों के समुच्चय B(Σ) द्वारा स्विच करने के लिए किनारो के संकेत निर्धारित किए जाते हैं।[22]

टिप्पणियाँ

  1. 1.0 1.1 Harary, Frank (1955), "On the notion of balance of a signed graph", Michigan Mathematical Journal, 2: 143–146, MR 0067468, archived from the original on 2013-04-15
  2. Kőnig, Dénes (1936), Akademische Verlagsgesellschaft (ed.), Theorie der endlichen und unendlichen Graphen
  3. 3.0 3.1 Cartwright, D.; Harary, Frank (1956). "Structural balance: a generalization of Heider's theory" (PDF). Psychological Review. 63 (5): 277–293. doi:10.1037/h0046049. PMID 13359597.
  4. Steven Strogatz (2010), The enemy of my enemy, The New York Times, February 14, 2010
  5. Zaslavsky, Thomas (1998), "A mathematical bibliography of signed and gain graphs and allied areas", Electronic Journal of Combinatorics, 5, Dynamic Surveys 8, 124 pp., MR 1744869.
  6. Luis Von Ahn Science of the Web Lecture 3 p. 28
  7. 7.0 7.1 Harary, Frank (1959), On the measurement of structural balance, Behavioral Science 4, 316–323.
  8. Robert P. Abelson; Milton J. Rosenberg (1958), Symbolic psycho-logic: a model of attitudinal cognition, Behavioral Science 3, 1–13.
  9. Aref, Samin; Mason, Andrew J.; Wilson, Mark C. (2019). "हस्ताक्षरित नेटवर्क में हताशा सूचकांक का एक मॉडलिंग और कम्प्यूटेशनल अध्ययन". arXiv:1611.09030 [cs.SI].
  10. Aref, Samin; Mason, Andrew J.; Wilson, Mark C. (2018), Goldengorin, Boris (ed.), "Computing the Line Index of Balance Using Integer Programming Optimisation", Optimization Problems in Graph Theory: In Honor of Gregory Z. Gutin's 60th Birthday, Springer Optimization and Its Applications (in English), Springer International Publishing, pp. 65–84, arXiv:1710.09876, doi:10.1007/978-3-319-94830-0_3, ISBN 9783319948300, S2CID 27936778
  11. Aref, Samin; Wilson, Mark C (2019-04-01). Estrada, Ernesto (ed.). "हस्ताक्षरित नेटवर्क में संतुलन और हताशा". Journal of Complex Networks (in English). 7 (2): 163–189. arXiv:1712.04628. doi:10.1093/comnet/cny015. ISSN 2051-1329.
  12. Gülpinar, N.; Gutin, G.; Mitra, G.; Zverovitch, A. (2004). "हस्ताक्षरित रेखांकन का उपयोग करके रैखिक कार्यक्रमों में शुद्ध नेटवर्क सबमैट्रिसेस निकालना". Discrete Appl. Math. 137 (3): 359–372. doi:10.1016/S0166-218X(03)00361-5.
  13. Zaslavsky, Thomas (1982), "Signed graphs", Discrete Applied Mathematics, 4 (1): 47–74, doi:10.1016/0166-218X(82)90033-6, hdl:10338.dmlcz/127957, MR 0676405. Erratum. Discrete Applied Mathematics, 5 (1983), 248
  14. Manas Joglekar, Nisarg Shah, and Ajit A. Diwan (2012), "Balanced group labeled graphs", Discrete Mathematics, vol. 312, no. 9, pp. 1542–1549.
  15. T. Antal, P.L. Krapivsky & S. Redner (2006) Social Balance on Networks: The Dynamics of Friendship and Enmity
  16. B. Anderson, in Perspectives on Social Network Research, ed. P.W. Holland and S. Leinhardt. New York: Academic Press, 1979.
  17. Morrissette, Julian O.; Jahnke, John C. (1967). "संरचनात्मक संतुलन के सिद्धांत में शक्ति शून्य का कोई संबंध और संबंध नहीं". Human Relations. 20 (2): 189–195. doi:10.1177/001872676702000207. S2CID 143210382.
  18. Puccia, Charles J. and Levins, Richard (1986). Qualitative Modeling of Complex Systems: An Introduction to Loop Analysis and Time Averaging. Harvard University Press, Cambridge, MA.
  19. Dambacher, Jeffrey M.; Li, Hiram W.; Rossignol, Philippe A. (2002). "पारिस्थितिक भविष्यवाणियों की अनिश्चितता का आकलन करने में सामुदायिक संरचना की प्रासंगिकता". Ecology. 83 (5): 1372–1385. doi:10.1890/0012-9658(2002)083[1372:rocsia]2.0.co;2. JSTOR 3071950.
  20. {{cite journal | vauthors = Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G | title = रेस्टिंग-स्टेट ब्रेन नेटवर्क की स्थिरता पर नकारात्मक लिंक का सामयिक प्रभाव| journal = Scientific Reports | date = January 2021 | volume = 11 | issue = 1 | page = 2176 | pmid = 33500525 | pmc = 7838299 | doi = 10.1038/s41598-021-81767-7 | bibcode = 2021NatSR..11.2176S | url = }
  21. Saberi M, Khosrowabadi R, Khatibi A, Misic B, Jafari G (October 2022). "Pattern of frustration formation in the functional brain network". Network Neuroscience. 6 (4): 1334-1356. doi:10.1162/netn_a_00268.
  22. Zaslavsky, Thomas (1981). "Characterizations of signed graphs". Journal of Graph Theory. 5 (4): 401–406. doi:10.1002/jgt.3190050409.


संदर्भ