संक्रामी घटाव (ट्रान्सिटिव रिडक्शन)

आलेख सिद्धांत के गणितीय क्षेत्र में, निर्देशित आलेख D का संक्रामी घटाव समान शीर्षों (आलेख सिद्धांत) और यथासंभव अल्प किनारों वाला एक और निर्देशित आलेख है, जैसे कि शीर्षों के सभी युग्म v, w के लिए (निर्देशित) पथ (आलेख सिद्धांत) से v को w में D सम्मिलित है यदि और केवल यदि ऐसा पथ घटाव में विद्यमान है। अहो, गैरी & उल्मैन (1972) द्वारा संक्रामी घटाव पेश किए गए, जिन्होंने उनके निर्माण की अभिकलनात्मक जटिलता पर कड़ी सीमाएं प्रदान कीं है।

तकनीकी रूप से, घटाव एक निर्देशित आलेख है जिसमें समान अभिगम्यता संबंध D होता है समान रूप से, D और इसकी संक्रामी घटाव में एक दूसरे के समान सकर्मक समापन और D की संक्रामी घटाव में उस गुण के साथ सभी आलेख के बीच जितना संभव हो उतना अल्प किनारा होना चाहिए।

परिमित निर्देशित चक्रीय आलेख (निर्देशित चक्रों के बिना निर्देशित आलेख) की संक्रामी घटाव अद्वितीय है और दिए गए आलेख का एक प्रेरित सबग्राफ़ है। चूंकि, (निर्देशित) चक्र वाले आलेख के लिए विशिष्टता विफल हो जाती है, और अनंत आलेख के लिए अस्तित्व की भी गारंटी नहीं होती है।

न्यूनतम समतुल्य आलेख की निकटतम संबंधित अवधारणा D का सबग्राफ़ है जिसमें समान पहुंच अभिगम्यता संबंध और यथासंभव अल्प किनारे होते हैं। अंतर यह है कि संक्रामी घटाव के लिए D का उपसमूह होना जरूरी नहीं है। परिमित निर्देशित चक्रीय आलेख के लिए, न्यूनतम समतुल्य आलेख संक्रामी घटाव के समान है। चूंकि, ऐसे आलेख के लिए जिनमें चक्र हो सकते हैं, न्यूनतम समतुल्य आलेख का निर्माण एनपी-कठोरता होता है, जबकि बहुपद समय में संक्रामी घटाव का निर्माण किया जा सकता है।

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

निर्देशित चक्रीय आलेख में

परिमित निर्देशित आलेख G की संक्रामी घटाव सबसे अल्प संभव किनारों वाला आलेख है जिसमें मूल आलेख के समान पहुंच अभिगम्यता संबंध है। अर्थात्, यदि आलेख G में शीर्ष x से शीर्ष y तक कोई पथ है, तो G की संक्रामी घटाव में x से y तक का पथ भी होना चाहिए, और इसके विपरीत भी होना चाहिए। विशेष रूप से, यदि x से y तक कुछ पथ है, और y से z तक कोई अन्य पथ है, जिसमें y सम्मिलित न हो तो x से z तक कोई पथ नहीं हो सकता है। x, y, और z के लिए परिवर्तनशीलता (गणित) का अर्थ है कि यदि x < y और y < z, तो x < z है। यदि y से z तक किसी पथ के लिए x से y तक कोई पथ है, तो x से z तक कोई पथ है; चूंकि, यह सच नहीं है कि किसी भी पथ x से y और x से z के लिए पथ y से z है, और इसलिए शीर्ष x और z के बीच के किसी भी किनारे को संक्रामी घटाव के अनुसार बाहर रखा गया है, क्योंकि वे उन पथों का प्रतिनिधित्व करते हैं जो सकर्मक नहीं हैं। निम्नलिखित छवि गैर-संक्रमणीय द्वयी सम्बन्ध (बाईं ओर) और इसकी संक्रामी घटाव (दाईं ओर) के अनुरूप आलेख के चित्र प्रदर्शित करती है।

परिमित निर्देशित चक्रीय आलेख G की संक्रामी घटाव अद्वितीय है, और इसमें G के किनारे सम्मिलित हैं जो उनके समापन बिंदुओं के बीच एकमात्र पथ बनाते हैं। विशेष रूप से, यह हमेशा दिए गए आलेख का फैला हुआ सबग्राफ होता है। इस कारण से, इस मामले में संक्रामी घटाव न्यूनतम समकक्ष आलेख के साथ मेल खाती है।

