किनारे का संकुचन: Difference between revisions
(Created page with "{{short description|Deleting a graph edge and merging its nodes}} Image:Edge contraction with multiple edges.svg|280px|thumb|right|संकेतित शीर्षो...") |
No edit summary |
||
| 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|संकेतित शीर्षों के बीच किनारे को सिकोड़ना, जिसके परिणामस्वरूप ग्राफ़ बनता है {{math|G / {uv}.}}]]ग्राफ़ सिद्धांत में, बढ़त संकुचन | [[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>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> अधिक आम तौर पर, शीर्ष सेट के सेट के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को [[भागफल ग्राफ]] के रूप में जाना जाता है। | ||
===वर्टेक्स क्लीविंग=== | ===वर्टेक्स क्लीविंग=== | ||
वर्टेक्स क्लीविंग, जो वर्टेक्स स्प्लिटिंग के समान है, का अर्थ है कि | वर्टेक्स क्लीविंग, जो वर्टेक्स स्प्लिटिंग के समान है, का अर्थ है कि शीर्ष को दो में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा ऑपरेशन है, हालांकि सामान्य तौर पर शीर्ष पहचान के लिए, दो पहचाने गए शीर्षों के आसन्न कोने ही सेट नहीं होते हैं। | ||
===पथ संकुचन=== | ===पथ संकुचन=== | ||
पथ संकुचन पथ (ग्राफ़ सिद्धांत) में किनारों के सेट पर होता है जो पथ के अंतिम बिंदुओं के बीच | पथ संकुचन पथ (ग्राफ़ सिद्धांत) में किनारों के सेट पर होता है जो पथ के अंतिम बिंदुओं के बीच एकल किनारा बनाने के लिए ''संकुचित'' होता है। पथ के शीर्षों पर पड़ने वाले किनारों को या तो हटा दिया जाता है, या मनमाने ढंग से (या व्यवस्थित रूप से) किसी समापन बिंदु से जोड़ दिया जाता है। | ||
===घुमाना=== | ===घुमाना=== | ||
दो असंयुक्त ग्राफ़ पर विचार करें <math>G_1</math> और <math>G_2</math>, कहाँ <math>G_1</math> शीर्ष शामिल हैं <math>u_1</math> और <math>v_1</math> और <math>G_2</math> शीर्ष शामिल हैं <math>u_2</math> और <math>v_2</math>. मान लीजिए हम ग्राफ़ प्राप्त कर सकते हैं <math>G</math> शीर्षों की पहचान करके <math>u_1</math> का <math>G_1</math> और <math>u_2</math> का <math>G_2</math> शीर्ष के रूप में <math>u</math> का <math>G</math> और शीर्षों की पहचान करना <math>v_1</math> का <math>G_1</math> और <math>v_2</math> का <math>G_2</math> शीर्ष के रूप में <math>v</math> का <math>G</math>. | दो असंयुक्त ग्राफ़ पर विचार करें <math>G_1</math> और <math>G_2</math>, कहाँ <math>G_1</math> शीर्ष शामिल हैं <math>u_1</math> और <math>v_1</math> और <math>G_2</math> शीर्ष शामिल हैं <math>u_2</math> और <math>v_2</math>. मान लीजिए हम ग्राफ़ प्राप्त कर सकते हैं <math>G</math> शीर्षों की पहचान करके <math>u_1</math> का <math>G_1</math> और <math>u_2</math> का <math>G_2</math> शीर्ष के रूप में <math>u</math> का <math>G</math> और शीर्षों की पहचान करना <math>v_1</math> का <math>G_1</math> और <math>v_2</math> का <math>G_2</math> शीर्ष के रूप में <math>v</math> का <math>G</math>. घुमाव में <math>G'</math> का <math>G</math> शीर्ष समुच्चय के संबंध में <math>\{u, v\}</math>, हम पहचानते हैं, इसके बजाय, <math>u_1</math> साथ <math>v_2</math> और <math>v_1</math> साथ <math>u_2</math>.<ref>{{harvnb|Oxley|2006|p=[{{GBurl|puKta1Hdz-8C|p=148}} 148]}}</ref> | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
किसी ग्राफ़ में शीर्षों या किनारों की संख्या को शामिल करके किनारे और शीर्ष संकुचन तकनीक दोनों प्रमाण में मूल्यवान हैं, जहां यह माना जा सकता है कि | किसी ग्राफ़ में शीर्षों या किनारों की संख्या को शामिल करके किनारे और शीर्ष संकुचन तकनीक दोनों प्रमाण में मूल्यवान हैं, जहां यह माना जा सकता है कि संपत्ति सभी छोटे ग्राफ़ के लिए है और इसका उपयोग बड़े ग्राफ़ के लिए संपत्ति को साबित करने के लिए किया जा सकता है। | ||
मनमाने ढंग से जुड़े ग्राफ़ के फैले हुए पेड़ों की संख्या के लिए पुनरावर्ती सूत्र में किनारे संकुचन का उपयोग किया जाता है,<ref>{{harvnb|Gross|Yellen|1998|loc=p. 264}}</ref> और साधारण ग्राफ के [[रंगीन बहुपद]] के लिए पुनरावृत्ति सूत्र में।<ref>{{harvnb|West|2001|loc=p. 221}}</ref> | |||
संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके | संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को [[चक्रीय निर्देशित ग्राफ]] में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध [[सकर्मक संबंध]] है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के सेट के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे। | ||
अन्य उदाहरण [[वैश्विक ग्राफ रंग रजिस्टर आवंटन]] में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)। | |||
कम-बहुभुज मॉडल के निर्माण में सहायता करते हुए, वर्टेक्स गिनती को लगातार कम करने के लिए 3 डी मॉडलिंग पैकेज (या तो मैन्युअल रूप से, या मॉडलिंग सॉफ़्टवेयर की कुछ सुविधा के माध्यम से) में एज संकुचन का उपयोग किया जाता है। | कम-बहुभुज मॉडल के निर्माण में सहायता करते हुए, वर्टेक्स गिनती को लगातार कम करने के लिए 3 डी मॉडलिंग पैकेज (या तो मैन्युअल रूप से, या मॉडलिंग सॉफ़्टवेयर की कुछ सुविधा के माध्यम से) में एज संकुचन का उपयोग किया जाता है। | ||
Revision as of 07:10, 20 July 2023
ग्राफ़ सिद्धांत में, बढ़त संकुचन ग्राफ़ संचालन है जो ग्राफ़ (अलग गणित) से किनारे को हटा देता है, साथ ही साथ दो वर्टेक्स (ग्राफ़ सिद्धांत) को विलय कर देता है जो पहले जुड़े हुए थे। ग्राफ लघु के सिद्धांत में एज संकुचन मौलिक ऑपरेशन है। वर्टेक्स पहचान इस ऑपरेशन का कम प्रतिबंधात्मक रूप है।
परिभाषा
धार संकुचन ऑपरेशन विशेष किनारे के सापेक्ष होता है, . किनारा हटा दिया गया है और इसके दो आपतित शीर्ष हैं, और , नए शिखर में विलीन हो जाते हैं , जहां किनारे आपतित होते हैं प्रत्येक किसी किनारे की घटना से मेल खाता है या . अधिक आम तौर पर, प्रत्येक किनारे को अनुबंधित करके (किसी भी क्रम में) किनारों के सेट पर ऑपरेशन किया जा सकता है।[1] परिणामी प्रेरित ग्राफ़ को कभी-कभी इस प्रकार लिखा जाता है . (इसके साथ तुलना करें , जिसका अर्थ है किनारा हटाना .)
जैसा कि नीचे परिभाषित किया गया है, किनारे संकुचन ऑपरेशन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।[2] हालाँकि, कुछ लेखक[3] एकाधिक किनारों के निर्माण की अनुमति न दें, ताकि सरल ग्राफ़ पर किए गए किनारे संकुचन हमेशा सरल ग्राफ़ उत्पन्न करें।
औपचारिक परिभाषा
होने देना ग्राफ़ (या निर्देशित ग्राफ) हो जिसमें किनारा हो साथ . होने देना ऐसा फ़ंक्शन बनें जो प्रत्येक शीर्ष को मैप करता हो स्वयं के लिए, और अन्यथा, इसे नए शीर्ष पर मैप करता है . का संकुचन नए ग्राफ़ में परिणाम , कहाँ , , और हर किसी के लिए , किनारे की घटना है यदि और केवल यदि, संगत किनारा, की घटना है में .
शीर्ष पहचान
शीर्ष पहचान (जिसे कभी-कभी शीर्ष संकुचन भी कहा जाता है) इस प्रतिबंध को हटा देती है कि संकुचन घटना किनारे को साझा करने वाले शीर्षों पर होना चाहिए। (इस प्रकार, किनारे का संकुचन शीर्ष पहचान का विशेष मामला है।) ऑपरेशन ग्राफ़ में शीर्षों के किसी भी जोड़े (या उपसमुच्चय) पर हो सकता है। दो अनुबंधित शीर्षों के बीच के किनारों को कभी-कभी हटा दिया जाता है। अगर और के अलग-अलग घटकों के शीर्ष हैं , तो हम नया ग्राफ़ बना सकते हैं पहचान कर और में नये शिखर के रूप में में .[4] अधिक आम तौर पर, शीर्ष सेट के सेट के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को भागफल ग्राफ के रूप में जाना जाता है।
वर्टेक्स क्लीविंग
वर्टेक्स क्लीविंग, जो वर्टेक्स स्प्लिटिंग के समान है, का अर्थ है कि शीर्ष को दो में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा ऑपरेशन है, हालांकि सामान्य तौर पर शीर्ष पहचान के लिए, दो पहचाने गए शीर्षों के आसन्न कोने ही सेट नहीं होते हैं।
पथ संकुचन
पथ संकुचन पथ (ग्राफ़ सिद्धांत) में किनारों के सेट पर होता है जो पथ के अंतिम बिंदुओं के बीच एकल किनारा बनाने के लिए संकुचित होता है। पथ के शीर्षों पर पड़ने वाले किनारों को या तो हटा दिया जाता है, या मनमाने ढंग से (या व्यवस्थित रूप से) किसी समापन बिंदु से जोड़ दिया जाता है।
घुमाना
दो असंयुक्त ग्राफ़ पर विचार करें और , कहाँ शीर्ष शामिल हैं और और शीर्ष शामिल हैं और . मान लीजिए हम ग्राफ़ प्राप्त कर सकते हैं शीर्षों की पहचान करके का और का शीर्ष के रूप में का और शीर्षों की पहचान करना का और का शीर्ष के रूप में का . घुमाव में का शीर्ष समुच्चय के संबंध में , हम पहचानते हैं, इसके बजाय, साथ और साथ .[5]
अनुप्रयोग
किसी ग्राफ़ में शीर्षों या किनारों की संख्या को शामिल करके किनारे और शीर्ष संकुचन तकनीक दोनों प्रमाण में मूल्यवान हैं, जहां यह माना जा सकता है कि संपत्ति सभी छोटे ग्राफ़ के लिए है और इसका उपयोग बड़े ग्राफ़ के लिए संपत्ति को साबित करने के लिए किया जा सकता है।
मनमाने ढंग से जुड़े ग्राफ़ के फैले हुए पेड़ों की संख्या के लिए पुनरावर्ती सूत्र में किनारे संकुचन का उपयोग किया जाता है,[6] और साधारण ग्राफ के रंगीन बहुपद के लिए पुनरावृत्ति सूत्र में।[7] संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को चक्रीय निर्देशित ग्राफ में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध सकर्मक संबंध है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के सेट के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे।
अन्य उदाहरण वैश्विक ग्राफ रंग रजिस्टर आवंटन में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)।
कम-बहुभुज मॉडल के निर्माण में सहायता करते हुए, वर्टेक्स गिनती को लगातार कम करने के लिए 3 डी मॉडलिंग पैकेज (या तो मैन्युअल रूप से, या मॉडलिंग सॉफ़्टवेयर की कुछ सुविधा के माध्यम से) में एज संकुचन का उपयोग किया जाता है।
यह भी देखें
टिप्पणियाँ
- ↑ 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
