धार संक्षेपण

File:Edge contraction with multiple edges.svg

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

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

परिभाषा

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

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

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

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

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

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

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

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

पथ संक्षेपण

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

घुमाना

दो असंयुक्त ग्राफ़ पर विचार करें $G_{1}$ और $G_{2}$, यहाँ $G_{1}$ शीर्ष सम्मलित हैं $$