धार संक्षेपण: Difference between revisions

Revision as of 10:40, 21 July 2023

File:Edge contraction with multiple edges.svg

संकेतित शीर्षों के बीच किनारे को सिकोड़ना, जिसके परिणामस्वरूप ग्राफ़ बनता है

G / {uv}.

ग्राफ़ सिद्धांत में, किनारे का संकुचन ग्राफ़ संचालन ऐसा कार्य है, जो ग्राफ़ (अलग गणित) से किनारे को हटा देता है, और साथ ही उस वर्टेक्स (ग्राफ़ सिद्धांत) दो वर्टेक्स को एकीकृत करती है, जिन्हें पहले वह जोड़ता था। ग्राफ लघु के सिद्धांत में एज संकुचन मौलिक क्रिया है। वर्टेक्स पहचान इस ऑपरेशन का कम प्रतिबंधात्मक रूप है।

परिभाषा

इस प्रकार धार संकुचन ऑपरेशन विशेष किनारे $e$ . के सापेक्ष होता है, किनारा $e$ हटा दिया गया है और इसके दो आपतित शीर्ष हैं, $u$ और $v$ , नए शिखर $w$ , में विलीन हो जाते हैं जहां किनारे आपतित होते हैं $w$ प्रत्येक किसी किनारे की घटना से मेल खाता है $u$ या $v$ . अधिक सामान्यतः , प्रत्येक किनारे को अनुबंधित करके (किसी भी क्रम में) किनारों के सेट पर ऑपरेशन किया जा सकता है।^[1]

इस प्रकार परिणामी प्रेरित ग्राफ़ को कभी-कभी इस प्रकार लिखा जाता है $G/e$ . (इसके साथ समानता करें $G\setminus e$ , जिसका अर्थ है किनारा हटाना $e$ .)होता है।

File:Edge contraction.svg

अनेक किनारे बनाए बिना किनारे को सिकोड़ना।

जैसा कि नीचे परिभाषित किया गया है, किनारे संकुचन ऑपरेशन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।^[2] चूँकि , कुछ लेखक^[3] एकाधिक किनारों के निर्माण की अनुमति न दें, जिससे सरल ग्राफ़ पर किए गए किनारे संकुचन हमेशा सरल ग्राफ़ उत्पन्न करता है।

औपचारिक परिभाषा

मान ले कि $G=(V,E)$ ग्राफ़ (या निर्देशित ग्राफ) हो जिसमें किनारा हो $e=(u,v)$ साथ $u\neq v$ . होने देना $f$ ऐसा फ़ंक्शन बनें जो प्रत्येक शीर्ष को मैप करता हो $V\setminus \{u,v\}$ स्वयं के लिए, इसे नए शीर्ष पर मैप करता है $w$ . का संकुचन $e$ नए ग्राफ़ में परिणाम $G'=(V',E')$ , यहाँ $V'=(V\setminus \{u,v\})\cup \{w\}$ , $E'=E\setminus \{e\}$ , और हर किसी के लिए $x\in V$ , $x'=f(x)\in V'$ किनारे की घटना है $e'\in E'$ यदि और केवल यदि, संगत किनारा, $e\in E$ की घटना $x$ में $G$ है.

शीर्ष पहचान

शीर्ष पहचान (जिसे कभी-कभी शीर्ष संकुचन भी कहा जाता है) इस प्रतिबंध को हटा देती है कि संकुचन घटना किनारे को साझा करने वाले शीर्षों पर होना चाहिए। (इस प्रकार, किनारे का संकुचन शीर्ष पहचान का विशेष स्थिति है।) ऑपरेशन ग्राफ़ में शीर्षों के किसी भी जोड़े (या उपसमुच्चय) पर हो सकता है। दो अनुबंधित शीर्षों के बीच के किनारों को कभी-कभी हटा दिया जाता है। यदि $v$ और $v'$ के अलग-अलग घटकों के शीर्ष हैं $G$ , तो हम नया ग्राफ़ बना सकते हैं $G'$ पहचान कर $v$ और $v'$ में $G$ नये शिखर के रूप में ${\textbf {v}}$ में $G'$ .^[4] अधिक सामान्यतः , शीर्ष सेट के सेट के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को भागफल ग्राफ के रूप में जाना जाता है।

वर्टेक्स क्लीविंग

वर्टेक्स क्लीविंग, जो वर्टेक्स स्प्लिटिंग के समान है, का अर्थ है कि शीर्ष को दो में विभाजित किया जा रहा है, जहां ये दो नए शीर्ष उन शीर्षों के निकट हैं जिनके निकट मूल शीर्ष था। यह शीर्ष पहचान का उलटा ऑपरेशन है, चूंकि सामान्यतः पर शीर्ष प�

[1]

[2]

[3]

[4]

@@ Line 5: / Line 5: @@
 इस प्रकार धार संकुचन ऑपरेशन विशेष किनारे <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|अनेक किनारे बनाए बिना किनारे को सिकोड़ना।]]जैसा कि नीचे परिभाषित किया गया है, किनारे संकुचन ऑपरेशन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।<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> एकाधिक किनारों के निर्माण की अनुमति न दें, जिससे सरल ग्राफ़ पर किए गए किनारे संकुचन हमेशा सरल ग्राफ़ उत्पन्न करें।
+  [[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>e' \in E'</math> यदि और केवल यदि, संगत किनारा, <math>e \in E</math> की घटना है <math>x</math> में <math>G</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>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'</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>
+दो असंयुक्त ग्राफ़ पर विचार करें <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>
+इच्छानुसार से जुड़े ग्राफ़ के विस्तरित तरु की संख्या के लिए पुनरावर्ती सूत्र में किनारे संकुचन का उपयोग किया जाता है,<ref>{{harvnb|Gross|Yellen|1998|loc=p. 264}}</ref>और साधारण ग्राफ के [[रंगीन बहुपद]] के लिए पुनरावृत्ति सूत्र में किया जाता है।<ref>{{harvnb|West|2001|loc=p. 221}}</ref>
 संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को [[चक्रीय निर्देशित ग्राफ]] में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध [[सकर्मक संबंध]] है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के सेट के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे।
@@ Line 33: / Line 33: @@
 अन्य उदाहरण [[वैश्विक ग्राफ रंग रजिस्टर आवंटन]] में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)।
-कम-बहुभुज मॉडल के निर्माण में सहायता करते हुए, वर्टेक्स गिनती को लगातार कम करने के लिए 3 डी मॉडलिंग पैकेज (या तो मैन्युअल रूप से, या मॉडलिंग सॉफ़्टवेयर की कुछ सुविधा के माध्यम से) में एज संकुचन का उपयोग किया जाता है।
+एज संकुचन का उपयोग 3D मॉडलिंग पैकेजों में (या इसे मॉडलिंग सॉफ़्टवेयर की किसी विशेषता द्वारा) वर्टेक्स गिनती को सतत रूप से कम करने में किया जाता है, जिससे लो-बहुभुज मॉडल बनाने में सहायक होता है।
 ==यह भी देखें==

Anonymous

Search

धार संक्षेपण: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:40, 21 July 2023

Contents

परिभाषा

औपचारिक परिभाषा

शीर्ष पहचान

वर्टेक्स क्लीविंग