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

Latest revision as of 15:20, 8 September 2023

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

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$

[1]

[2]

[3]

@@ 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 53: / 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: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 15:20, 8 September 2023

Contents

परिभाषा

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