द्विआधारी संबंधों के गणितीय सिद्धांत में, समुच्चय X पर किसी भी संबंध R को निर्देशित आलेख के रूप में माना जा सकता है इसके शीर्ष समुच्चय के रूप में समुच्चय X है और इसमें R में संबंधित तत्वों के प्रत्येक क्रमित युग्म के लिए चाप xy है। विशेष रूप से, यह विधि आंशिक रूप से क्रम किए गए सेटों को निर्देशित चक्रीय आलेख के रूप में दोबारा व्याख्या करने की अनुमति देती है, जिसमें आंशिक क्रम के तत्वों की दी गई जोड़ी के बीच जब भी क्रम संबंध x < y होता है तो आलेख में चाप xy होता है। जब संक्रामी घटाव संक्रिया को इस तरह से निर्मित निर्देशित चक्रीय आलेख पर लागू किया जाता है, तो यह आंशिक क्रम के समुपयोग संबंध को उत्पन्न करता है, जिसे अधिकांशतः हस्से आरेख के माध्यम से दृश्य अभिव्यक्ति दी जाती है।

नेटवर्क पर संक्रामी घटाव का उपयोग किया गया है जिसे नेटवर्क के बीच संरचनात्मक अंतर प्रकट करने के लिए निर्देशित चक्रीय आलेख (जैसे उद्धरण आलेख या उद्धरण आलेख) के रूप में दर्शाया जा सकता है।

चक्र वाले आलेख में

चक्र वाले परिमित आलेख में, संक्रामी घटाव अद्वितीय नहीं हो सकती है: एक ही शीर्ष समुच्चय पर एक से अधिक आलेख हो सकते हैं जिनमें किनारों की न्यूनतम संख्या होती है और दिए गए आलेख के समान पहुंच अभिगम्यता संबंध होता है। इसके अतिरिक्त, ऐसा भी हो सकता है कि इनमें से कोई भी न्यूनतम आलेख दिए गए आलेख का सबग्राफ न हो। फिर भी, दिए गए आलेख G के समान अभिगम्यता संबंध के साथ न्यूनतम आलेख को चिह्नित करना सीधा है। यदि G यादृच्छिक निर्देशित आलेख है, और H किनारों की न्यूनतम संभावित संख्या वाला आलेख है जिसमें G के समान पहुंच अभिगम्यता संबंध है, तो H में सम्मिलित हैं

• G के प्रत्येक दृढता से जुड़े घटक के लिए निर्देशित चक्र, इस घटक में शीर्षों को एक साथ जोड़ता है
• दृढ़ता से जुड़े घटक की संक्रामी घटाव के प्रत्येक किनारे XY के लिए किनारा xy की परिभाषा, जहां X और Y, G के दो दृढता से जुड़े हुए घटक हैं जो संक्षेपण में किनारे से जुड़े हुए हैं, x घटक X में कोई शीर्ष है, और y घटक Y में कोई शीर्ष है। G का संघनन निर्देशित चक्रीय आलेख है जिसमें G के प्रत्येक दृढता से जुड़े घटक के लिए शीर्ष होता है और G में किनारे से जुड़े प्रत्येक दो घटकों के लिए किनारा होता है। विशेष रूप से, क्योंकि यह चक्रीय है, इसकी संक्रामी घटाव को पिछले अनुभाग के अनुसार परिभाषित किया जा सकता है।

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

संक्षेपण किनारों के अनुरूप संक्रामी घटाव के किनारों को हमेशा दिए गए आलेख G का सबग्राफ चुना जा सकता है। चूंकि, प्रत्येक दृढ़ता से जुड़े घटक के भीतर चक्र को केवल G का सबग्राफ चुना जा सकता है यदि उस घटक में हैमिल्टनियन चक्र हो, कुछ ऐसा जो हमेशा सत्य नहीं होता और जिसे जांचना कठिन होता है। इस कठिनाई के कारण, समान अभिगम्यता (इसका न्यूनतम समतुल्य आलेख) के साथ दिए गए आलेख G का सबसे छोटा सबग्राफ ढूंढना एनपी-कठोरता है।

अभिकलनात्मक जटिलता

अहो एट अल के रूप में दिखाएँ,जब आलेख एल्गोरिदम की समय जटिलता को केवल आलेख में शीर्षों की संख्या n के फलन के रूप में मापा जाता है, न कि किनारों की संख्या के फलन के रूप में, निर्देशित चक्रीय आलेख के सकर्मक समापन और संक्रामी घटाव में समान जटिलता होती है। यह पहले ही दिखाया जा चुका है कि आकार n × n के बूलियन आव्यूह के सकर्मक समापन और आव्यूह गुणन में एक दूसरे के समान जटिलता थी, इसलिए इस परिणाम ने संक्रामी घटाव को उसी वर्ग में डाल दिया है। 2015 तक, आव्यूह गुणन की अभिकलनात्मक जटिलता में O(n^2.3729) समय लगता है, और यह सघन आलेख में संक्रामी घटाव के लिए सबसे तेज़ ज्ञात सबसे खराब स्थिति की समय सीमा देता है।

