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

ग्राफ़ सिद्धांत के गणितीय क्षेत्र में, निर्देशित ग्राफ 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.