धार संक्षेपण: Difference between revisions
No edit summary |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{short description|Deleting a graph edge and merging its nodes}} | {{short description|Deleting a graph edge and merging its nodes}} | ||
[[Image:Edge contraction with multiple edges.svg|280px|thumb|right|संकेतित शीर्षों के बीच | [[Image:Edge contraction with multiple edges.svg|280px|thumb|right|संकेतित शीर्षों के बीच धार को सिकोड़ना, जिसके परिणामस्वरूप ग्राफ़ बनता है {{math|G / {uv}.}}]]ग्राफ़ सिद्धांत में, '''धार का संक्षेपण''' ग्राफ़ संचालन ऐसा संचालन है, जो ग्राफ़ से धार को हटा देता है, और साथ ही उन दो [[वर्टेक्स (ग्राफ़ सिद्धांत)|शीर्षों(ग्राफ़ सिद्धांत)]] को विलय करता है जो पहले जुड़े हुए थे। [[ ग्राफ लघु |ग्राफ लघु]] के सिद्धांत में धार का संक्षेपण मौलिक क्रिया है। वर्टेक्स पहचान इस संचालन का कम प्रतिबंधात्मक रूप है। | ||
== परिभाषा == | == परिभाषा == | ||
इस प्रकार धार | इस प्रकार धार संक्षेपण संचालन विशेष धार <math>e</math>. के सापेक्ष होता है, किनारा <math>e</math> हटा दिया गया है और इसके दो आपतित शीर्ष <math>u</math> और <math>v</math>, नए शिखर <math>w</math>, में विलीन हो जाते हैं जहां <math>w</math> प्रत्येक संबंधित धार किसी भी <math>u</math> या <math>v</math>. से संबंधित धार को संदर्भित करते हैं। इससे अधिक सामान्य रूप से, यह संचालन समुच्चय के एज पर किया जा सकता है, जिसमें प्रत्येक एज को संक्षेपण किया जाता है (किसी भी क्रम में)।<ref>{{harvnb|Gross|Yellen|1998|loc=p. 264}}</ref> | ||
इस प्रकार परिणामी प्रेरित ग्राफ़ को कभी-कभी <math>G/e</math> लिखा जाता है। (इसके साथ समानता करें <math>G \setminus e</math>, जिसका अर्थ है किनारा हटाना <math>e</math>.) | इस प्रकार परिणामी प्रेरित ग्राफ़ को कभी-कभी <math>G/e</math> लिखा जाता है। (इसके साथ समानता करें <math>G \setminus e</math>, जिसका अर्थ है किनारा हटाना <math>e</math>.) | ||
[[Image:Edge contraction.svg|280px|thumb|right|अनेक | [[Image:Edge contraction.svg|280px|thumb|right|अनेक धार बनाए बिना धार को सिकोड़ना।]]जैसा कि नीचे परिभाषित किया गया है, धार संक्षेपण संचालन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।<ref>Also, [[loop (graph theory)|loops]] may arise when the graph started with multiple edges or, even if the graph was simple, from the repeated application of edge contraction.</ref> चूँकि , कुछ लेखक<ref>{{harvnb|Rosen|2011|loc=p. 664}}</ref> एकाधिक किनारों के निर्माण की अनुमति न दें, जिससे सरल ग्राफ़ पर किए गए धार संक्षेपण सदैव सरल ग्राफ़ उत्पन्न करता है। | ||
===औपचारिक परिभाषा=== | ===औपचारिक परिभाषा=== | ||
मान ले कि <math>G = (V, E)</math> ग्राफ़ (या [[निर्देशित ग्राफ]]) हो जिसमें किनारा <math>e = (u, v)</math> हो साथ <math>u \neq v</math>, फलन <math>f</math> को प्रत्येक शीर्ष को खुद के साथ मैप करता है, <math>V \setminus\{u, v\}</math> के लिए, और अन्यथा नए शीर्ष <math>w</math> पर मैप करता है। किनारा <math>e</math> के संक्षेपण से नया ग्राफ <math>G' = (V', E')</math>, यहाँ <math>V' = (V \setminus\{u, v\})\cup\{w\}</math>, <math>E' = E \setminus \{e\}</math>, और हर किसी के लिए <math>x \in V</math>, <math>x' = f(x)\in V'</math> | मान ले कि <math>G = (V, E)</math> ग्राफ़ (या [[निर्देशित ग्राफ]]) हो जिसमें किनारा <math>e = (u, v)</math> हो साथ <math>u \neq v</math>, फलन <math>f</math> को प्रत्येक शीर्ष को खुद के साथ मैप करता है, <math>V \setminus\{u, v\}</math> के लिए, और अन्यथा नए शीर्ष <math>w</math> पर मैप करता है। किनारा <math>e</math> के संक्षेपण से नया ग्राफ <math>G' = (V', E')</math>, यहाँ <math>V' = (V \setminus\{u, v\})\cup\{w\}</math>, <math>E' = E \setminus \{e\}</math>, और हर किसी के लिए <math>x \in V</math>, <math>x' = f(x)\in V'</math> धार की घटना है <math>e' \in E'</math> यदि और केवल यदि, संगत किनारा, <math>e \in E</math> की घटना <math>x</math> में <math>G</math> में संबंधित है। | ||
===शीर्ष पहचान=== | ===शीर्ष पहचान=== | ||
'''शीर्ष पहचान''' (जिसे कभी-कभी शीर्ष | '''शीर्ष पहचान''' (जिसे कभी-कभी शीर्ष संक्षेपण भी कहा जाता है) इस प्रतिबंध को हटा देती है कि ''संक्षेपण'' घटना धार को साझा करने वाले शीर्षों पर होना चाहिए। (इस प्रकार, धार का संक्षेपण शीर्ष पहचान का विशेष स्थिति है।) संचालन ग्राफ़ में शीर्षों के किसी भी जोड़े (या उपसमुच्चय) पर हो सकता है। दो ''अनुबंधित'' शीर्षों के बीच के किनारों को कभी-कभी हटा दिया जाता है। यदि <math>v</math> और <math>v'</math> के अलग-अलग घटकों के शीर्ष हैं <math>G</math>, तो हम नया ग्राफ़ बना सकते हैं <math>G'</math> पहचान कर <math>v</math> और <math>v'</math> में <math>G</math> नये शिखर के रूप में <math>\textbf{v}</math> में <math>G'</math>.<ref>{{harvnb|Oxley|2006|pp=[{{GBurl|puKta1Hdz-8C|p=147}} 147–8 §5.3 Whitney's 2-Isomorphism Theorem]}}</ref> अधिक सामान्यतः , शीर्ष समुच्चय के समुच्चय के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को [[भागफल ग्राफ]] के रूप में जाना जाता है। | ||
===वर्टेक्स क्लीविंग=== | ===वर्टेक्स क्लीविंग=== | ||
'''वर्टेक्स क्लीविंग''', जो वर्टेक्स विभाजन के समान है,उसका का अर्थ है कि शीर्ष को दो अंश में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा संचालन है, चूंकि सामान्यतः पर शीर्ष पहचान के लिए, दो पहचाने गए शीर्षों के आसन्न कोने ही समुच्चय नहीं होते हैं। | '''वर्टेक्स क्लीविंग''', जो वर्टेक्स विभाजन के समान है,उसका का अर्थ है कि शीर्ष को दो अंश में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा संचालन है, चूंकि सामान्यतः पर शीर्ष पहचान के लिए, दो पहचाने गए शीर्षों के आसन्न कोने ही समुच्चय नहीं होते हैं। | ||
===पथ | ===पथ संक्षेपण=== | ||
'''पथ | '''पथ संक्षेपण''' पथ (ग्राफ़ सिद्धांत) में किनारों के समुच्चय पर होता है जो पथ के अंतिम बिंदुओं के बीच एकल किनारा बनाने के लिए ''संकुचित'' होता है। पथ के शीर्षों पर पड़ने वाले किनारों को या तो हटा दिया जाता है, या इच्छानुसार से (या व्यवस्थित रूप से) किसी समापन बिंदु से जोड़ दिया जाता है। | ||
===घुमाना=== | ===घुमाना=== | ||
| Line 25: | Line 25: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
किसी ग्राफ़ में शीर्षों या किनारों की संख्या को सम्मलित करके | किसी ग्राफ़ में शीर्षों या किनारों की संख्या को सम्मलित करके धार और शीर्ष संक्षेपण तकनीक दोनों प्रमाण में मूल्यवान हैं, जहां यह माना जा सकता है कि संपत्ति सभी छोटे ग्राफ़ के लिए है और इसका उपयोग बड़े ग्राफ़ के लिए संपत्ति को सिद्ध करने के लिए किया जा सकता है। | ||
इच्छानुसार से जुड़े ग्राफ़ के विस्तरित तरु की संख्या के लिए पुनरावर्ती सूत्र में | इच्छानुसार से जुड़े ग्राफ़ के विस्तरित तरु की संख्या के लिए पुनरावर्ती सूत्र में धार संक्षेपण का उपयोग किया जाता है,<ref>{{harvnb|Gross|Yellen|1998|loc=p. 264}}</ref>और साधारण ग्राफ के [[रंगीन बहुपद]] के लिए पुनरावृत्ति सूत्र में किया जाता है।<ref>{{harvnb|West|2001|loc=p. 221}}</ref> | ||
संक्षेपण उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को [[चक्रीय निर्देशित ग्राफ]] में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध [[सकर्मक संबंध]] है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के समुच्चय के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे। | |||
अन्य उदाहरण [[वैश्विक ग्राफ रंग रजिस्टर आवंटन]] में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)। | अन्य उदाहरण [[वैश्विक ग्राफ रंग रजिस्टर आवंटन]] में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)। | ||
धार का संक्षेपण का उपयोग 3D मॉडलिंग पैकेजों में (या इसे मॉडलिंग सॉफ़्टवेयर की किसी विशेषता द्वारा) वर्टेक्स गिनती को सतत रूप से कम करने में किया जाता है, जिससे लो-बहुभुज मॉडल बनाने में सहायक होता है। | |||
==यह भी देखें== | ==यह भी देखें== | ||
Latest revision as of 15:20, 8 September 2023
ग्राफ़ सिद्धांत में, धार का संक्षेपण ग्राफ़ संचालन ऐसा संचालन है, जो ग्राफ़ से धार को हटा देता है, और साथ ही उन दो शीर्षों(ग्राफ़ सिद्धांत) को विलय करता है जो पहले जुड़े हुए थे। ग्राफ लघु के सिद्धांत में धार का संक्षेपण मौलिक क्रिया है। वर्टेक्स पहचान इस संचालन का कम प्रतिबंधात्मक रूप है।
परिभाषा
इस प्रकार धार संक्षेपण संचालन विशेष धार . के सापेक्ष होता है, किनारा हटा दिया गया है और इसके दो आपतित शीर्ष और , नए शिखर , में विलीन हो जाते हैं जहां प्रत्येक संबंधित धार किसी भी या . से संबंधित धार को संदर्भित करते हैं। इससे अधिक सामान्य रूप से, यह संचालन समुच्चय के एज पर किया जा सकता है, जिसमें प्रत्येक एज को संक्षेपण किया जाता है (किसी भी क्रम में)।[1]
इस प्रकार परिणामी प्रेरित ग्राफ़ को कभी-कभी लिखा जाता है। (इसके साथ समानता करें , जिसका अर्थ है किनारा हटाना .)
जैसा कि नीचे परिभाषित किया गया है, धार संक्षेपण संचालन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।[2] चूँकि , कुछ लेखक[3] एकाधिक किनारों के निर्माण की अनुमति न दें, जिससे सरल ग्राफ़ पर किए गए धार संक्षेपण सदैव सरल ग्राफ़ उत्पन्न करता है।
औपचारिक परिभाषा
मान ले कि ग्राफ़ (या निर्देशित ग्राफ) हो जिसमें किनारा हो साथ , फलन को प्रत्येक शीर्ष को खुद के साथ मैप करता है, के लिए, और अन्यथा नए शीर्ष पर मैप करता है। किनारा के संक्षेपण से नया ग्राफ , यहाँ , , और हर किसी के लिए , धार की घटना है यदि और केवल यदि, संगत किनारा, की घटना में में संबंधित है।
शीर्ष पहचान
शीर्ष पहचान (जिसे कभी-कभी शीर्ष संक्षेपण भी कहा जाता है) इस प्रतिबंध को हटा देती है कि संक्षेपण घटना धार को साझा करने वाले शीर्षों पर होना चाहिए। (इस प्रकार, धार का संक्षेपण शीर्ष पहचान का विशेष स्थिति है।) संचालन ग्राफ़ में शीर्षों के किसी भी जोड़े (या उपसमुच्चय) पर हो सकता है। दो अनुबंधित शीर्षों के बीच के किनारों को कभी-कभी हटा दिया जाता है। यदि और के अलग-अलग घटकों के शीर्ष हैं , तो हम नया ग्राफ़ बना सकते हैं पहचान कर और में नये शिखर के रूप में में .[4] अधिक सामान्यतः , शीर्ष समुच्चय के समुच्चय के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को भागफल ग्राफ के रूप में जाना जाता है।
वर्टेक्स क्लीविंग
वर्टेक्स क्लीविंग, जो वर्टेक्स विभाजन के समान है,उसका का अर्थ है कि शीर्ष को दो अंश में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा संचालन है, चूंकि सामान्यतः पर शीर्ष पहचान के लिए, दो पहचाने गए शीर्षों के आसन्न कोने ही समुच्चय नहीं होते हैं।
पथ संक्षेपण
पथ संक्षेपण पथ (ग्राफ़ सिद्धांत) में किनारों के समुच्चय पर होता है जो पथ के अंतिम बिंदुओं के बीच एकल किनारा बनाने के लिए संकुचित होता है। पथ के शीर्षों पर पड़ने वाले किनारों को या तो हटा दिया जाता है, या इच्छानुसार से (या व्यवस्थित रूप से) किसी समापन बिंदु से जोड़ दिया जाता है।
घुमाना
दो असंयुक्त ग्राफ़ पर विचार करें और , यहाँ शीर्ष सम्मलित हैं और और शीर्ष सम्मलित हैं और . मान लीजिए हम ग्राफ़ प्राप्त कर सकते हैं शीर्षों की पहचान करके का और का शीर्ष के रूप में का और शीर्षों की पहचान करना का और का शीर्ष के रूप में का . घुमाव में का शीर्ष समुच्चय के संबंध में , हम पहचानते हैं, इसके अतिरिक्त, साथ और साथ .के साथ पहचानते हैं।[5]
अनुप्रयोग
किसी ग्राफ़ में शीर्षों या किनारों की संख्या को सम्मलित करके धार और शीर्ष संक्षेपण तकनीक दोनों प्रमाण में मूल्यवान हैं, जहां यह माना जा सकता है कि संपत्ति सभी छोटे ग्राफ़ के लिए है और इसका उपयोग बड़े ग्राफ़ के लिए संपत्ति को सिद्ध करने के लिए किया जा सकता है।
इच्छानुसार से जुड़े ग्राफ़ के विस्तरित तरु की संख्या के लिए पुनरावर्ती सूत्र में धार संक्षेपण का उपयोग किया जाता है,[6]और साधारण ग्राफ के रंगीन बहुपद के लिए पुनरावृत्ति सूत्र में किया जाता है।[7]
संक्षेपण उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को चक्रीय निर्देशित ग्राफ में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध सकर्मक संबंध है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के समुच्चय के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे।
अन्य उदाहरण वैश्विक ग्राफ रंग रजिस्टर आवंटन में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)।
धार का संक्षेपण का उपयोग 3D मॉडलिंग पैकेजों में (या इसे मॉडलिंग सॉफ़्टवेयर की किसी विशेषता द्वारा) वर्टेक्स गिनती को सतत रूप से कम करने में किया जाता है, जिससे लो-बहुभुज मॉडल बनाने में सहायक होता है।
यह भी देखें
टिप्पणियाँ
- ↑ Gross & Yellen 1998, p. 264
- ↑ Also, loops may arise when the graph started with multiple edges or, even if the graph was simple, from the repeated application of edge contraction.
- ↑ Rosen 2011, p. 664
- ↑ Oxley 2006, pp. 147–8 §5.3 Whitney's 2-Isomorphism Theorem
- ↑ Oxley 2006, p. 148
- ↑ Gross & Yellen 1998, p. 264
- ↑ West 2001, p. 221
संदर्भ
- Gross, Jonathan; Yellen, Jay (1998), Graph Theory and its applications, CRC Press, ISBN 0-8493-3982-0
- Oxley, James (2006) [1992], Matroid Theory, Oxford University Press, ISBN 978-0-19-920250-8
- Rosen, Kenneth (2011), Discrete Mathematics and Its Applications (7th ed.), McGraw-Hill, ISBN 978-0-07-338309-5
- West, Douglas B. (2001), Introduction to Graph Theory (2nd ed.), Prentice-Hall, ISBN 0-13-014400-2