क्लोजर का उपयोग करके घटाव की गणना करना

यह सिद्ध करने के लिए कि संक्रामी घटाव सकर्मक समापन जितना आसान है, अहो एट अल बूलियन आव्यूह गुणन के साथ पहले से ज्ञात तुल्यता पर भरोसा करें। उन्होंने A को दिए गए निर्देशित चक्रीय आलेख का आसन्न आव्यूह है, और B को इसके सकर्मक समापन का आसन्न आव्यूह है (किसी भी मानक सकर्मक समापन एल्गोरिदम का उपयोग करके गणना की गई)। तब किनारा uv संक्रामी घटाव से संबंधित होता है यदि और केवल यदि आव्यूह A की पंक्ति u और कॉलम v में गैर-शून्य प्रविष्टि है, और आव्यूह उत्पाद AB की उसी स्थिति में शून्य प्रविष्टि है। इस निर्माण में, आव्यूह AB के गैर-शून्य तत्व दो या अधिक लंबाई के पथों से जुड़े शीर्षों के युग्म का प्रतिनिधित्व करते हैं।

घटाव का उपयोग करके समापन की गणना करना

यह सिद्ध करने के लिए कि संक्रामी घटाव सकर्मक समापन जितनी ही कठिन है, अहो एट अल दिए गए निर्देशित चक्रीय आलेख G से एक और आलेख H का निर्माण करें, जिसमें G के प्रत्येक शीर्ष को तीन शीर्षों के पथ से बदल दिया जाता है, और G का प्रत्येक किनारा इन पथों के संबंधित मध्य शीर्षों को जोड़ने वाले H में किनारे से मेल खाता है। इसके अतिरिक्त, आलेख H, अहो एट अल में प्रत्येक पथ के आरंभ से प्रत्येक पथ के अंत तक किनारा जोड़ें। H की संक्रामी घटाव में, u के लिए पथ प्रारंभ से v के लिए पथ के अंत तक किनारा है, यदि और केवल यदि किनारा uv G के सकर्मक समापन से संबंधित नहीं है। इसलिए, यदि H की संक्रामी घटाव हो सकती है कुशलतापूर्वक गणना करने पर, G के सकर्मक समापन को सीधे इससे पढ़ा जा सकता है।

विरल आलेख में घटाव की गणना करना

जब निर्देशित चक्रीय आलेख में शीर्षों की संख्या n और किनारों की संख्या m दोनों के संदर्भ में मापा जाता है, तो समय O(nm) में संक्रामी घटाव भी पाई जा सकती है, एक सीमा जो विरल आलेख के लिए आव्यूह गुणन विधियों से तेज़ हो सकती है ऐसा करने के लिए, प्रारंभिक शीर्ष के प्रत्येक संभावित विकल्प के लिए, दिए गए निर्देशित चक्रीय आलेख में रैखिक समय सबसे लंबे पथ समस्या को लागू करता है। गणना किए गए सबसे लंबे पथों में से, केवल एक लंबाई (एकल किनारे) वाले पथों को ही रखें; दूसरे शब्दों में, उन किनारों (u, v) को रखें जिनके लिए u से v तक कोई अन्य पथ सम्मिलित नहीं है। यह O(nm) समयबद्ध गहराई पहले सर्च या विस्तार-प्रधान सर्च का उपयोग करके सकर्मक समापन के निर्माण की जटिलता से मेल खाता है। आरंभिक शीर्ष के हर विकल्प से पहुंच योग्य शीर्ष, इसलिए फिर से इन मान्यताओं के साथ सकर्मक समापन और संक्रामी घटाव एक ही समय में पाई जा सकती हैं।

संदर्भ

• Aho, A. V.; Garey, M. R.; Ullman, J. D. (1972), "The transitive reduction of a directed graph", SIAM Journal on Computing, 1 (2): 131–137, doi:10.1137/0201008, MR 0306032.
• Clough, J. R.; Gollings, J.; Loach, T. V.; Evans, T. S. (2015), "Transitive reduction of citation networks", Journal of Complex Networks, 3 (2): 189–203, arXiv:1310.8224, doi:10.1093/comnet/cnu039.
• Moyles, Dennis M.; Thompson, Gerald L. (1969), "An Algorithm for Finding a Minimum Equivalent Graph of a Digraph", Journal of the ACM, 16 (3): 455–460, doi:10.1145/321526.321534.
• Le Gall, François (2014), "Powers of Tensors and Fast Matrix Multiplication", Proc. 39th International Symposium on Symbolic and Algebraic Computation (ISSAC '14), pp. 296–303, doi:10.1145/2608628.2608664.

बाहरी संबंध

• Weisstein, Eric W. "Transitive Reduction". MathWorld.