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

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

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

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

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

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

निर्देशित चक्रीय ग्राफ़ में

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

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

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

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

चक्र वाले ग्राफ़ में

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

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

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

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

कम्प्यूटेशनल जटिलता

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

क्लोजर का उपयोग करके कमी की गणना करना

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

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

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

विरल ग्राफ़ में कमी की गणना करना

जब निर्देशित एसाइक्लिक ग्राफ़ में शीर्षों की संख्या n और किनारों की संख्या m दोनों के संदर्भ में मापा जाता है, तो समय 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.