लाभ ग्राफ
एक लाभ ग्राफ एक ग्राफ (असतत गणित) है जिसके किनारों को एक समूह (गणित) जी के तत्वों द्वारा उल्टे या उन्मुख रूप से लेबल किया जाता है। इसका मतलब यह है कि, यदि एक किनारे e में एक दिशा में लेबल g (एक समूह तत्व) है, तो दूसरी दिशा में इसका लेबल g है-1. इसलिए लेबल फ़ंक्शन φ में संपत्ति है कि इसे किनारे ई के दो अलग-अलग झुकावों या दिशाओं पर अलग-अलग परिभाषित किया गया है, लेकिन स्वतंत्र रूप से नहीं। समूह G को 'लाभ समूह' कहा जाता है, φ 'लाभ फलन' है, और मान φ(e) e का 'लाभ' है (कुछ संकेतित दिशा में)। एक लाभ ग्राफ एक हस्ताक्षरित ग्राफ का सामान्यीकरण है, जहां लाभ समूह G में केवल दो तत्व होते हैं। ज़स्लावस्की (1989, 1991) देखें।
लाभ को किनारे पर 'वजन' के साथ भ्रमित नहीं होना चाहिए, जिसका मूल्य किनारे के उन्मुखीकरण से स्वतंत्र है।
अनुप्रयोग
गेन ग्राफ़ में दिलचस्पी लेने के कुछ कारण संयोजन सिद्धांत, ज्यामिती और भौतिकी में नेटवर्क सिद्धांत प्रवाहित करने के लिए उनके कनेक्शन हैं।
- लाभ या सामान्यीकृत नेटवर्क प्रवाह नेटवर्क का गणित, लाभ ग्राफ के पक्षपाती ग्राफ से जुड़ा होता है।
- मान लीजिए हमारे पास R में कुछ hyperplane हैंn x के रूप के समीकरणों द्वारा दिया गयाj= जी एक्सi. निम्नलिखित लाभ ग्राफ का उपयोग करके हाइपरप्लेन की ज्यामिति का इलाज किया जा सकता है: वर्टेक्स सेट {1,2,...,n} है। समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ एक बढ़त ij हैj = जी एक्सi. इन हाइपरप्लेन का उपचार गेन ग्राफ के फ्रेम मैट्रॉइड के माध्यम से किया जाता है (ज़स्लावस्की 2003)।
- या, मान लें कि हमारे पास एक्स के रूप के समीकरणों द्वारा दिए गए हाइपरप्लेन हैंj= एक्सi+ जी। समीकरण x के साथ प्रत्येक हाइपरप्लेन के लिए लाभ g (i से j की दिशा में) के साथ एक ही शीर्ष सेट और एक किनारे ij के साथ लाभ ग्राफ का उपयोग करके इन हाइपरप्लेन की ज्यामिति का इलाज किया जा सकता है।j= एक्सi+ जी। इन हाइपरप्लेन का अध्ययन गेन ग्राफ के पक्षपाती ग्राफ (ज़स्लावस्की 2003) के माध्यम से किया जाता है।
- मान लीजिए कि लाभ समूह के पास एक सेट क्यू पर एक समूह क्रिया (गणित) है। एक तत्व एस असाइन करनाiप्रत्येक शीर्ष पर क्यू का लाभ ग्राफ का 'राज्य' देता है। एक किनारा 'संतुष्ट' है, यदि प्रत्येक किनारे के लिए लाभ जी के साथ (i से j की दिशा में), समीकरण sj= एसiजी संतुष्ट है; अन्यथा यह 'निराश' है। एक राज्य संतुष्ट है अगर हर किनारा संतुष्ट है। भौतिकी में यह एक जमीनी अवस्था (न्यूनतम ऊर्जा की स्थिति) से मेल खाती है, यदि ऐसा राज्य मौजूद है। भौतिकी में एक महत्वपूर्ण समस्या, विशेष रूप से स्पिन ग्लास के सिद्धांत में, सबसे कम कुंठित किनारों वाली अवस्था का निर्धारण करना है।
संबंधित अवधारणाएं
सतहों में ग्राफ एम्बेडिंग के निर्माण के साधन के रूप में टोपोलॉजिकल ग्राफ सिद्धांत में उपयोग किए गए ग्राफ को वोल्टेज ग्राफ (सकल 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.
