सब कुछ का बीजगणित

लिंक की तालिका

सार और 1 परिचय

2 बुनियादी परिभाषाएँ और संकेतन

2.1 सेट

2.2 अनुक्रम

2.3 हस्ताक्षर और बीजगणित और 2.4 श्रेणियाँ

3 मोनोग्राफ और उनकी रूपात्मकता

4 सीमाएं और सहसीमाएं

5 ड्राइंग मोनोग्राफ

6 ग्राफ संरचनाएं और टाइप किए गए मोनोग्राफ

7 सबमोनोग्राफ और आंशिक रूपवाद

8 मोनोग्राफ के बीजगणितीय रूपांतरण

9 एट्रिब्यूटेड टाइप्ड मोनोग्राफ

10 निष्कर्ष और संदर्भ

अमूर्त

मोनोग्राफ असीमित लंबाई के निर्देशित किनारों के साथ ग्राफ जैसी संरचनाएं हैं जो एक दूसरे से स्वतंत्र रूप से सटे हुए हैं। मानक नोड्स को शून्य लंबाई के किनारों के रूप में दर्शाया जाता है। उन्हें मानक ग्राफ़ और कई अन्य जैसे ई-ग्राफ़ या 8-ग्राफ़ के साथ संगत तरीके से खींचा जा सकता है। मोनोग्राफ की श्रेणी ग्राफ़ संरचनाओं की श्रेणियों (मोनाडिक कई-सॉर्ट किए गए हस्ताक्षरों के बीजगणित) के साथ कई गुणों को साझा करती है, सिवाय इसके कि कोई टर्मिनल मोनोग्राफ नहीं है। यह इस अर्थ में सार्वभौमिक है कि इसकी स्लाइस श्रेणियां (या टाइप किए गए मोनोग्राफ की श्रेणियां) ग्राफ़ संरचनाओं की श्रेणियों के बराबर हैं। इस प्रकार टाइप मोनोग्राफ ग्राफ़ संरचनाओं को निर्दिष्ट करने का एक स्वाभाविक तरीका बनकर उभरता है। मोनोग्राफ के एकल और दोहरे पुशआउट परिवर्तनों का विस्तृत विश्लेषण प्रदान किया गया है, और टाइप किए गए एट्रिब्यूटेड ई-ग्राफ़ को सामान्यीकृत करने वाले एट्रिब्यूटेड टाइप किए गए मोनोग्राफ की धारणा का विश्लेषण विशेषता-संरक्षण परिवर्तनों के संबंध में किया गया है।

कीवर्ड : बीजीय ग्राफ परिवर्तन, ग्राफ संरचनाएं, टाइप किए गए ग्राफ

1 परिचय

गणित और कंप्यूटर विज्ञान में ग्राफ की कई अलग-अलग धारणाओं का उपयोग किया जाता है: सरल ग्राफ, निर्देशित ग्राफ, मल्टीग्राफ, हाइपरग्राफ, आदि। तर्क और पुनर्लेखन के संदर्भ में एक पसंदीदा धारणा है जिसे क्विवर के रूप में भी जाना जाता है, यानी, pN, E, s, tq के रूप की संरचनाएँ जहाँ N, E सेट हैं और s, t E (किनारों) से N (नोड्स) तक के फ़ंक्शन हैं, जो हर किनारे (या तीर) के स्रोत और लक्ष्य युक्तियों की पहचान करते हैं। इसका एक कारण यह है कि क्विवर की श्रेणी कई-सॉर्ट किए गए हस्ताक्षर के बीजगणित की श्रेणी के साथ समरूप है जिसमें दो सॉर्ट नोड्स और किनारे और दो ऑपरेटर नाम src और tgt हैं जो किनारे Ñ नोड्स के प्रकार हैं। इस परंपरा के अनुरूप, इस पूरे पेपर में ग्राफ से हमारा मतलब क्विवर है।

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

अधिक सटीक रूप से, ई-ग्राफ एक बीजगणित है जिसका हस्ताक्षर निम्नलिखित ग्राफ द्वारा दर्शाया जा सकता है:

सॉर्ट और ऑपरेटर को दिए गए नाम ई-ग्राफ़ की संरचना को समझने में मदद करते हैं: किनारे आपस में नोड्स को जोड़ते हैं, एनवी-किनारे नोड्स को मानों से जोड़ते हैं, और ईवी-किनारे किनारों को मानों से जोड़ते हैं। इसलिए सॉर्ट मान उन विशेषताओं को धारण करते हैं जो नोड्स भी हैं। लेकिन फिर हम देखते हैं कि ई-ग्राफ़ में ईवी-किनारे किनारों के समीप होते हैं। यह गैर मानक है, लेकिन हम अभी भी इस तरह की संरचनाओं को ग्राफ़ के किसी रूप के रूप में स्वीकार कर सकते हैं, अगर केवल इसलिए कि हम समझते हैं कि उन्हें कैसे खींचा जा सकता है।

