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

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

एक हस्ताक्षरित आरेख संतुलित होता है यदि हर चक्र के किनारे के संकेतों का उत्पाद धनात्मक होता है। <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>{{citation

  | year = 1998}}.</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" />), Σ को संतुलित बनाता है। तुल्यता का कारण यह है कि हताशा सूचकांक किनारों की सबसे छोटी संख्या के बराबर होता है जिसका निषेध (या, समतुल्य, विलोपन; Σ संतुलित बनाता है।

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

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

हताशा सूचकांक ढूँढना एक एनपी-कठिन समस्या है। अरेफ एट अल। बाइनरी प्रोग्रामिंग निदर्श सुझाएं जो 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>

<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 मानते हैं। इस प्रकार, प्रत्येक राज्य में कई कुंठित किनारे हैं। एक राज्य की ऊर्जा तब बड़ी होती है जब उसके पास अधिक कुंठित किनारे होते हैं, इसलिए एक जमीनी राज्य सबसे कम कुंठित ऊर्जा वाला राज्य होता है। इस प्रकार, $$\ $ की जमीनी स्थिति ऊर्जा का पता लगाने के लिए किसी को निराशा सूचकांक का पता लगाना होगा।

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

हस्ताक्षरित आलेख के बारे में तीन मूलभूत प्रश्न हैं: क्या यह संतुलित है? इसमें समुच्चय किए गए संतुलित किनारे का सबसे बड़ा आकार क्या है? [[ शीर्ष (ग्राफ सिद्धांत) | शीर्ष (आरेख सिद्धांत)]] की सबसे छोटी संख्या क्या है जिसे संतुलित करने के लिए हटाया जाना चाहिए? बहुपद समय में पहला प्रश्न हल करना आसान है। दूसरे प्रश्न को फ्रस्ट्रेशन इंडेक्स या मैक्सिमम बैलेंस्ड सबआरेख समस्या कहा जाता है। यह एनपी-हार्ड है क्योंकि इसका विशेष मामला (जब आरेख के सभी किनारे ऋणात्मक हैं) एनपी-हार्ड प्रॉब्लम मैक्सिमम कट है। तीसरे प्रश्न को निराशा संख्या या अधिकतम संतुलित प्रेरित सबआरेख समस्या कहा जाता है, यह एनपी-हार्ड भी है; उदाहरण देखें<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 ]] कहा जाता है (जिसे फ़्रेम मैट्रॉइड या कभी-कभी बायस मैट्रोइड भी कहा जाता है) और लिफ्ट मैट्रोइड, जो दोनों एक आलेख के चक्र मैट्रॉइड को सामान्य करते हैं। वे [[पक्षपाती ग्राफ|पक्षपाती आरेख]] के समान मैट्रोइड्स के विशेष मामले हैं।

'फ़्रेम मेट्रॉइड' (या 'चिन्ह-आलेखिक मैट्रॉइड') 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 सिद्धांत है।

यही कारण है कि यह प्राचीन रूट सिस्टम की जड़ों की रैखिक निर्भरताओं का वर्णन करता है।

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

== अन्य प्रकार के हस्ताक्षरित आरेख ==

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

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

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

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

===हस्ताक्षरित डिआरेख ===

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

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

एक शीर्ष-हस्ताक्षरित आलेख, जिसे कभी-कभी चिह्नित आलेख कहा जाता है, एक आलेख होता है जिसके शीर्षों को संकेत दिए जाते हैं। एक वृत्त को संगत कहा जाता है (लेकिन यह तार्किक स्थिरता से असंबंधित है) या सामंजस्यपूर्ण कहा जाता है यदि इसके शीर्ष संकेतों का गुणनफल धनात्मक है, और असंगत या धार्मिक है यदि उत्पाद ऋणात्मक है। हरारी के संतुलन प्रमेय के अनुरूप सामंजस्यपूर्ण शीर्ष-हस्ताक्षरित रेखांकन का कोई सरल लक्षण वर्णन नहीं है; इसके बजाय, चरित्र-चित्रण एक कठिन समस्या रही है, जोगलेकर, शाह और दीवान (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) द्वारा सद्भाव के लक्षण वर्णन के लिए यह विशेष रूप से सच है।

एक चिह्नित हस्ताक्षरित आरेख और एक राज्य समारोह के साथ एक हस्ताक्षरित आरेख के मध्य का अंतर (जैसा कि § हस्ताक्षरित आरेख # हताशा में है) यह है कि पूर्व में वर्टेक्स संकेत आवश्यक संरचना का हिस्सा हैं, जबकि एक राज्य फ़ंक्शन हस्ताक्षरित पर एक चर फ़ंक्शन है आरेख।

ध्यान दें कि [[चिह्नित ग्राफ|चिह्नित आरेख]] शब्द [[पेट्री नेट]] में व्यापक रूप से एक पूरी तरह से अलग अर्थ में उपयोग किया जाता ह