Ear decomposition
ग्राफ सिद्धांत में, एक दिशाहीन ग्राफ जी का कान एक पथ पी है जहां पथ के दो अंतिम बिंदु मेल खा सकते हैं, लेकिन जहां अन्यथा किनारों या शीर्षों की पुनरावृत्ति की अनुमति नहीं है, इसलिए पी के प्रत्येक आंतरिक शीर्ष में जी में डिग्री दो होती है। इसके अतिरिक्त, ज्यादातर मामलों में अनुक्रम में पहला कान एक चक्र होना चाहिए। एक खुला कान अपघटन या एक उचित कान अपघटन एक कान अपघटन है जिसमें पहले के बाद प्रत्येक कान के दो अंतिम बिंदु एक दूसरे से अलग होते हैं। कान अपघटन का उपयोग कई महत्वपूर्ण ग्राफ वर्गों को चिह्नित करने के लिए और कुशल ग्राफ एल्गोरिदम के हिस्से के रूप में किया जा सकता है। उन्हें ग्राफ से लेकर मैट्रोइड तक भी सामान्यीकृत किया जा सकता है। ग्राफ वर्गों की विशेषता ग्राफ के कई महत्वपूर्ण वर्गों को कुछ प्रकार के कान अपघटन वाले ग्राफ के रूप में वर्णित किया जा सकता है। ग्राफ कनेक्टिविटी एक ग्राफ के-वर्टेक्स से जुड़ा होता है यदि किसी भी (के-1) शीर्ष को हटाने से एक जुड़ा हुआ उपग्राफ निकल जाता है, और के-एज से जुड़ा होता है यदि किसी भी (के-1) किनारों को हटाने से एक जुड़ा हुआ उपग्राफ निकल जाता है। निम्नलिखित परिणाम इसके कारण हैः एक ग्राफ 2-वर्टेक्स से जुड़ा हुआ है यदि और केवल तभी जब इसमें खुले कान का अपघटन हो। निम्नलिखित परिणाम इसके कारण हैः एक ग्राफ 2-किनारे से जुड़ा होता है यदि और केवल तभी जब इसमें कान का अपघटन होता है। दोनों ही मामलों में कान की संख्या अनिवार्य रूप से दिए गए ग्राफ के परिपथ श्रेणी के बराबर होती है। रॉबिन्स ने रॉबिन्स प्रमेय को साबित करने के लिए एक उपकरण के रूप में 2-किनारे से जुड़े ग्राफों के कान के अपघटन की शुरुआत की, कि ये वास्तव में ऐसे ग्राफ हैं जिन्हें दृढ़ता से जुड़ा हुआ अभिविन्यास दिया जा सकता है। कान के अपघटन पर व्हिटनी और रॉबिन्स के अग्रणी काम के कारण, कान के अपघटन को कभी-कभी व्हिटनी-रॉबिन्स संश्लेषण भी कहा जाता है। एक गैर-पृथक्कृत कान अपघटन एक खुला कान अपघटन है जैसे कि, केवल एक अपवाद के साथ प्रत्येक शीर्ष v के लिए, v का एक पड़ोसी होता है जिसका अपघटन में पहली उपस्थिति v की पहली उपस्थिति की तुलना में बाद के कान में होती है। इस प्रकार के कान अपघटन का उपयोग व्हिटनी के परिणाम को सामान्य बनाने के लिए किया जा सकता हैः 3-वर्टेक्स के साथ एक ग्राफ 3-वर्टेक्स से जुड़ा होता है यदि और केवल तभी जब G में एक गैर-पृथक्कृत कान अपघटन होता है। यदि ऐसा अपघटन मौजूद है, तो इसे जी के एक विशेष किनारे यूवी के संबंध में इस तरह से चुना जा सकता है कि यू पहले कान में हो, वी अंतिम कान में एक से अधिक किनारे वाला नया शीर्ष हो, और यूवी एक एकल-किनारे वाला कान हो। यह परिणाम पहली बार स्पष्ट रूप से ली मोंडशेन द्वारा कहा गया था, लेकिन जैसा कि वर्णन किया गया है, यह ली मोंडशीन के 1971 के पीएचडी थीसिस के परिणाम के बराबर है। अधिकतम समतलीय ग्राफ के गैर-पृथक्कृत कान अपघटन से निकटता से संबंधित संरचनाएँ, जिन्हें कैनॉनिकल ऑर्डरिंग कहा जाता है, भी ग्राफ ड्राइंग में एक मानक उपकरण हैं। निर्देशित ग्राफ की मजबूत कनेक्टिविटी उपरोक्त परिभाषाओं को निर्देशित ग्राफ पर भी लागू किया जा सकता है। एक कान तब एक निर्देशित मार्ग होगा जहाँ सभी आंतरिक शीर्षों में 1 के बराबर अनिर्णित और बाहरी डिग्री होती है। एक निर्देशित ग्राफ दृढ़ता से जुड़ा होता है यदि इसमें प्रत्येक शीर्ष से प्रत्येक अन्य शीर्ष तक एक निर्देशित मार्ग होता है। फिर हमारे पास निम्नलिखित प्रमेय हैः एक निर्देशित ग्राफ दृढ़ता से जुड़ा हुआ है यदि और केवल तभी जब इसमें कान का अपघटन हो। कारक-महत्वपूर्ण ग्राफ एक कान का अपघटन विषम है यदि इसके प्रत्येक कान विषम संख्या में किनारों का उपयोग करते हैं। एक कारक-महत्वपूर्ण ग्राफ शीर्षों की विषम संख्या वाला एक ग्राफ है, जैसे कि प्रत्येक शीर्ष v के लिए, यदि v को ग्राफ से हटा दिया जाता है तो शेष शीर्षों का एक सही मिलान होता है। यह पाया गया किः एक ग्राफ जी कारक-महत्वपूर्ण है यदि और केवल तभी जब जी में एक विषम कान अपघटन हो। अधिक सामान्य रूप से, इसका परिणाम किसी भी ग्राफ जी में सबसे कम सम कान के साथ कान के अपघटन को खोजना संभव बनाता है। श्रृंखला-समानांतर ग्राफ एक वृक्ष के कान का अपघटन एक उचित कान अपघटन है जिसमें पहला कान एक किनारा होता है और प्रत्येक बाद के कान के लिए एक कान होता है, जैसे कि दोनों अंतिम बिंदु होते हैं। एक नेस्टेड कान अपघटन एक पेड़ के कान का अपघटन है, जैसे कि प्रत्येक कान के भीतर, अन्य कानों के अंतिम बिंदुओं के जोड़े जो नेस्टेड अंतराल के एक सेट के भीतर होते हैं। एक श्रृंखला-समानांतर ग्राफ दो निर्दिष्ट टर्मिनलों एस और टी के साथ एक ग्राफ है जिसे दो तरीकों में से एक में छोटे श्रृंखला-समानांतर ग्राफों को मिलाकर पुनरावर्ती रूप से बनाया जा सकता हैः श्रृंखला संरचना (एक छोटे ग्राफ से एक टर्मिनल की पहचान दूसरे छोटे ग्राफ से एक टर्मिनल के साथ करना, और अन्य दो टर्मिनलों को संयुक्त ग्राफ के टर्मिनलों के रूप में रखना) और समानांतर संरचना (दो छोटे ग्राफों से दोनों जोड़े टर्मिनलों की पहचान करना)। निम्नलिखित परिणाम निम्नलिखित के कारण हैः एक 2-वर्टेक्स से जुड़ा ग्राफ श्रृंखला-समानांतर है यदि और केवल तभी जब इसमें एक नेस्टेड कान अपघटन हो। इसके अलावा, 2-वर्टेक्स से जुड़े श्रृंखला-समानांतर ग्राफ के किसी भी खुले कान के अपघटन को नेस्ट किया जाना चाहिए। परिणाम को श्रृंखला-समानांतर ग्राफों तक बढ़ाया जा सकता है जो दो टर्मिनलों के बीच एक पथ के साथ शुरू होने वाले खुले कान अपघटन का उपयोग करके 2-वर्टेक्स से जुड़े नहीं हैं। मैट्रोइड्स कान के अपघटन की अवधारणा को ग्राफ से लेकर मैट्रोइड्स तक बढ़ाया जा सकता है। एक मैट्रायड के कान के अपघटन को दो गुणों के साथ मैट्रायड के परिपथों के एक अनुक्रम के रूप में परिभाषित किया गया हैः अनुक्रम में प्रत्येक परिपथ में पिछले परिपथों के साथ एक गैर-खाली प्रतिच्छेदन होता है, और अनुक्रम में प्रत्येक परिपथ एक परिपथ बना रहता है, भले ही अनुक्रम में पिछले सभी परिपथ संकुचित हों। जब ग्राफ जी के ग्राफिक मैट्रायड पर लागू किया जाता है, तो कान के अपघटन की यह परिभाषा जी के उचित कान अपघटन की परिभाषा के साथ मेल खाती हैः अनुचित अपघटन को इस आवश्यकता से बाहर रखा जाता है कि प्रत्येक परिपथ में कम से कम एक किनारा शामिल हो जो पिछले परिपथ से भी संबंधित हो। इस परिभाषा का उपयोग करते हुए, एक मैट्रायड को कारक-महत्वपूर्ण के रूप में परिभाषित किया जा सकता है जब इसमें कान का अपघटन होता है जिसमें अनुक्रम में प्रत्येक परिपथ में विषम संख्या में नए तत्व होते हैं। एल्गोरिदम शास्त्रीय कंप्यूटरों पर, 2-किनारे से जुड़े ग्राफों के कान के अपघटन और 2-वर्टेक्स से जुड़े ग्राफों के खुले कान के अपघटन लालची एल्गोरिदम द्वारा पाए जा सकते हैं जो प्रत्येक कान को एक समय में एक पाते हैं। एक सरल लालची दृष्टिकोण जो एक ही समय में कान के अपघटन, खुले कान के अपघटन, एस. टी.-संख्या और रैखिक समय (यदि मौजूद हो) में-अभिविन्यास की गणना करता है, में दिया गया है। यह दृष्टिकोण एक पथ-उत्पन्न करने वाले नियम द्वारा श्रृंखला अपघटन नामक एक विशेष कान अपघटन की गणना पर आधारित है। यह दर्शाता है कि गैर-अलग कान अपघटन भी रैखिक समय में बनाया जा सकता है। , और विभिन्न प्रकार के कान अपघटन के निर्माण के लिए कुशल समानांतर एल्गोरिदम प्रदान किए। उदाहरण के लिए, 2-किनारे से जुड़े ग्राफ के कान के अपघटन का पता लगाने के लिए, निम्नलिखित चरणों के अनुसार आय का एल्गोरिथ्मः दिए गए ग्राफ का एक फैला हुआ पेड़ खोजें और पेड़ के लिए एक जड़ चुनें। प्रत्येक किनारे यूवी के लिए, जो पेड़ का हिस्सा नहीं है, मूल और यू और वी के सबसे निचले सामान्य पूर्वज के बीच की दूरी निर्धारित करें। प्रत्येक किनारे यूवी के लिए जो पेड़ का हिस्सा है, संबंधित "मास्टर एज", एक गैर-पेड़ का किनारा डब्ल्यूएक्स ऐसे खोजें कि पेड़ में डब्ल्यूएक्स जोड़कर बनाया गया चक्र यूवी के माध्यम से गुजरता है और ऐसे किनारों के बीच, डब्ल्यू और एक्स का सबसे कम सामान्य पूर्वज होता है जो जड़ के जितना संभव हो उतना करीब होता है (किनारे पहचानकर्ताओं द्वारा टूटे संबंधों के साथ)। प्रत्येक गैर-वृक्ष किनारे के लिए एक कान बनाएँ, जिसमें यह और पेड़ के किनारे शामिल हैं, जिसके लिए यह मास्टर है, और जड़ से अपने मास्टर किनारों की दूरी (उसी टाई-ब्रेकिंग नियम के साथ) से कानों को क्रमबद्ध करें। इन एल्गोरिदम का उपयोग अन्य समस्याओं के लिए उप-दिनचर्या के रूप में किया जा सकता है जिसमें परीक्षण संपर्क, श्रृंखला-समानांतर ग्राफ को पहचानना और ग्राफ की एस. टी.-संख्या (समतलीयता परीक्षण में एक महत्वपूर्ण उप-दिनचर्या) का निर्माण शामिल है। एक दिए गए मैट्रायड का एक कान अपघटन, इस अतिरिक्त बाधा के साथ कि प्रत्येक कान में मैट्रायड का एक ही निश्चित तत्व होता है, बहुपद समय में पाया जा सकता है जिसे मैट्रायड के लिए एक स्वतंत्र दैवज्ञ तक पहुंच दी जाती है। संदर्भ। .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ग्राफ सिद्धांत ने मैट्रायड सिद्धांत पर आपत्ति जताई