इसलिए ग्राफ की धारणा को सामान्य बनाने का तरीका बीजगणित के रूप में माने जाने वाले ग्राफ के हस्ताक्षर के सामान्यीकरण को शामिल करता है। इस मार्ग का अनुसरण माइकल लोवे ने [3] में किया है, जहाँ एक ग्राफ संरचना को मोनाडिक कई-सॉर्टेड हस्ताक्षर के रूप में परिभाषित किया गया है। वास्तव में ऊपर दिए गए उदाहरणों में, और [3] में दिए गए कई उदाहरणों में, सभी ऑपरेटरों की एरिटी 1 है और इसलिए उन्हें उनके डोमेन से लेकर उनके रेंज सॉर्ट तक के किनारों के रूप में माना जा सकता है। क्या यही कारण है कि उन्हें ग्राफ संरचनाएँ कहा जाता है? लेकिन ऊपर दिया गया उदाहरण दिखाता है कि ई-ग्राफ उनके हस्ताक्षर का प्रतिनिधित्व करने वाले ग्राफ से बहुत अलग हैं। इसके अलावा, यह सुविधाजनक नहीं है कि ऐसी संरचनाओं की हमारी समझ वाक्यविन्यास पर आधारित होनी चाहिए, यानी, हस्ताक्षर में सॉर्ट और ऑपरेटरों को दिए गए विशेष नामों पर।

इसके अलावा, यह देखना मुश्किल है कि कुछ बहुत ही सरल मोनाडिक हस्ताक्षरों के बीजगणित को किसी भी रूप के ग्राफ़ के रूप में कैसे व्याख्या किया जा सकता है। उदाहरण के लिए ग्राफ़ के हस्ताक्षर लें और लक्ष्य फ़ंक्शन को tgt पर उलट दें: नोड्स Ñ किनारे। फिर सॉर्ट नोड्स और किनारों के बीच एक समरूपता है, जिसका अर्थ है कि इस हस्ताक्षर के बीजगणित में नोड्स और किनारे एक ही प्रकृति की वस्तुएँ होंगी। क्या यह अभी भी एक ग्राफ़ है? क्या हम इसे खींच सकते हैं? इससे भी बदतर, अगर दो सॉर्ट को एक में समेट दिया जाए, तो क्या इसका मतलब यह है कि एक नोड/किनारा खुद से सटा हो सकता है?

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

यहाँ अपनाया गया दृष्टिकोण नोड्स और किनारों के बीच किसी भी संरचनात्मक अंतर को अस्वीकार करना है, इसलिए नोड्स को लंबाई 0 के किनारों के रूप में और मानक किनारों को लंबाई 2 के किनारों के रूप में एक एकीकृत दृष्टिकोण अपनाना है क्योंकि वे दो नोड्स के समीप हैं। यह एकीकृत दृष्टिकोण तार्किक रूप से किनारों को किसी भी किनारे से सटा होने की अनुमति देता है, न कि केवल नोड्स से, इस प्रकार ई-ग्राफ के ईवी-किनारों को सामान्यीकृत करता है, और यहां तक कि उन किनारों को भी जो स्वयं से सटे हुए हैं। अंत में, किनारों की लंबाई को 0 या 2 तक सीमित करने का कोई कारण नहीं है, और हम अनंत, क्रमिक लंबाई के किनारों को अनुमति देने के लिए (अनुभाग 6 में) अच्छे कारण पाएंगे। आवश्यक धारणाएँ और संकेतन अनुभाग 2 में पेश किए गए हैं। मोनोग्राफ की संरचना (रूपवाद के साथ) अनुभाग 3 में परिभाषित की गई है, जो उनकी कुछ विशेषताओं के अनुसार मोनोग्राफ की श्रेणियों की एक बेस्टियरी प्रदान करती है। सीमाओं और सह-सीमाओं के अस्तित्व के संबंध में इन श्रेणियों के गुणों का विश्लेषण अनुभाग 4 में किया गया है।

फिर हम अनुभाग 5 में देखते हैं कि मोनोग्राफ को रेखाचित्रों द्वारा कैसे सटीक रूप से दर्शाया जा सकता है, बशर्ते कि उनके पास सीमित किनारे हों और उनकी लंबाई सीमित हो। विशेष रूप से, ऐसे रेखाचित्र उन मोनोग्राफ के लिए ग्राफ बनाने के मानक तरीके के अनुरूप होते हैं जिन्हें मानक ग्राफ़ के साथ पहचाना जा सकता है, और इसी तरह ई-ग्राफ़ के लिए भी।

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

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

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

हम धारा 10 में निष्कर्ष निकालते हैं। ध्यान दें कि धारा 4 से 6 के कुछ भाग [4] में प्रकाशित किए गए हैं।