ग्राफ विवरण के लिए ब्रैकेट फॉर्म

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

वर्णित दृष्टिकोण के लेखक सेमीकंडक्टर भौतिकी संस्थान एसबी आरएएस के वरिष्ठ शोधकर्ता हैं Melent'ev। आलेखों के औपचारिक विवरण के लिए एक नई विधि पहली बार 2000 में लेख में प्रस्तुत की गई थी "आलेखों के वर्णन के लिए ब्रेस फॉर्म और टेन्शनिंग कंप्यूटिंग सिस्टम के संरचनात्मक अध्ययन में इसका उपयोग"।

तो क्या बात है?

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

विसंगतियों से बचने के लिए, मैं कुछ अच्छी तरह से ज्ञात परिभाषाएं दूंगा, साथ ही आलेख में उपयोग किए गए ग्राफ़ चित्रों के बारे में बुनियादी जानकारी भी देगा।

ग्राफ G एक ऑर्डर की गई जोड़ी G (V, E) है जिसमें V , वर्टिस या नोड्स का एक बिना सेट है, E किनारों के जोड़े के जोड़े का एक सेट है।

छोर u और v को किनारे का अंत कोने (या बस छोर) कहा जाता है e = {u, v} । रिब, बदले में, इन चोटियों को जोड़ता है। एक ही किनारे के दो अंत वाले छोरों को आसन्न कहा जाता है।

वर्टेक्स v का डिग्री डिग (v) किनारों की संख्या है जिसके लिए यह टर्मिनल है। सीधे शब्दों में कहें, यह ऊपर से निकलने वाले किनारों की संख्या है।

ग्राफ G (V, E) की छवि P (v _i ) कोष्ठक में ग्राफ का वर्णन है, जिसमें से प्रारंभिक बिंदु (कोण शीर्ष) है जो कि शीर्ष v v । V है।

सेट N (w) एक शीर्ष w का वातावरण है जिसमें s (w) = deg (w) कोने हैं।

सेट एम _मैं प्रक्षेपण के ith स्तर पर स्थित कोने का सेट है।

सी _i - प्रोजेक्शन के i- वें स्तर की कुल संख्या।

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



छवि की बेहतर दृश्य धारणा और इसके साथ काम करने की सुविधा के लिए, हम स्तरों के परिमित सेट के रूप में ग्राफ के ब्रैकेट विवरण की संरचना करते हैं। हम प्रारंभिक शीर्ष चुनते हैं (पसंद मनमानी या प्रेरित हो सकती है, हमारे मामले में v ₀ = 0) और इसे स्तर शून्य पर रखें, हम इसके आसन्न कोने को ऊपर 1 स्तर पर और प्रारंभिक एक के दाईं ओर रखेंगे। कोण वर्टेक्स एन (0) = {1, 2, 3} का वातावरण 1 स्तर के कोने का समूह है: M ₁ = {1, 2, 3}, | एम ₁ | = सी ₁ = 3।

0 ^{{1, 2, 3}}

तो, प्रश्न में ग्राफ की छवि के शून्य और पहले स्तरों पर, एक शीर्ष से | वी | = 8 और तीन किनारों से | ई | = 12।

हम दूसरे स्तर पर विवरण जारी रखते हैं। द्वितीय स्तर के समुच्चय का M ₂ सेट C ₁ = 3 सबसेट को मिलाता है जो कि 1 स्तर के तीन शीर्षों के वातावरण के बिना (शीर्ष 0 के तुरंत इन उपसमुच्चय के) हैं:

M ₂ = M ₂₁ U M ₂₂ U M ₂₃ = {4, 5} U {4, 6} U {5, 6} = {4, 5, 6}, C ₂ = 6 के साथ, और | एम ₂ | = ३।

हमें मिलता है:

0 ^{{1 {4, 5} , 2 {4, 6} , 3 {5, 6} }}

सामान्य स्थिति में, 2 के स्तर से शुरू होता है, प्रत्येक बाद का स्तर एक संग्रह है, न कि सेट का एक सेट, क्योंकि इसमें दोहराए जाने वाले तत्व शामिल हो सकते हैं। ध्यान दें कि एम ₁ यू एम ₂ , वी , इसलिए प्रक्षेपण का निर्माण अगले स्तर तक जारी रहना चाहिए।

तीसरे स्तर के सेट एम _{३ के} सेट में ६ उपसमुच्चय होते हैं, जो २ स्तर के संबंधित ६ कोणों के वातावरण होते हैं, जिनमें से प्रत्येक को इस वातावरण के पूर्ववर्ती कोने के सेटों को घटाकर संशोधित किया जाता है:

