किनारे का संकुचन: Difference between revisions

Latest revision as of 17:50, 19 September 2023

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

G / {uv}.

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

परिभाषा

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

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

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

जैसा कि नीचे परिभाषित किया गया है, किनारे संकुचन संचालन के परिणामस्वरूप कई किनारों वाला ग्राफ़ बन सकता है, भले ही मूल ग्राफ़ साधारण ग्राफ़ हो।^[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] अधिक सामान्यतः , शीर्ष समुच्चय के समुच्चय के विभाजन को देखते हुए, कोई भी विभाजन में शीर्षों की पहचान कर सकता है; परिणामी ग्राफ को भागफल ग्राफ के रूप में जाना जाता है।

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

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

पथ संकुचन

पथ संकुचन पथ (ग्राफ़ सिद्धांत) में किनारों के समुच्चय पर होता है जो पथ के अंतिम बिंदुओं के बीच एकल किनारा बनाने के लिए संकुचित होता है। पथ के शीर्षों पर पड़ने वाले किनारों को या तो हटा दिया जाता है, या इच्छानुसार से (या व्यवस्थित रूप से) किसी समापन बिंदु से जोड़ दिया जाता है।

घुमाना

दो असंयुक्त ग्राफ़ पर विचार करें $G_{1}$ और $G_{2}$ , यहाँ $G_{1}$ शीर्ष सम्मलित हैं $u_{1}$ और $v_{1}$ और $G_{2}$ शीर्ष सम्मलित हैं $u_{2}$ और $v_{2}$ . मान लीजिए हम ग्राफ़ प्राप्त कर सकते हैं $G$ शीर्षों की पहचान करके $u_{1}$ का $G_{1}$ और $u_{2}$ का $G_{2}$ शीर्ष के रूप में $u$ का $G$ और शीर्षों की पहचान करना $v_{1}$ का $G_{1}$ और $v_{2}$ का $G_{2}$ शीर्ष के रूप में $v$ का $G$ . घुमाव में $G'$ का $G$ शीर्ष समुच्चय के संबंध में $\{u,v\}$ , हम पहचानते हैं, इसके अतिरिक्त, $u_{1}$ साथ $v_{2}$ और $v_{1}$ साथ $u_{2}$ .के साथ पहचानते हैं।^[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

बाहरी संबंध

Weisstein, Eric W. "Edge Contraction". MathWorld.

[1] Gross & Yellen 1998, p. 264

[2] 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.

[3] Rosen 2011, p. 664

[4] Oxley 2006, pp. 147–8 §5.3 Whitney's 2-Isomorphism Theorem

[5] Oxley 2006, p. 148

[6] Gross & Yellen 1998, p. 264

[7] West 2001, p. 221

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{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>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>
-संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को [[चक्रीय निर्देशित ग्राफ]] में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध [[सकर्मक संबंध]] है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के सेट के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे।
+संकुचन उन संरचनाओं में भी उपयोगी होते हैं जहां हम उन शीर्षों की पहचान करके ग्राफ को सरल बनाना चाहते हैं जो अनिवार्य रूप से समकक्ष संस्थाओं का प्रतिनिधित्व करते हैं। सबसे आम उदाहरणों में से है प्रत्येक दृढ़ता से जुड़े घटक में सभी शीर्षों को अनुबंधित करके सामान्य निर्देशित ग्राफ को [[चक्रीय निर्देशित ग्राफ]] में कम करना। यदि ग्राफ़ द्वारा वर्णित संबंध [[सकर्मक संबंध]] है, तो कोई भी जानकारी तब तक नष्ट नहीं होती जब तक हम प्रत्येक शीर्ष को उन शीर्षों के लेबल के समुच्चय के साथ लेबल करते हैं जो इसे बनाने के लिए अनुबंधित थे।
 अन्य उदाहरण [[वैश्विक ग्राफ रंग रजिस्टर आवंटन]] में किया गया सह-संयोजन है, जहां अलग-अलग चर के बीच चाल संचालन को खत्म करने के लिए शीर्षों को अनुबंधित किया जाता है (जहां यह सुरक्षित है)।
-कम-बहुभुज मॉडल के निर्माण में सहायता करते हुए, वर्टेक्स गिनती को लगातार कम करने के लिए 3 डी मॉडलिंग पैकेज (या तो मैन्युअल रूप से, या मॉडलिंग सॉफ़्टवेयर की कुछ सुविधा के माध्यम से) में एज संकुचन का उपयोग किया जाता है।
+किनारे का संकुचन का उपयोग 3D मॉडलिंग पैकेजों में (या इसे मॉडलिंग सॉफ़्टवेयर की किसी विशेषता द्वारा) वर्टेक्स गिनती को सतत रूप से कम करने में किया जाता है, जिससे लो-बहुभुज मॉडल बनाने में सहायक होता है।
 ==यह भी देखें==
@@ Line 51: / Line 51: @@
 == बाहरी संबंध ==
 *{{MathWorld|id=EdgeContraction|title=Edge Contraction}}
-[[Category: ग्राफ़ संचालन]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 09/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:ग्राफ़ संचालन]]

Anonymous

Search

किनारे का संकुचन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:50, 19 September 2023

Contents