लाभ ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Graph with group-labeled edges}} | {{Short description|Graph with group-labeled edges}} | ||
एक लाभ ग्राफ | एक लाभ ग्राफ [[ग्राफ (असतत गणित)]] है जिसके किनारों को [[समूह (गणित)]] ''G'' के तत्वों द्वारा उल्टे या उन्मुख रूप से लेबल किया जाता है। इसका अर्थ यह है कि, यदि किनारे ''e'' में दिशा में लेबल ''g'' (एक समूह तत्व) है तो दूसरी दिशा में इसका लेबल ''g'' <sup>−1</sup>है इसलिए लेबल कार्य φ में संपत्ति है कि इसे किनारे ''e'' के दो अलग-अलग झुकावों या दिशाओं पर अलग-अलग परिभाषित किया गया है किंतु स्वतंत्र रूप से नहीं। समूह G को 'लाभ समूह' कहा जाता है, φ 'लाभ फलन' है, और मान φ(e) e का 'लाभ' है (कुछ संकेतित दिशा में) लाभ ग्राफ [[हस्ताक्षरित ग्राफ]] का सामान्यीकरण है जहां लाभ समूह G में केवल दो तत्व होते हैं। ज़स्लावस्की (1989, 1991) देखें। | ||
लाभ को किनारे पर 'वजन' के साथ अस्पष्ट नहीं होना चाहिए जिसका मान किनारे के उन्मुखीकरण से स्वतंत्र है। | लाभ को किनारे पर 'वजन' के साथ अस्पष्ट नहीं होना चाहिए जिसका मान किनारे के उन्मुखीकरण से स्वतंत्र है। | ||
| Line 8: | Line 8: | ||
* लाभ या [[सामान्यीकृत नेटवर्क]] [[प्रवाह नेटवर्क]] का गणित, लाभ ग्राफ के [[पक्षपाती ग्राफ]] से जुड़ा होता है। | * लाभ या [[सामान्यीकृत नेटवर्क]] [[प्रवाह नेटवर्क]] का गणित, लाभ ग्राफ के [[पक्षपाती ग्राफ]] से जुड़ा होता है। | ||
* मान लीजिए हमारे पास R<sup>n</sup> में कुछ [[ hyperplane | हाइपरप्लेन]] | * मान लीजिए हमारे पास R<sup>n</sup> में कुछ [[ hyperplane |हाइपरप्लेन]] हैं ''x<sub>j</sub>'' = ''g x<sub>i</sub>'' के रूप के समीकरणों द्वारा दिया गया निम्नलिखित लाभ ग्राफ का उपयोग करके हाइपरप्लेन की ज्यामिति का उपचार किया जा सकता है: वर्टेक्स सेट {1,2,...,n} है। समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ बढ़त ''x<sub>j</sub> = g x<sub>i</sub>'' है इन हाइपरप्लेन का उपचार गेन ग्राफ के फ्रेम मैट्रॉइड के माध्यम से किया जाता है (ज़स्लावस्की 2003) | ||
* या मान लें कि हमारे पास ''x<sub>j</sub>'' = ''x<sub>i</sub>'' + ''g''.के रूप के समीकरणों द्वारा दिए गए हाइपरप्लेन हैं समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ | * या मान लें कि हमारे पास ''x<sub>j</sub>'' = ''x<sub>i</sub>'' + ''g''.के रूप के समीकरणों द्वारा दिए गए हाइपरप्लेन हैं समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ ही शीर्ष सेट और किनारे ij के साथ लाभ ग्राफ का उपयोग करके इन हाइपरप्लेन की ज्यामिति का उपचार किया जा सकता है। ''x<sub>j</sub>'' = ''x<sub>i</sub>'' + ''g''.इन हाइपरप्लेन का अध्ययन गेन ग्राफ के पक्षपाती ग्राफ (ज़स्लावस्की 2003) के माध्यम से किया जाता है। | ||
* मान लीजिए कि लाभ समूह के पास | * मान लीजिए कि लाभ समूह के पास सेट ''Q'' पर [[समूह क्रिया (गणित)]] है। तत्व ''s<sub>i</sub>'' असाइन करना प्रत्येक शीर्ष पर ''Q'' का लाभ ग्राफ का 'अवस्था' देता है। किनारा 'संतुष्ट' है यदि प्रत्येक किनारे के लिए लाभ ''g'' के साथ (i से j की दिशा में) समीकरण ''s<sub>j</sub>'' = ''s<sub>i</sub> g'' संतुष्ट है अन्यथा यह 'निराश' है। अवस्था संतुष्ट है यदि हर किनारा संतुष्ट है। भौतिकी में यह जमीनी अवस्था (न्यूनतम ऊर्जा की स्थिति) से मेल खाती है यदि ऐसा अवस्था उपस्थित है। भौतिकी में महत्वपूर्ण समस्या विशेष रूप से [[स्पिन ग्लास]] के सिद्धांत में सबसे कम कुंठित किनारों वाली अवस्था का निर्धारण करना है। | ||
== संबंधित अवधारणाएं == | == संबंधित अवधारणाएं == | ||
सतहों में [[ग्राफ एम्बेडिंग]] के निर्माण के साधन के रूप में [[टोपोलॉजिकल ग्राफ सिद्धांत]] में उपयोग किए गए ग्राफ को [[वोल्टेज ग्राफ]] (सकल 1974; सकल और टकर 1977) के रूप में जाना जाता है। शब्द लाभ ग्राफ अन्य संदर्भों में अधिक सामान्य है उदाहरण के लिए पक्षपाती ग्राफ सिद्धांत और [[मैट्रोइड सिद्धांत]] समूह-लेबल वाले ग्राफ़ शब्द का भी उपयोग किया गया है किंतु यह अस्पष्ट है क्योंकि समूह लेबल हो सकते हैं - और उन्हें वजन के रूप में माना जाता है। | सतहों में [[ग्राफ एम्बेडिंग]] के निर्माण के साधन के रूप में [[टोपोलॉजिकल ग्राफ सिद्धांत]] में उपयोग किए गए ग्राफ को [[वोल्टेज ग्राफ]] (सकल 1974; सकल और टकर 1977) के रूप में जाना जाता है। शब्द लाभ ग्राफ अन्य संदर्भों में अधिक सामान्य है उदाहरण के लिए पक्षपाती ग्राफ सिद्धांत और [[मैट्रोइड सिद्धांत]] समूह-लेबल वाले ग्राफ़ शब्द का भी उपयोग किया गया है किंतु यह अस्पष्ट है क्योंकि समूह लेबल हो सकते हैं - और उन्हें वजन के रूप में माना जाता है। | ||
चूँकि गेन ग्राफ़ के सिद्धांत का अधिकांश पक्षपाती ग्राफ़ का | चूँकि गेन ग्राफ़ के सिद्धांत का अधिकांश पक्षपाती ग्राफ़ का विशेष स्थिति है (और पक्षपाती ग्राफ़ के सिद्धांत का अधिकांश लाभ ग्राफ़ का सामान्यीकरण है) पाठक को अधिक जानकारी और उदाहरण के लिए पक्षपाती ग्राफ़ पर लेख का उल्लेख करना चाहिए । | ||
==संदर्भ == | ==संदर्भ == | ||
*Jonathan L. Gross (1974), | *Jonathan L. Gross (1974), Voltage graphs. ''Discrete Mathematics'', Vol. 9, pp. 239–246. | ||
*J.L. Gross and T.W. Tucker (1977), | *J.L. Gross and T.W. Tucker (1977), Generating all graph coverings by permutation voltage assignments. ''Discrete Mathematics'', Vol. 18, pp. 273–283. | ||
*[[Thomas Zaslavsky]] (1989), | *[[Thomas Zaslavsky]] (1989), Biased graphs. I. Bias, balance, and gains. ''Journal of Combinatorial Theory, Series B'', Vol. 47, 32–52. | ||
*Thomas Zaslavsky (1991), | *Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. ''Journal of Combinatorial Theory, Series B'', Vol. 51, 46–72. | ||
*Thomas Zaslavsky (1999). | *Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas. [https://web.archive.org/web/20100912123133/http://www.combinatorics.org/Surveys/index.html ''Electronic Journal of Combinatorics'', Dynamic Surveys in Combinatorics, #DS8]. | ||
*Thomas Zaslavsky (2003), | *Thomas Zaslavsky (2003), Biased graphs IV: Geometrical realizations. ''Journal of Combinatorial Theory, Series B'', Vol. 89, no. 2, pp. 231–297. | ||
[[Category: मैट्रोइड सिद्धांत]] [[Category: रेखांकन का विस्तार और सामान्यीकरण]] | [[Category: मैट्रोइड सिद्धांत]] [[Category: रेखांकन का विस्तार और सामान्यीकरण]] | ||
Revision as of 14:52, 31 May 2023
एक लाभ ग्राफ ग्राफ (असतत गणित) है जिसके किनारों को समूह (गणित) G के तत्वों द्वारा उल्टे या उन्मुख रूप से लेबल किया जाता है। इसका अर्थ यह है कि, यदि किनारे e में दिशा में लेबल g (एक समूह तत्व) है तो दूसरी दिशा में इसका लेबल g −1है इसलिए लेबल कार्य φ में संपत्ति है कि इसे किनारे e के दो अलग-अलग झुकावों या दिशाओं पर अलग-अलग परिभाषित किया गया है किंतु स्वतंत्र रूप से नहीं। समूह G को 'लाभ समूह' कहा जाता है, φ 'लाभ फलन' है, और मान φ(e) e का 'लाभ' है (कुछ संकेतित दिशा में) लाभ ग्राफ हस्ताक्षरित ग्राफ का सामान्यीकरण है जहां लाभ समूह G में केवल दो तत्व होते हैं। ज़स्लावस्की (1989, 1991) देखें।
लाभ को किनारे पर 'वजन' के साथ अस्पष्ट नहीं होना चाहिए जिसका मान किनारे के उन्मुखीकरण से स्वतंत्र है।
अनुप्रयोग
गेन ग्राफ़ में रौचक लेने के कुछ कारण संयोजन सिद्धांत ज्यामिती और भौतिकी में नेटवर्क सिद्धांत प्रवाहित करने के लिए उनके कनेक्शन हैं।
- लाभ या सामान्यीकृत नेटवर्क प्रवाह नेटवर्क का गणित, लाभ ग्राफ के पक्षपाती ग्राफ से जुड़ा होता है।
- मान लीजिए हमारे पास Rn में कुछ हाइपरप्लेन हैं xj = g xi के रूप के समीकरणों द्वारा दिया गया निम्नलिखित लाभ ग्राफ का उपयोग करके हाइपरप्लेन की ज्यामिति का उपचार किया जा सकता है: वर्टेक्स सेट {1,2,...,n} है। समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ बढ़त xj = g xi है इन हाइपरप्लेन का उपचार गेन ग्राफ के फ्रेम मैट्रॉइड के माध्यम से किया जाता है (ज़स्लावस्की 2003)
- या मान लें कि हमारे पास xj = xi + g.के रूप के समीकरणों द्वारा दिए गए हाइपरप्लेन हैं समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ ही शीर्ष सेट और किनारे ij के साथ लाभ ग्राफ का उपयोग करके इन हाइपरप्लेन की ज्यामिति का उपचार किया जा सकता है। xj = xi + g.इन हाइपरप्लेन का अध्ययन गेन ग्राफ के पक्षपाती ग्राफ (ज़स्लावस्की 2003) के माध्यम से किया जाता है।
- मान लीजिए कि लाभ समूह के पास सेट Q पर समूह क्रिया (गणित) है। तत्व si असाइन करना प्रत्येक शीर्ष पर Q का लाभ ग्राफ का 'अवस्था' देता है। किनारा 'संतुष्ट' है यदि प्रत्येक किनारे के लिए लाभ g के साथ (i से j की दिशा में) समीकरण sj = si g संतुष्ट है अन्यथा यह 'निराश' है। अवस्था संतुष्ट है यदि हर किनारा संतुष्ट है। भौतिकी में यह जमीनी अवस्था (न्यूनतम ऊर्जा की स्थिति) से मेल खाती है यदि ऐसा अवस्था उपस्थित है। भौतिकी में महत्वपूर्ण समस्या विशेष रूप से स्पिन ग्लास के सिद्धांत में सबसे कम कुंठित किनारों वाली अवस्था का निर्धारण करना है।
संबंधित अवधारणाएं
सतहों में ग्राफ एम्बेडिंग के निर्माण के साधन के रूप में टोपोलॉजिकल ग्राफ सिद्धांत में उपयोग किए गए ग्राफ को वोल्टेज ग्राफ (सकल 1974; सकल और टकर 1977) के रूप में जाना जाता है। शब्द लाभ ग्राफ अन्य संदर्भों में अधिक सामान्य है उदाहरण के लिए पक्षपाती ग्राफ सिद्धांत और मैट्रोइड सिद्धांत समूह-लेबल वाले ग्राफ़ शब्द का भी उपयोग किया गया है किंतु यह अस्पष्ट है क्योंकि समूह लेबल हो सकते हैं - और उन्हें वजन के रूप में माना जाता है।
चूँकि गेन ग्राफ़ के सिद्धांत का अधिकांश पक्षपाती ग्राफ़ का विशेष स्थिति है (और पक्षपाती ग्राफ़ के सिद्धांत का अधिकांश लाभ ग्राफ़ का सामान्यीकरण है) पाठक को अधिक जानकारी और उदाहरण के लिए पक्षपाती ग्राफ़ पर लेख का उल्लेख करना चाहिए ।
संदर्भ
- Jonathan L. Gross (1974), Voltage graphs. Discrete Mathematics, Vol. 9, pp. 239–246.
- J.L. Gross and T.W. Tucker (1977), Generating all graph coverings by permutation voltage assignments. Discrete Mathematics, Vol. 18, pp. 273–283.
- Thomas Zaslavsky (1989), Biased graphs. I. Bias, balance, and gains. Journal of Combinatorial Theory, Series B, Vol. 47, 32–52.
- Thomas Zaslavsky (1991), Biased graphs. II. The three matroids. Journal of Combinatorial Theory, Series B, Vol. 51, 46–72.
- Thomas Zaslavsky (1999). A mathematical bibliography of signed and gain graphs and allied areas. Electronic Journal of Combinatorics, Dynamic Surveys in Combinatorics, #DS8.
- Thomas Zaslavsky (2003), Biased graphs IV: Geometrical realizations. Journal of Combinatorial Theory, Series B, Vol. 89, no. 2, pp. 231–297.