M ₃ = M ₃₄ ¹ U M ₃₅ ¹ U M ₃₄ ² U M ₃₆ ¹ U M ₃₅ ² U M ₃₆ ²

यहां, निचले सूचकांक का पहला अंक संबंधित प्रक्षेपण स्तर से संबंधित है, दूसरा ग्राफ के शीर्ष को पहचानता है, और ऊपरी सूचकांक प्रक्षेपण के माना स्तर पर एक ही शीर्ष के कई उदाहरणों को अनुक्रमणित करता है। इस तरह से निर्मित प्रक्षेपण से

0 ^{{1 {4 {2, 7} , 5 {3, 7} } , 2 {4 {1, 7} , 6 {3, 7} } , 3 {5 {1, 7} , 6 {2, 7 } } }}

यह देखा जा सकता है कि केवल तीसरे स्तर पर वर्टेक्स 7 दिखाई देता है, पिछले स्तरों के किसी भी सबसेट में शामिल नहीं है: M ₃ = {2, 7} U {3, 7} U {1, 7} U {3, 7} U {1,7} U {2, 7} = {1, 2, 3, 7}। सी ₃ = 12. | एम ₃ | = 4. एकल-पंक्ति संस्करण में समान प्रक्षेपण की रिकॉर्डिंग का रूप है

P ₃ (0) = 0 {1 {4 {2, 7}, 5 {3, 7}}, 2 {4 {1, 7}, 6 {3, 7}}, 3 {5 {1, 7}। , 6 {2, 7}}}।

एक या दूसरे उपसमुच्चय के सामने खुलने वाले कोष्ठक उसके घोंसले के शिकार को इंगित करते हैं, और बंद करने से "को मंजूरी नहीं दी गई" कोष्ठक की संख्या पूर्ववर्तियों के सेट में इस सबसेट के घोंसले के स्तर को निर्धारित करती है। कोण शीर्ष के वंशज (प्रक्षेपण में स्तर संख्या) के सेट में सबसेट का घोंसला स्तर इसी उपसमुच्चय के कोने से इसकी दूरी निर्धारित करता है।

यदि यह इस ग्राफ के सभी कोने और सभी किनारों (आसन्न संबंध) को परिभाषित करता है तो ग्राफ P _k (v _o ) का प्रक्षेपण पूर्ण माना जाता है। उपर्युक्त प्रक्षेपण पी ₃ (0) से यह देखा जा सकता है कि शीर्ष और किनारे की पूर्णता की स्थिति दोनों यहां केवल 3 डिग्री स्तर पर पूरी होती हैं:

M ₀ U M ₁ U M ₂ U M ₃ = V , | M ₀ U M ₁ U M ₂ U M ₃ | = | वी | = 8

E ₀ U E ₁ U E ₂ U E ₃ = E , | E ₀ U E ₁ U E ₂ U E ₃ | = | ई | = 12

ब्रैकेट छवि के कुछ गुण

अनवेटेड ग्राफ की ब्रैकेट छवि के प्रत्येक स्तर में प्रारंभिक शीर्ष से निकलने वाली सभी अनूठी (गैर-दोहराव) सरल श्रृंखलाओं के अंतिम छोरों का एक सेट होता है, जिनकी लंबाई इस स्तर की संख्या के बराबर होती है।

Kth स्तर के कोने के सेट पर विचार करें। निर्दिष्ट सेट में प्रारंभिक शीर्ष से निकलने वाली सभी सरल श्रृंखलाओं के अंत कोने शामिल हैं, जिनकी लंबाई इस स्तर की संख्या के बराबर होती है, जिनमें कोने शामिल हैं जिनकी छवि के प्रारंभिक शीर्ष से दूरी इस स्तर की संख्या के बराबर है। इसमें वे कोने शामिल नहीं हो सकते हैं जिनकी प्रारंभिक शीर्ष से दूरी स्तर संख्या k से अधिक है।

यदि ग्राफ हैमिल्टनियन है, तो इसके वर्टिकल के सेट में ऐसा मौजूद होता है कि शून्य सहित अधिकतम छवि के स्तरों की संख्या ग्राफ के वर्टिकल की संख्या के बराबर होती है।

और इसका उपयोग कैसे करें?

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

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

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

साहित्य

वी। ए। के कार्यों की सूची Melentyeva