सकर्मक समापन: Difference between revisions

Revision as of 11:33, 10 July 2023

गणित में, द्विआधारी संबंध का सकर्मक समापन $R$ समुच्चय $X$ पर (गणित) पर सबसे छोटा संबंध (गणित) है $X$ उसमें सम्मिलित है $R$ और सकर्मक संबंध है. परिमित समुच्चयों के लिए, सबसे छोटे को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत समुच्चयों के लिए यह अद्वितीय न्यूनतम तत्व सकर्मक सुपरसेट है $R$ .

गणित में, समुच्चय $X$ पर द्विआधारी संबंध $R$ का सकर्मक समापन, X पर सबसे छोटा संबंध (गणित) है इसमें R सम्मिलित होते है और यह सकर्मक संबंध होते है। परिमित समुच्चयों के लिए, "सबसे छोटे" को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत समुच्चयों के लिए यह R का अद्वितीय न्यूनतम तत्व सकर्मक सुपरसेट है।

इस प्रकार से उदाहरण के लिए, यदि $X$ हवाई अड्डों का एक समूह है और $x R y$ का अर्थ है "हवाई अड्डे $X$ से हवाई अड्डे $y$ के लिए सीधी उड़ान है" ( $x$ में $X$ और $y$ के लिए), तो उस $x R + y$ का अर्थ है "एक या अधिक उड़ानों में $X$ से $y$ तक उड़ान भरना संभव होता है"। अनौपचारिक रूप से, ट्रांजिटिव क्लोजर आपको उन सभी स्थानों का सेट देता है जहां आप किसी भी प्रारंभिक स्थान से पहुंच सकते हैं।

अधिक औपचारिक रूप से, द्विआधारी संबंध का सकर्मक समापन $R$ समुच्चय $X$ पर सकर्मक संबंध है समुच्चय $R +$ पर $X$ ऐसा है कि $R +$ रोकना $R$ और $R +$ न्यूनतम है; देखना Lidl & Pilz (1998, p. 337). यदि द्विआधारी संबंध स्वयं सकर्मक है, तो सकर्मक समापन वही द्विआधारी संबंध है; अन्यथा, सकर्मक समापन अलग संबंध है।

इसके विपरीत, संक्रमणीय कमी न्यूनतम संबंध $S$ से जोड़ती है किन्तु किसी दिए गए संबंध $R$ से जैसे कि उनका समापन $S + = R +$ ही है ; चूंकि , कई भिन्न $S$ इस संपत्ति के साथ उपस्तिथ हो सकता है।

अतः सकर्मक समापन और संक्रमणीय कमी दोनों का उपयोग ग्राफ सिद्धांत के निकट से संबंधित क्षेत्र में भी किया जाता है।

सकर्मक संबंध और उदाहरण

इस प्रकार से समुच्चय X पर संबंध R सकर्मक है यदि, X में सभी x, y, z के लिए, जब भी x R y और y R z तब x R z. सकर्मक संबंधों के उदाहरणों में किसी भी समुच्चय पर समानता संबंध, किसी भी रैखिक रूप से आदेशित समुच्चय पर कम या समान संबंध, और सभी लोगों के समुच्चय पर संबंध x का जन्म y से पहले हुआ था। और प्रतीकात्मक रूप से, इसे इस प्रकार दर्शाया जा सकता है: यदि x < y और y < z तब x < z. प्राप्त होता है

किन्तु गैर-संक्रमणीय संबंध का उदाहरण इस प्रकार से है कि शहर x तक सभी शहरों y के समुच्चय पर शहर से सीधी उड़ान के माध्यम से पहुंचा जा सकता है। और इसके अतिरिक्त शहर से दूसरे शहर के लिए सीधी उड़ान है, और दूसरे शहर से तीसरे शहर के लिए सीधी उड़ान होती है, इसका मतलब यह नहीं है कि पहले शहर से तीसरे शहर के लिए सीधी उड़ान है। इस संबंध का सकर्मक समापन अलग संबंध है, अर्थात् सीधी उड़ानों का क्रम है जो शहर x से प्रारंभ होता है और शहर y पर समाप्त होता है। प्रत्येक संबंध को सकर्मक संबंध के समान ही बढ़ाया जा सकता है।

कम सार्थक सकर्मक समापन के साथ एक गैर-संक्रमणीय संबंध का एक उदाहरण है "x, y के पश्चात सप्ताह का दिन है"। इस संबंध का सकर्मक समापन "कुछ दिन x कैलेंडर पर एक दिन y के पश्चात आता है" है, जो सप्ताह के सभी दिनों x और y के लिए तुच्छ रूप से सत्य है (और इस प्रकार कार्टेशियन वर्ग के समान है, जो कि "x और y हैं सप्ताह के दोनों दिन")।

अस्तित्व और विवरण

इस प्रकार से किसी भी संबंध R के लिए, R का सकर्मक समापन सदैव उपस्तिथ रहता है। और इसे देखने के लिए, ध्यान दें कि सकर्मक संबंधों के किसी भी अनुक्रमित परिवार का प्रतिच्छेदन (समुच्चय सिद्धांत) पुनः से सकर्मक है। इसके अतिरिक्त , R, युक्त कम से कम सकर्मक संबंध उपस्तिथ होते है, अर्थात् तुच्छ एक: X × X । आर का सकर्मक समापन तब R, युक्त सभी सकर्मक संबंधों के प्रतिच्छेदन द्वारा दिया जाता है।

परिमित समुच्चयों के लिए, हम R से प्रारंभ करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं।

यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी समुच्चय X, के लिए, हम

यह प्रमाणित कर सकता है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है

R^{+}=\bigcup _{i=1}^{\infty }R^{i}.

जहाँ $R^{i}$ R की i-th पावर है, जिसे आगमनात्मक रूप से परिभाषित किया गया है

R^{1}=R

और के लिए $i>0$ ,

R^{i+1}=R\circ R^{i}

जहाँ $\circ$ संबंधों की संरचना को दर्शाता है.

इस प्रकार से यह दर्शाने के लिए कि R⁺ की उपरोक्त परिभाषा R युक्त सबसे कम सकर्मक संबंध है, हम दिखाते हैं कि इसमें R सम्मिलित है, कि यह सकर्मक है, और यह उन दोनों विशेषताओं के साथ सबसे छोटा समुच्चय है।

$R\subseteq R^{+}$ : $R^{+}$ सभी सम्मिलित हैं $R^{i}$ , इसलिए विशेष रूप से $R^{+}$ रोकना $R$ .
$R^{+}$ सकर्मक है: यदि $(s_{1},s_{2}),(s_{2},s_{3})\in R^{+}$ , तब $(s_{1},s_{2})\in R^{j}$ और $(s_{2},s_{3})\in R^{k}$ कुछ के लिए $j,k$ की परिभाषा के अनुसार $R^{+}$ . चूँकि रचना साहचर्य है, $R^{j+k}=R^{j}\circ R^{k}$ ; इस तरह $(s_{1},s_{3})\in R^{j+k}\subseteq R^{+}$ की परिभाषा के अनुसार $\circ$ और $R^{+}$ .
$R^{+}$ न्यूनतम है, अर्थात यदि $T$ कोई सकर्मक संबंध युक्त है $R$ , तब $R^{+}\subseteq T$ : ऐसा कोई दिया गया $T$ , गणितीय प्रेरण पर $i$ दिखाने के लिए उपयोग किया जा सकता है $R^{i}\subseteq T$ सभी के लिए $i$ इस प्रकार: आधार: $R^{1}=R\subseteq T$ अनुमान से. चरण: यदि $R^{i}\subseteq T$ धारण करता है, और $(s_{1},s_{3})\in R^{i+1}=R\circ R^{i}$ , तब $(s_{1},s_{2})\in R$ और $(s_{2},s_{3})\in R^{i}$ कुछ के लिए $s_{2}$ , की परिभाषा के अनुसार $\circ$ . इस तरह, $(s_{1},s_{2}),(s_{2},s_{3})\in T$ धारणा द्वारा और प्रेरण परिकल्पना द्वारा। इस तरह $(s_{1},s_{3})\in T$ की परिवर्तनशीलता द्वारा $T$ ; यह प्रेरण पूरा करता है। इस प्रकार से , $R^{i}\subseteq T$ सभी के लिए $i$ तात्पर्य $R^{+}\subseteq T$ की परिभाषा $R^{+}$ के अनुसार .

गुण

इस प्रकार से दो सकर्मक संबंधों का प्रतिच्छेदन (समुच्चय सिद्धांत) सकर्मक है।

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

ग्राफ़ सिद्धांत में

Transitive closure constructs the output graph from the input graph.

ट्रांसिटिव क्लोजर इनपुट ग्राफ से आउटपुट ग्राफ का निर्माण करता है।

इस प्रकार से कंप्यूटर विज्ञान में, ट्रांजिटिव क्लोजर की अवधारणा को डेटा संरचना के निर्माण के रूप में विचार किया जा सकता है जोकी गम्यता प्रश्नों का उत्तर देना संभव बनाता है। अर्थात , क्या कोई या अधिक हॉप्स में नोड A से नोड d तक पहुंच सकता है? द्विआधारी संबंध आपको केवल यह बताता है कि नोड A नोड b से जुड़ा है, और वह नोड b नोड सी से जुड़ा है, आदि। ट्रांजिटिव क्लोजर के निर्माण के पश्चात , जैसा कि निम्नलिखित चित्र में दर्शाया गया है, Big_O_notation#Orders_of_common_functions|O(1) में ) ऑपरेशन यह निर्धारित कर सकता है कि नोड d नोड a से पहुंच योग्य है। डेटा संरचना को सामान्यतः बूलियन मैट्रिक्स के रूप में संग्रहीत किया जाता है, इसलिए यदि मैट्रिक्स [1] [4] = सत्य है, तो यह स्तिथि है कि नोड 1 या अधिक हॉप्स के माध्यम से नोड 4 तक पहुंच सकता है।

इस प्रकार से निर्देशित अचक्रीय ग्राफ (डीएजी) के आसन्न संबंध का सकर्मक समापन डीएजी का पहुंच योग्यता संबंध और सख्त आंशिक आदेश है।

एक क्लस्टर ग्राफ़, अप्रत्यक्ष ग्राफ़ का सकर्मक समापन

एक अप्रत्यक्ष ग्राफ का सकर्मक समापन क्लस्टर ग्राफ़ उत्पन्न करता है, जोकी क्लिक (ग्राफ़ सिद्धांत) के ग्राफ़ का असंयुक्त संघ है। ट्रांजिटिव क्लोजर का निर्माण ग्राफ के घटक (ग्राफ सिद्धांत) को खोजने की समस्या का समतुल्य सूत्रीकरण है।^[1]

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

इस प्रकार से किसी द्विआधारी संबंध का सकर्मक समापन, सामान्य तौर पर, प्रथम-क्रम तर्क (एफओ) में व्यक्त नहीं किया जा सकता है।

किन्तु इसका मतलब यह है कि कोई भी विधेय प्रतीकों R और T का उपयोग करके सूत्र नहीं लिख सकता है जो संतुष्ट हो जाएगा

कोई भी मॉडल यदि और केवल यदि T, R का सकर्मक समापन है।

इस प्रकार से परिमित मॉडल सिद्धांत में, ट्रांजिटिव क्लोजर ऑपरेटर के साथ विस्तारित प्रथम-क्रम तर्क (एफओ) को सामान्यतः 'ट्रांसिटिव क्लोजर लॉजिक' कहा जाता है, और संक्षिप्त रूप से FO (टीसी) या सिर्फ TC कहा जाता है। TC फिक्सप्वाइंट लॉजिक्स का उप-प्रकार है। तथ्य यह है कि FO (टीसी) FO की तुलना में सख्ती से अधिक अभिव्यंजक है, इसकी खोज रोनाल्ड फागिन ने 1974 में की थी; परिणाम को इस प्रकार से 1979 में मैं अल्फ्रेड हूं और जेफरी उलमन द्वारा पुनः से खोजा गया, जिन्होंने डेटाबेस क्वेरी भाषा के रूप में फिक्सपॉइंट तर्क का उपयोग करने का प्रस्ताव रखा गया था ।^[2] और परिमित मॉडल सिद्धांत की नवीनतम अवधारणाओं के साथ, यह प्रमाण कि FO (टीसी) FO की तुलना में सख्ती से अधिक अभिव्यंजक है, इस तथ्य से तुरंत पता चलता है कि FO (टीसी) गैफमैन-स्थानीय नहीं होते है।^[3]

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

डेटाबेस क्वेरी भाषाओं में

1980 के दशक से आकाशवाणी डेटाबेस ने मालिकाना एसक्यूएल एक्सटेंशन प्रयुक्त किया है CONNECT BY... START WITH यह घोषणात्मक क्वेरी के भाग के रूप में सकर्मक समापन की गणना की अनुमति देता है। एसक्यूएल 3 (1999) मानक ने और अधिक सामान्य जोड़ा WITH RECURSIVE निर्माण क्वेरी प्रोसेसर के अंदर ट्रांजिटिव क्लोजर की गणना करने की भी अनुमति देता है; 2011 तक पश्चात वाले को आईबीएम डीबी2, माइक्रोसॉफ्ट एसक्यूएल सर्वर, आकाशवाणी डेटाबेस, पोस्टग्रेएसक्यूएल और माई एसक्यूएल (v8.0+) में प्रयुक्त किया गया है। और एसक्यूलाइट ने 2014 में इसके लिए समर्थन उपयोग किया गया था ।

इस प्रकार से संगणक वैज्ञानिक ट्रांजिटिव क्लोजर गणनाओं को भी प्रयुक्त करता है।^[4]

मारियाडीबी रिकर्सिव कॉमन टेबल एक्सप्रेशन प्रयुक्त करता है, जिसका उपयोग ट्रांजिटिव क्लोजर की गणना करने के लिए किया जा सकता है। यह सुविधा अप्रैल 2016 की रिलीज़ 10.2.2 में उपस्तिथ की गई थी।^[5]

एल्गोरिदम

इस प्रकार से ग्राफ़ के आसन्न संबंध के सकर्मक समापन की गणना के लिए कुशल एल्गोरिदम यहां पाए जा सकते हैं नुउटिला (1995). आसन्न मैट्रिक्स के गुणन की समस्या को कम करने से न्यूनतम उपलब्धि प्राप्त होती है समय जटिलता, अर्थात। मैट्रिक्स गुणन (मुनरो 1971, फिशर & मेयेर 1971), जो है $O(n^{2.3728596})$ as of December 2020^[update]. चूंकि , यह दृष्टिकोण व्यावहारिक नहीं है क्योंकि विरल ग्राफ़ के लिए स्थिर कारक और मेमोरी खपत दोनों अधिक हैं (नुउटिला 1995, pp. 22–23, sect.2.3.3). समस्या को फ़्लॉइड-वॉर्शल एल्गोरिथम $O(n^{3})$ , द्वारा भी हल किया जा सकता है या ग्राफ़ के प्रत्येक नोड से प्रारंभ होने वाली बार-बार चौड़ाई-पहली खोज या गहराई-पहली खोज द्वारा किया गया था ।

इस प्रकार से निर्देशित ग्राफ़ के लिए, पर्डोम का एल्गोरिदम पहले इसके संक्षेपण डीएजी और इसके संक्रमणीय समापन की गणना करके, पुनः इसे मूल ग्राफ़ पर उठाकर समस्या का समाधान करता है। इसका रनटाइम $O(m+\mu n)$ है , जहाँ $\mu$ इसके कठोरता से जुड़े घटकों के मध्य किनारों की संख्या है।^[6]^[7]^[8]^[9]

वर्तमान में शोध ने मैपरेडइयूस प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल विधियों का पता लगाया है।^[10]

यह भी देखें

पैतृक संबंध
निगमनात्मक समापन
प्रतिवर्ती समापन
सममित समापन
सकर्मक कमी (एक सबसे छोटा संबंध जिसमें R का सकर्मक समापन इसके सकर्मक समापन के रूप में होता है)

संदर्भ

↑ McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics, 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101
↑ (Libkin 2004:vii)
↑ (Libkin 2004:49)
↑ (Silberschatz et al. 2010:C.3.6)
↑ "पुनरावर्ती सामान्य तालिका अभिव्यक्तियाँ अवलोकन". mariadb.com.
↑ Purdom Jr., Paul (Mar 1970). "एक सकर्मक समापन एल्गोरिथ्म". BIT Numerical Mathematics. 10 (1): 76–94. doi:10.1007/BF01940892.
↑ Paul W. Purdom Jr. (Jul 1968). एक सकर्मक समापन एल्गोरिथ्म (Computer Sciences Technical Report). Vol. 33. University of Wisconsin-Madison.
↑ ""Purdom's algorithm" on AlgoWiki".
↑ ""Transitive closure of a directed graph" on AlgoWiki".
↑ (Afrati et al. 2011)

Foto N. Afrati, Vinayak Borkar, Michael Carey, Neoklis Polyzotis, Jeffrey D. Ullman, Map-Reduce Extensions and Recursive Queries, EDBT 2011, March 22–24, 2011, Uppsala, Sweden, ISBN 978-1-4503-0528-0
Aho, A. V.; Ullman, J. D. (1979). "Universality of data retrieval languages". Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of programming languages - POPL '79. pp. 110–119. doi:10.1145/567752.567763.
Benedikt, M.; Senellart, P. (2011). "Databases". In Blum, Edward K.; Aho, Alfred V. (eds.). Computer Science. The Hardware, Software and Heart of It. pp. 169–229. doi:10.1007/978-1-4614-1168-0_10. ISBN 978-1-4614-1167-3.
Heinz-Dieter Ebbinghaus; Jörg Flum (1999). Finite Model Theory (2nd ed.). Springer. pp. 123–124, 151–161, 220–235. ISBN 978-3-540-28787-2.
M.J. Fischer and A.R. Meyer (Oct 1971). "Boolean matrix multiplication and transitive closure" (PDF). In Raymond E. Miller and John E. Hopcroft (ed.). Proc. 12th Ann. Symp. on Switching and Automata Theory (SWAT). IEEE Computer Society. pp. 129–131. doi:10.1109/SWAT.1971.4.
Erich Grädel; Phokion G. Kolaitis; Leonid Libkin; Maarten Marx; Joel Spencer; Moshe Y. Vardi; Yde Venema; Scott Weinstein (2007). Finite Model Theory and Its Applications. Springer. pp. 151–152. ISBN 978-3-540-68804-4.
Keller, U., 2004, Some Remarks on the Definability of Transitive Closure in First-order Logic and Datalog (unpublished manuscript)* Libkin, Leonid (2004), Elements of Finite Model Theory, Springer, ISBN 978-3-540-21202-7
Lidl, R.; Pilz, G. (1998), Applied abstract algebra, Undergraduate Texts in Mathematics (2nd ed.), Springer, ISBN 0-387-98290-6
Munro, Ian (Jan 1971). "Efficient determination of the transitive closure of a directed graph". Information Processing Letters. 1 (2): 56–58. doi:10.1016/0020-0190(71)90006-8.
Nuutila, Esko (1995). Efficient transitive closure computation in large digraphs. Finnish Academy of Technology. ISBN 951-666-451-2. OCLC 912471702.
Abraham Silberschatz; Henry Korth; S. Sudarshan (2010). Database System Concepts (6th ed.). McGraw-Hill. ISBN 978-0-07-352332-3. Appendix C (online only)

बाहरी संबंध

"Transitive closure and reduction", The Stony Brook Algorithm Repository, Steven Skiena.

[1] McColl, W. F.; Noshita, K. (1986), "On the number of edges in the transitive closure of a graph", Discrete Applied Mathematics, 15 (1): 67–73, doi:10.1016/0166-218X(86)90020-X, MR 0856101

[2] (Libkin 2004:vii)

[3] (Libkin 2004:49)

[4] (Silberschatz et al. 2010:C.3.6)

[5] "पुनरावर्ती सामान्य तालिका अभिव्यक्तियाँ अवलोकन". mariadb.com.

[Purdom-6] Purdom Jr., Paul (Mar 1970). "एक सकर्मक समापन एल्गोरिथ्म". BIT Numerical Mathematics. 10 (1): 76–94. doi:10.1007/BF01940892.

[7] Paul W. Purdom Jr. (Jul 1968). एक सकर्मक समापन एल्गोरिथ्म (Computer Sciences Technical Report). Vol. 33. University of Wisconsin-Madison.

[8] ""Purdom's algorithm" on AlgoWiki".

[9] ""Transitive closure of a directed graph" on AlgoWiki".

[10] (Afrati et al. 2011)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{Short description|Smallest transitive relation containing a given binary relation}}
-{{About|the transitive closure of a binary relation|the transitive closure of a set|transitive set#Transitive closure}}
+{{About|एक द्विआधारी संबंध का सकर्मक समापन|एक सेट का सकर्मक समापन|सकर्मक समुच्चय #सकर्मक समापन}}
-गणित में, [[द्विआधारी संबंध]] का सकर्मक समापन {{mvar|R}} सेट पर (गणित) {{mvar|X}} पर सबसे छोटा [[संबंध (गणित)]] है {{mvar|X}} उसमें सम्मिलित है {{mvar|R}} और [[सकर्मक संबंध]] है. परिमित समुच्चयों के लिए, सबसे छोटे को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत सेटों के लिए यह अद्वितीय [[न्यूनतम तत्व]] सकर्मक [[सुपरसेट]] है {{math|''R''}}.
+'''गणित में, [[द्विआधारी संबंध]] का सकर्मक समापन {{mvar|R}} समुच्चय {{mvar|X}} पर (गणित)  पर सबसे छोटा [[संबंध (गणित)]] है {{mvar|X}} उसमें सम्मिलित है {{mvar|R}} और [[सकर्मक संबंध]] है. परिमित समुच्चयों के लिए, सबसे छोटे को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत समुच्चयों  के लिए यह अद्वितीय [[न्यूनतम तत्व]] सकर्मक [[सुपरसेट]] है {{math|''R''}}.'''
-उदाहरण के लिए, यदि {{mvar|X}}हवाई अड्डों का समूह है और {{mvar|x R y}}मतलब एयरपोर्ट से सीधी फ्लाइट है {{mvar|x}} हवाई अड्डे के लिए {{mvar|y}}  (के लिए {{mvar|x}} और {{mvar|y}} में {{mvar|X}}), फिर का सकर्मक समापन {{mvar|R}} पर {{mvar|X}}संबंध है {{math|''R''{{sup|+}}}} ऐसा है कि {{math|''x'' ''R''{{sup|+}} ''y''}} यानी इससे उड़ान भरना संभव है {{mvar|x}} को {{mvar|y}} या अधिक उड़ानों में। अनौपचारिक रूप से, ट्रांजिटिव क्लोजर आपको उन सभी स्थानों का सेट देता है जहां आप किसी भी शुरुआती स्थान से पहुंच सकते हैं।
+गणित में, समुच्चय {{mvar|X}} पर  [[द्विआधारी संबंध]] {{mvar|R}} का सकर्मक समापन, ''X'' पर सबसे छोटा [[संबंध (गणित)]] है इसमें ''R'' सम्मिलित होते  है और यह [[सकर्मक संबंध]]  होते है। परिमित समुच्चयों  के लिए, "सबसे छोटे" को उसके सामान्य अर्थ में लिया जा सकता है, जिसमें सबसे कम संबंधित जोड़े होते हैं; अनंत समुच्चयों के लिए यह ''R'' का अद्वितीय [[न्यूनतम तत्व]] सकर्मक '''[[सुपरसेट]]'''  है।
-अधिक औपचारिक रूप से, द्विआधारी संबंध का सकर्मक समापन {{mvar|R}} सेट पर {{mvar|X}} सकर्मक संबंध है {{math|''R''{{sup|+}}}} सेट पर {{mvar|X}} ऐसा है कि {{math|''R''{{sup|+}}}} रोकना {{mvar|R}} और {{math|''R''{{sup|+}}}} न्यूनतम है; देखना {{harvtxt|Lidl|Pilz|1998|p=337}}. यदि द्विआधारी संबंध स्वयं सकर्मक है, तो सकर्मक समापन वही द्विआधारी संबंध है; अन्यथा, सकर्मक समापन अलग संबंध है।
+इस प्रकार से उदाहरण के लिए, यदि {{mvar|X}} हवाई अड्डों का एक समूह है और {{mvar|x R y}} का अर्थ है "हवाई अड्डे {{mvar|X}} से हवाई अड्डे {{mvar|y}} के लिए सीधी उड़ान है" ({{mvar|x}} में {{mvar|X}} और {{mvar|y}} के लिए), तो उस {{math|''x'' ''R''{{sup|+}} ''y''}}  का अर्थ है "एक या अधिक उड़ानों में {{mvar|X}} से {{mvar|y}} तक उड़ान भरना संभव होता  है"। अनौपचारिक रूप से, ट्रांजिटिव क्लोजर आपको उन सभी स्थानों का सेट देता है जहां आप किसी भी प्रारंभिक  स्थान से पहुंच सकते हैं।
-इसके विपरीत, [[सकर्मक कमी]] न्यूनतम संबंध जोड़ती है {{mvar|S}} किसी दिए गए संबंध से {{mvar|R}} जैसे कि उनका समापन ही है, अर्थात, {{math|1=''S''{{sup|+}} = ''R''{{sup|+}}}}; हालाँकि, कई भिन्न {{mvar|S}} इस संपत्ति के साथ मौजूद हो सकता है।
+अधिक औपचारिक रूप से, द्विआधारी संबंध का सकर्मक समापन {{mvar|R}} समुच्चय {{mvar|X}}  पर  सकर्मक संबंध है  समुच्चय {{math|''R''{{sup|+}}}} पर {{mvar|X}} ऐसा है कि {{math|''R''{{sup|+}}}} रोकना {{mvar|R}} और {{math|''R''{{sup|+}}}} न्यूनतम है; देखना {{harvtxt|Lidl|Pilz|1998|p=337}}. यदि द्विआधारी संबंध स्वयं सकर्मक है, तो सकर्मक समापन वही द्विआधारी संबंध है; अन्यथा, सकर्मक समापन अलग संबंध है।
-सकर्मक समापन और सकर्मक कमी दोनों का उपयोग [[ग्राफ सिद्धांत]] के निकट से संबंधित क्षेत्र में भी किया जाता है।
+इसके विपरीत, [[सकर्मक कमी|संक्रमणीय कमी]]  न्यूनतम संबंध {{mvar|S}} से जोड़ती है किन्तु  किसी दिए गए संबंध  {{mvar|R}} से  जैसे कि उनका समापन  {{math|1=''S''{{sup|+}} = ''R''{{sup|+}}}} ही है ; चूंकि , कई भिन्न {{mvar|S}} इस संपत्ति के साथ उपस्तिथ   हो सकता है।
+अतः सकर्मक समापन और संक्रमणीय कमी  दोनों का उपयोग [[ग्राफ सिद्धांत]] के निकट से संबंधित क्षेत्र में भी किया जाता है।
 == सकर्मक संबंध और उदाहरण ==
-समुच्चय X पर संबंध R सकर्मक है यदि, X में सभी x, y, z के लिए, जब भी {{nowrap|''x R y''}} और {{nowrap|''y R z''}} तब {{nowrap|''x R z''}}. सकर्मक संबंधों के उदाहरणों में किसी भी सेट पर समानता संबंध, किसी भी रैखिक रूप से आदेशित सेट पर कम या बराबर संबंध, और सभी लोगों के सेट पर संबंध x का जन्म y से पहले हुआ था। प्रतीकात्मक रूप से, इसे इस प्रकार दर्शाया जा सकता है: यदि {{nowrap|''x'' < ''y''}} और {{nowrap|''y'' < ''z''}} तब {{nowrap|''x'' < ''z''}}.
+इस प्रकार से समुच्चय ''X'' पर संबंध ''R'' सकर्मक है यदि, ''X'' में सभी ''x, y, z'' के लिए, जब भी {{nowrap|''x R y''}} और {{nowrap|''y R z''}} तब {{nowrap|''x R z''}}. सकर्मक संबंधों के उदाहरणों में किसी भी समुच्चय  पर समानता संबंध, किसी भी रैखिक रूप से आदेशित समुच्चय  पर कम या समान  संबंध, और सभी लोगों के समुच्चय  पर संबंध x का जन्म y से पहले हुआ था। और  प्रतीकात्मक रूप से, इसे इस प्रकार दर्शाया जा सकता है: यदि {{nowrap|''x'' < ''y''}} और {{nowrap|''y'' < ''z''}} तब {{nowrap|''x'' < ''z''}}. प्राप्त होता है
-गैर-संक्रमणीय संबंध का उदाहरण यह है कि शहर x तक सभी शहरों के सेट पर शहर y से सीधी उड़ान के माध्यम से पहुंचा जा सकता है। सिर्फ इसलिए कि शहर से दूसरे शहर के लिए सीधी उड़ान है, और दूसरे शहर से तीसरे शहर के लिए सीधी उड़ान है, इसका मतलब यह नहीं है कि पहले शहर से तीसरे शहर के लिए सीधी उड़ान है। इस संबंध का सकर्मक समापन अलग संबंध है, अर्थात् सीधी उड़ानों का क्रम है जो शहर x से शुरू होता है और शहर y पर समाप्त होता है। प्रत्येक संबंध को सकर्मक संबंध के समान ही बढ़ाया जा सकता है।
+किन्तु गैर-संक्रमणीय संबंध का उदाहरण इस प्रकार से  है कि शहर ''x'' तक सभी शहरों ''y''  के समुच्चय  पर शहर से सीधी उड़ान के माध्यम से पहुंचा जा सकता है। और  इसके अतिरिक्त  शहर से दूसरे शहर के लिए सीधी उड़ान है, और दूसरे शहर से तीसरे शहर के लिए सीधी उड़ान होती है, इसका मतलब यह नहीं  है कि पहले शहर से तीसरे शहर के लिए सीधी उड़ान है। इस संबंध का सकर्मक समापन अलग संबंध है, अर्थात् सीधी उड़ानों का क्रम है जो शहर x से प्रारंभ  होता है और शहर y पर समाप्त होता है। प्रत्येक संबंध को सकर्मक संबंध के समान ही बढ़ाया जा सकता है।
-कम सार्थक सकर्मक समापन के साथ गैर-संक्रमणीय संबंध का उदाहरण है x, y के बाद [[सप्ताह का दिन]] है। इस संबंध का सकर्मक समापन कैलेंडर पर दिन y के बाद आने वाला कोई दिन है, जो सप्ताह के सभी दिनों x और y के लिए तुच्छ रूप से सत्य है (और इस प्रकार कार्टेशियन उत्पाद के बराबर है, जो कि x और y दोनों दिन हैं) सप्ताह )।
+कम सार्थक सकर्मक समापन के साथ एक गैर-संक्रमणीय संबंध का एक उदाहरण है "x, y के पश्चात  [[सप्ताह का दिन]] है"। इस संबंध का सकर्मक समापन "कुछ दिन x कैलेंडर पर एक दिन y के पश्चात  आता है" है, जो सप्ताह के सभी दिनों ''x'' और ''y'' के लिए तुच्छ रूप से सत्य है (और इस प्रकार कार्टेशियन वर्ग के समान  है, जो कि ''"x'' और ''y'' हैं सप्ताह के दोनों दिन")।
 ==अस्तित्व और विवरण==
-किसी भी संबंध R के लिए, R का सकर्मक समापन हमेशा मौजूद रहता है। इसे देखने के लिए, ध्यान दें कि सकर्मक संबंधों के किसी भी [[अनुक्रमित परिवार]] का [[प्रतिच्छेदन (सेट सिद्धांत)]] फिर से सकर्मक है। इसके अलावा, आर युक्त कम से कम सकर्मक संबंध मौजूद है, अर्थात् तुच्छ एक: एक्स × एक्स। आर का सकर्मक समापन तब आर युक्त सभी सकर्मक संबंधों के प्रतिच्छेदन द्वारा दिया जाता है।
+इस प्रकार से किसी भी संबंध R के लिए, R का सकर्मक समापन सदैव  उपस्तिथ   रहता है। और इसे देखने के लिए, ध्यान दें कि सकर्मक संबंधों के किसी भी [[अनुक्रमित परिवार]] का [[प्रतिच्छेदन (सेट सिद्धांत)|प्रतिच्छेदन (समुच्चय  सिद्धांत)]] पुनः  से सकर्मक है। इसके अतिरिक्त , ''R'',  युक्त कम से कम सकर्मक संबंध उपस्तिथ होते   है, अर्थात् तुच्छ एक: ''X  × X'' । आर का सकर्मक समापन तब ''R'', युक्त सभी सकर्मक संबंधों के प्रतिच्छेदन द्वारा दिया जाता है।
-परिमित सेटों के लिए, हम आर से शुरू करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं।
+परिमित समुच्चयों  के लिए, हम ''R'' से प्रारंभ  करके और संक्रमणीय किनारों को जोड़कर चरण दर चरण संक्रमणीय समापन का निर्माण कर सकते हैं।
-यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी सेट एक्स के लिए, हम
-यह साबित कर सकता है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है
+यह सामान्य निर्माण के लिए अंतर्ज्ञान देता है। किसी भी समुच्चय  ''X'', के लिए, हम
+यह प्रमाणित  कर सकता है कि सकर्मक समापन निम्नलिखित अभिव्यक्ति द्वारा दिया गया है
 :<math>R^{+}=\bigcup_{i = 1}^{\infty} R^i.</math>
-कहाँ <math>R^i</math> R की i-वीं शक्ति है, जिसे आगमनात्मक रूप से परिभाषित किया गया है
+जहाँ  <math>R^i</math> R की ''i''-th पावर  है, जिसे आगमनात्मक रूप से परिभाषित किया गया है
 :<math>R^1 = R</math>
 और के लिए <math>i>0</math>,
 :<math>R^{i+1} = R \circ R^i</math>
-कहाँ <math>\circ</math> [[संबंधों की संरचना]] को दर्शाता है.
+जहाँ  <math>\circ</math> [[संबंधों की संरचना]] को दर्शाता है.
-यह दर्शाने के लिए कि R की उपरोक्त परिभाषा<sup>+</sup> R युक्त सबसे कम सकर्मक संबंध है, हम दिखाते हैं कि इसमें R शामिल है, कि यह सकर्मक है, और यह उन दोनों विशेषताओं के साथ सबसे छोटा सेट है।
+इस प्रकार से यह दर्शाने के लिए कि ''R<sup>+</sup>'' की उपरोक्त परिभाषा ''R'' युक्त सबसे कम सकर्मक संबंध है, हम दिखाते हैं कि इसमें ''R'' सम्मिलित  है, कि यह सकर्मक है, और यह उन दोनों विशेषताओं के साथ सबसे छोटा समुच्चय  है।
-* <math>R \subseteq R^{+}</math>: <math> R^+</math> सभी शामिल हैं <math> R^i</math>, इसलिए विशेष रूप से <math> R^+</math> रोकना <math> R</math>.
+* <math>R \subseteq R^{+}</math>: <math> R^+</math> सभी सम्मिलित  हैं <math> R^i</math>, इसलिए विशेष रूप से <math> R^+</math> रोकना <math> R</math>.
 * <math> R^{+}</math> सकर्मक है: यदि <math>(s_1, s_2), (s_2, s_3)\in R^+</math>, तब <math>(s_1, s_2)\in R^j</math> और <math>(s_2, s_3)\in R^k</math> कुछ के लिए <math>j,k</math> की परिभाषा के अनुसार <math>R^+</math>. चूँकि रचना साहचर्य है, <math>R^{j+k} = R^j \circ R^k</math>; इस तरह <math>(s_1, s_3)\in R^{j+k} \subseteq R^+</math> की परिभाषा के अनुसार <math>\circ</math> और <math>R^+</math>.
-* <math>R^{+}</math> न्यूनतम है, अर्थात यदि <math>T</math> कोई सकर्मक संबंध युक्त है <math>R</math>, तब <math>R^{+} \subseteq T</math>: ऐसा कोई दिया गया <math>T</math>, [[गणितीय प्रेरण]] पर <math>i</math> दिखाने के लिए उपयोग किया जा सकता है <math>R^i\subseteq T</math> सभी के लिए <math>i</math> इस प्रकार: आधार: <math>R^1 = R \subseteq T</math> अनुमान से. चरण: यदि <math>R^i\subseteq T</math> धारण करता है, और <math>(s_1, s_3)\in R^{i+1} = R \circ R^i</math>, तब <math>(s_1, s_2) \in R</math> और <math>(s_2, s_3)\in R^i</math> कुछ के लिए <math>s_2</math>, की परिभाषा के अनुसार <math>\circ</math>. इस तरह, <math>(s_1, s_2), (s_2, s_3)\in T</math> धारणा द्वारा और प्रेरण परिकल्पना द्वारा। इस तरह <math>(s_1, s_3)\in T</math> की परिवर्तनशीलता द्वारा <math>T</math>; यह प्रेरण पूरा करता है। आखिरकार, <math>R^i\subseteq T</math> सभी के लिए <math>i</math> तात्पर्य <math>R^{+} \subseteq T</math> की परिभाषा के अनुसार <math>R^{+}</math>.
+* <math>R^{+}</math> न्यूनतम है, अर्थात यदि <math>T</math> कोई सकर्मक संबंध युक्त है <math>R</math>, तब <math>R^{+} \subseteq T</math>: ऐसा कोई दिया गया <math>T</math>, [[गणितीय प्रेरण]] पर <math>i</math> दिखाने के लिए उपयोग किया जा सकता है <math>R^i\subseteq T</math> सभी के लिए <math>i</math> इस प्रकार: आधार: <math>R^1 = R \subseteq T</math> अनुमान से. चरण: यदि <math>R^i\subseteq T</math> धारण करता है, और <math>(s_1, s_3)\in R^{i+1} = R \circ R^i</math>, तब <math>(s_1, s_2) \in R</math> और <math>(s_2, s_3)\in R^i</math> कुछ के लिए <math>s_2</math>, की परिभाषा के अनुसार <math>\circ</math>. इस तरह, <math>(s_1, s_2), (s_2, s_3)\in T</math> धारणा द्वारा और प्रेरण परिकल्पना द्वारा। इस तरह <math>(s_1, s_3)\in T</math> की परिवर्तनशीलता द्वारा <math>T</math>; यह प्रेरण पूरा करता है। इस प्रकार से , <math>R^i\subseteq T</math> सभी के लिए <math>i</math> तात्पर्य <math>R^{+} \subseteq T</math> की परिभाषा <math>R^{+}</math> के अनुसार .
 == गुण ==
-दो सकर्मक संबंधों का प्रतिच्छेदन (सेट सिद्धांत) सकर्मक है।
+इस प्रकार से दो सकर्मक संबंधों का प्रतिच्छेदन (समुच्चय  सिद्धांत) सकर्मक है।
-दो सकर्मक संबंधों का मिलन (सेट सिद्धांत) सकर्मक होना आवश्यक नहीं है। सकर्मकता को संरक्षित करने के लिए, व्यक्ति को सकर्मक समापन लेना होगा। ऐसा तब होता है, उदाहरण के लिए, जब दो [[समतुल्य संबंध]]ों या दो पूर्व-आदेशों का मिलन होता है। नया तुल्यता संबंध या [[पूर्व आदेश]] प्राप्त करने के लिए व्यक्ति को ट्रांजिटिव क्लोजर (रिफ्लेक्सिविटी और समरूपता - तुल्यता संबंधों के मामले में - स्वचालित हैं) लेना होगा।
+दो सकर्मक संबंधों का मिलन (समुच्चय  सिद्धांत) सकर्मक होना आवश्यक नहीं है। सकर्मकता को संरक्षित करने के लिए, व्यक्ति को सकर्मक समापन लेना होगा। ऐसा तब होता है, उदाहरण के लिए, जब दो [[समतुल्य संबंध]] या दो पूर्व-आदेशों का संबंध होता है। और नया तुल्यता संबंध या [[पूर्व आदेश]] प्राप्त करने के लिए व्यक्ति को ट्रांजिटिव क्लोजर (रिफ्लेक्सिविटी और समरूपता - तुल्यता संबंधों के स्तिथियो  में - स्वचालित हैं) लेना होता है ।
 == ग्राफ़ सिद्धांत में ==
-[[File:Transitive-closure.svg|thumb|right|alt=Transitive closure constructs the output graph from the input graph.|ट्रांसिटिव क्लोजर इनपुट ग्राफ से आउटपुट ग्राफ का निर्माण करता है।]][[कंप्यूटर विज्ञान]] में, ट्रांजिटिव क्लोजर की अवधारणा को डेटा संरचना के निर्माण के रूप में सोचा जा सकता है जो [[गम्यता]] प्रश्नों का उत्तर देना संभव बनाता है। यानी, क्या कोई या अधिक हॉप्स में नोड ए से नोड डी तक पहुंच सकता है? द्विआधारी संबंध आपको केवल यह बताता है कि नोड ए नोड बी से जुड़ा है, और वह नोड बी नोड सी से जुड़ा है, आदि। ट्रांजिटिव क्लोजर के निर्माण के बाद, जैसा कि निम्नलिखित चित्र में दर्शाया गया है, Big_O_notation#Orders_of_common_functions|O(1) में ) ऑपरेशन यह निर्धारित कर सकता है कि नोड डी नोड ए से पहुंच योग्य है। डेटा संरचना को आम तौर पर बूलियन मैट्रिक्स के रूप में संग्रहीत किया जाता है, इसलिए यदि मैट्रिक्स [1] [4] = सत्य है, तो यह मामला है कि नोड 1 या अधिक हॉप्स के माध्यम से नोड 4 तक पहुंच सकता है।
+[[File:Transitive-closure.svg|thumb|right|alt=Transitive closure constructs the output graph from the input graph.|ट्रांसिटिव क्लोजर इनपुट ग्राफ से आउटपुट ग्राफ का निर्माण करता है।]]इस प्रकार से [[कंप्यूटर विज्ञान]] में, ट्रांजिटिव क्लोजर की अवधारणा को डेटा संरचना के निर्माण के रूप में विचार किया  जा सकता है जोकी  [[गम्यता]] प्रश्नों का उत्तर देना संभव बनाता है। अर्थात , क्या कोई या अधिक हॉप्स में नोड ''A''  से नोड ''d'' तक पहुंच सकता है? द्विआधारी संबंध आपको केवल यह बताता है कि नोड ''A'' नोड ''b'' से जुड़ा है, और वह नोड ''b'' नोड सी से जुड़ा है, आदि। ट्रांजिटिव क्लोजर के निर्माण के पश्चात , जैसा कि निम्नलिखित चित्र में दर्शाया गया है, '''Big_O_notation#Orders_of_common_functions'''|O(1) में ) ऑपरेशन यह निर्धारित कर सकता है कि नोड ''d'' नोड ''a'' से पहुंच योग्य है। डेटा संरचना को सामान्यतः  बूलियन मैट्रिक्स के रूप में संग्रहीत किया जाता है, इसलिए यदि मैट्रिक्स [1] [4] = सत्य है, तो यह स्तिथि  है कि नोड 1 या अधिक हॉप्स के माध्यम से नोड 4 तक पहुंच सकता है।
-एक [[निर्देशित अचक्रीय ग्राफ]] (डीएजी) के आसन्न संबंध का सकर्मक समापन डीएजी का पहुंच योग्यता संबंध और [[सख्त आंशिक आदेश]] है।
+इस प्रकार से [[निर्देशित अचक्रीय ग्राफ]] (डीएजी) के आसन्न संबंध का सकर्मक समापन डीएजी का पहुंच योग्यता संबंध और [[सख्त आंशिक आदेश]] है।
-[[File:Equivalentie.svg|thumb|एक [[क्लस्टर ग्राफ़]], अप्रत्यक्ष ग्राफ़ का सकर्मक समापन]]एक [[अप्रत्यक्ष ग्राफ]]़ का सकर्मक समापन क्लस्टर ग्राफ़ उत्पन्न करता है, जो क्लिक (ग्राफ़ सिद्धांत) के ग्राफ़ का असंयुक्त संघ है। ट्रांजिटिव क्लोजर का निर्माण ग्राफ के [[घटक (ग्राफ सिद्धांत)]] को खोजने की समस्या का समतुल्य सूत्रीकरण है।<ref>{{citation
+[[File:Equivalentie.svg|thumb|एक [[क्लस्टर ग्राफ़]], अप्रत्यक्ष ग्राफ़ का सकर्मक समापन]]एक [[अप्रत्यक्ष ग्राफ]] का सकर्मक समापन क्लस्टर ग्राफ़ उत्पन्न करता है, जोकी  क्लिक (ग्राफ़ सिद्धांत) के ग्राफ़ का असंयुक्त संघ है। ट्रांजिटिव क्लोजर का निर्माण ग्राफ के [[घटक (ग्राफ सिद्धांत)]] को खोजने की समस्या का समतुल्य सूत्रीकरण है।<ref>{{citation
   | last1 = McColl | first1 = W. F.
   | last2 = Noshita | first2 = K.
@@ Line 60: / Line 64: @@
   | volume = 15
   | year = 1986}}</ref>
+== तर्क और कम्प्यूटेशनल जटिलता में ==
+इस प्रकार से किसी द्विआधारी संबंध का सकर्मक समापन, सामान्य तौर पर, [[प्रथम-क्रम तर्क]] (एफओ) में व्यक्त नहीं किया जा सकता है।
+किन्तु इसका मतलब यह है कि कोई भी विधेय प्रतीकों ''R''  और ''T'' का उपयोग करके सूत्र नहीं लिख सकता है जो संतुष्ट हो जाएगा
-== तर्क और कम्प्यूटेशनल जटिलता में ==
+कोई भी मॉडल यदि और केवल यदि T, R का सकर्मक समापन है।
-किसी द्विआधारी संबंध का सकर्मक समापन, सामान्य तौर पर, [[प्रथम-क्रम तर्क]] (एफओ) में व्यक्त नहीं किया जा सकता है।
-इसका मतलब यह है कि कोई भी विधेय प्रतीकों आर और टी का उपयोग करके सूत्र नहीं लिख सकता है जो संतुष्ट हो जाएगा
+इस प्रकार से [[परिमित मॉडल सिद्धांत]] में, ट्रांजिटिव क्लोजर ऑपरेटर के साथ विस्तारित प्रथम-क्रम तर्क (एफओ) को सामान्यतः  'ट्रांसिटिव क्लोजर लॉजिक' कहा जाता है, और संक्षिप्त रूप से FO (टीसी) या सिर्फ TC कहा जाता है। TC फिक्सप्वाइंट लॉजिक्स का उप-प्रकार है। तथ्य यह है कि FO (टीसी) FO की तुलना में सख्ती से अधिक अभिव्यंजक है, इसकी खोज [[रोनाल्ड फागिन]] ने 1974 में की थी; परिणाम को इस प्रकार से 1979 में  [[ मैं अल्फ्रेड हूं |मैं अल्फ्रेड हूं]]  और [[जेफरी उलमन]] द्वारा पुनः  से खोजा गया, जिन्होंने [[डेटाबेस क्वेरी भाषा]] के रूप में [[फिक्सपॉइंट तर्क]] का उपयोग करने का प्रस्ताव रखा गया था ।<ref>(Libkin 2004:vii)</ref> और  परिमित मॉडल सिद्धांत की नवीनतम अवधारणाओं के साथ, यह प्रमाण कि FO (टीसी) FO की तुलना में सख्ती से अधिक अभिव्यंजक है, इस तथ्य से तुरंत पता चलता है कि FO (टीसी) गैफमैन-स्थानीय नहीं होते है।<ref>(Libkin 2004:49)</ref>
-कोई भी मॉडल यदि और केवल यदि T, R का सकर्मक समापन है।
-[[परिमित मॉडल सिद्धांत]] में, ट्रांजिटिव क्लोजर ऑपरेटर के साथ विस्तारित प्रथम-क्रम तर्क (एफओ) को आमतौर पर 'ट्रांसिटिव क्लोजर लॉजिक' कहा जाता है, और संक्षिप्त रूप से एफओ (टीसी) या सिर्फ टीसी कहा जाता है। टीसी फिक्सप्वाइंट लॉजिक्स का उप-प्रकार है। तथ्य यह है कि एफओ (टीसी) एफओ की तुलना में सख्ती से अधिक अभिव्यंजक है, इसकी खोज [[रोनाल्ड फागिन]] ने 1974 में की थी; परिणाम को 1979 में  [[ मैं अल्फ्रेड हूं |मैं अल्फ्रेड हूं]]  और [[जेफरी उलमन]] द्वारा फिर से खोजा गया, जिन्होंने [[डेटाबेस क्वेरी भाषा]] के रूप में [[फिक्सपॉइंट तर्क]] का उपयोग करने का प्रस्ताव रखा।<ref>(Libkin 2004:vii)</ref> परिमित मॉडल सिद्धांत की नवीनतम अवधारणाओं के साथ, यह प्रमाण कि एफओ (टीसी) एफओ की तुलना में सख्ती से अधिक अभिव्यंजक है, इस तथ्य से तुरंत पता चलता है कि एफओ (टीसी) गैफमैन-स्थानीय नहीं है।<ref>(Libkin 2004:49)</ref>
+इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] एन[[एल (जटिलता)]] टीसी में व्यक्त तार्किक वाक्यों के समुच्चय  से स्पष्ट  रूप से मेल खाती है। ऐसा इसलिए है क्योंकि ट्रांज़िटिव क्लोजर प्रॉपर्टी का ग्राफ़ में [[निर्देशित पथ]] खोजने के लिए [[एनएल-पूर्ण]] समस्या [[STCON|एसटीसीओएन]]  के साथ घनिष्ठ संबंध होता  है। इसी प्रकार, वर्ग एल (जटिलता) क्रमविनिमेय, सकर्मक समापन के साथ प्रथम-क्रम तर्क है। जब इसके अतिरिक्त  दूसरे क्रम के तर्क में ट्रांजिटिव क्लोजर जोड़ा जाता है, तो हमें [[PSPACE|पीस्पेस]] प्राप्त होता है।
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] एन[[एल (जटिलता)]] टीसी में व्यक्त तार्किक वाक्यों के सेट से सटीक रूप से मेल खाती है। ऐसा इसलिए है क्योंकि ट्रांज़िटिव क्लोजर प्रॉपर्टी का ग्राफ़ में [[निर्देशित पथ]] खोजने के लिए [[एनएल-पूर्ण]] समस्या [[STCON]] के साथ घनिष्ठ संबंध है। इसी प्रकार, वर्ग एल (जटिलता) क्रमविनिमेय, सकर्मक समापन के साथ प्रथम-क्रम तर्क है। जब इसके बजाय दूसरे क्रम के तर्क में ट्रांजिटिव क्लोजर जोड़ा जाता है, तो हमें [[PSPACE]] प्राप्त होता है।
 == डेटाबेस क्वेरी भाषाओं में ==
-{{further|Hierarchical and recursive queries in SQL}}
+{{further|SQL में पदानुक्रमित और पुनरावर्ती क्वेरीज़}}
-के दशक से Oracle डेटाबेस ने मालिकाना [[SQL]] एक्सटेंशन लागू किया है <code>CONNECT BY... START WITH</code> यह घोषणात्मक क्वेरी के भाग के रूप में सकर्मक समापन की गणना की अनुमति देता है। [[SQL 3]] (1999) मानक ने और अधिक सामान्य जोड़ा <code>WITH RECURSIVE</code> निर्माण क्वेरी प्रोसेसर के अंदर ट्रांजिटिव क्लोजर की गणना करने की भी अनुमति देता है; 2011 तक बाद वाले को [[IBM Db2]], [[Microsoft SQL Server]], Oracle डेटाबेस, [[PostgreSQL]] और [[MySQL]] (v8.0+) में लागू किया गया है। [[SQLite]] ने 2014 में इसके लिए समर्थन जारी किया।
-[[ संगणक वैज्ञानिक | संगणक वैज्ञानिक]]  ट्रांजिटिव क्लोजर गणनाओं को भी लागू करता है।<ref>(Silberschatz et al. 2010:C.3.6)</ref>
+के दशक से आकाशवाणी  डेटाबेस ने मालिकाना  [[SQL|एसक्यूएल]] एक्सटेंशन प्रयुक्त   किया है <code>CONNECT BY... START WITH</code> यह घोषणात्मक क्वेरी के भाग के रूप में सकर्मक समापन की गणना की अनुमति देता है। [[SQL 3|एसक्यूएल 3]] (1999) मानक ने और अधिक सामान्य जोड़ा <code>WITH RECURSIVE</code> निर्माण क्वेरी प्रोसेसर के अंदर ट्रांजिटिव क्लोजर की गणना करने की भी अनुमति देता है; 2011 तक पश्चात  वाले को [[Microsoft SQL Server|आईबीएम डीबी2, माइक्रोसॉफ्ट एसक्यूएल सर्वर]], आकाशवाणी  डेटाबेस, [[PostgreSQL|पोस्टग्रेएसक्यूएल]] और [[MySQL|माई एसक्यूएल]] (v8.0+) में प्रयुक्त   किया गया है। और  [[SQLite|एसक्यूलाइट]]  ने 2014 में इसके लिए समर्थन उपयोग  किया गया था ।
-[[MariaDB]] रिकर्सिव कॉमन टेबल एक्सप्रेशन लागू करता है, जिसका उपयोग ट्रांजिटिव क्लोजर की गणना करने के लिए किया जा सकता है। यह सुविधा अप्रैल 2016 की रिलीज़ 10.2.2 में पेश की गई थी।<ref>{{cite web| title=पुनरावर्ती सामान्य तालिका अभिव्यक्तियाँ अवलोकन| url=https://mariadb.com/kb/en/recursive-common-table-expressions-overview/| publisher=mariadb.com}}</ref>
+इस प्रकार से [[ संगणक वैज्ञानिक | संगणक वैज्ञानिक]]  ट्रांजिटिव क्लोजर गणनाओं को भी प्रयुक्त   करता है।<ref>(Silberschatz et al. 2010:C.3.6)</ref>
+[[MariaDB|मारियाडीबी]]  रिकर्सिव कॉमन टेबल एक्सप्रेशन प्रयुक्त   करता है, जिसका उपयोग ट्रांजिटिव क्लोजर की गणना करने के लिए किया जा सकता है। यह सुविधा अप्रैल 2016 की रिलीज़ 10.2.2 में उपस्तिथ  की गई थी।<ref>{{cite web| title=पुनरावर्ती सामान्य तालिका अभिव्यक्तियाँ अवलोकन| url=https://mariadb.com/kb/en/recursive-common-table-expressions-overview/| publisher=mariadb.com}}</ref>
 == एल्गोरिदम ==
-ग्राफ़ के आसन्न संबंध के सकर्मक समापन की गणना के लिए कुशल एल्गोरिदम यहां पाए जा सकते हैं {{harvtxt|Nuutila|1995}}. आसन्न मैट्रिक्स के गुणन की समस्या को कम करने से न्यूनतम उपलब्धि प्राप्त होती है{{citation needed|date=February 2022}} समय जटिलता, अर्थात। [[मैट्रिक्स गुणन]] ({{harvnb|Munro|1971}}, {{harvnb|Fischer|Meyer|1971}}), जो है <math>O(n^{2.3728596})</math> {{as of|2020|12|lc=y}}. हालाँकि, यह दृष्टिकोण व्यावहारिक नहीं है क्योंकि विरल ग्राफ़ के लिए स्थिर कारक और मेमोरी खपत दोनों अधिक हैं {{harv|Nuutila|1995|pp=22–23|loc=sect.2.3.3}}. समस्या को फ़्लॉइड-वॉर्शल एल्गोरिथम द्वारा भी हल किया जा सकता है <math>O(n^3)</math>, या ग्राफ़ के प्रत्येक नोड से शुरू होने वाली बार-बार चौड़ाई-पहली खोज या [[गहराई-पहली खोज]] द्वारा।
+इस प्रकार से ग्राफ़ के आसन्न संबंध के सकर्मक समापन की गणना के लिए कुशल एल्गोरिदम यहां पाए जा सकते हैं {{harvtxt|नुउटिला|1995}}. आसन्न मैट्रिक्स के गुणन की समस्या को कम करने से न्यूनतम उपलब्धि प्राप्त होती है समय जटिलता, अर्थात। [[मैट्रिक्स गुणन]] ({{harvnb|मुनरो|1971}}, {{harvnb|फिशर|मेयेर|1971}}), जो है <math>O(n^{2.3728596})</math> {{as of|2020|12|lc=y}}. चूंकि , यह दृष्टिकोण व्यावहारिक नहीं है क्योंकि विरल ग्राफ़ के लिए स्थिर कारक और मेमोरी खपत दोनों अधिक हैं {{harv|नुउटिला|1995|pp=22–23|loc=sect.2.3.3}}. समस्या को फ़्लॉइड-वॉर्शल एल्गोरिथम  <math>O(n^3)</math>, द्वारा भी हल किया जा सकता है या ग्राफ़ के प्रत्येक नोड से प्रारंभ  होने वाली बार-बार चौड़ाई-पहली खोज या [[गहराई-पहली खोज]] द्वारा किया गया था ।
-निर्देशित ग्राफ़ के लिए, Purdom का एल्गोरिदम पहले इसके संक्षेपण DAG और इसके संक्रमणीय समापन की गणना करके, फिर इसे मूल ग्राफ़ पर उठाकर समस्या का समाधान करता है। इसका रनटाइम है <math>O(m+\mu n)</math>, कहाँ <math>\mu</math> इसके मजबूती से जुड़े घटकों के बीच किनारों की संख्या है।<ref name=Purdom>{{cite journal | doi=10.1007/BF01940892 | url= | first=Paul |last=Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| journal=[[BIT Numerical Mathematics]] | volume=10 | number=1 | pages=76&ndash;94 | date=Mar 1970 }}</ref><ref>{{cite report | url=https://minds.wisconsin.edu/handle/1793/57514 | author=Paul W. Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| institution=[[University of Wisconsin-Madison]] | type=Computer Sciences Technical Report | volume=33 | date=Jul 1968 }}</ref><ref>{{cite web
+इस प्रकार से निर्देशित ग्राफ़ के लिए, पर्डोम का एल्गोरिदम पहले इसके संक्षेपण डीएजी  और इसके संक्रमणीय समापन की गणना करके, पुनः  इसे मूल ग्राफ़ पर उठाकर समस्या का समाधान करता है। इसका रनटाइम <math>O(m+\mu n)</math> है , जहाँ  <math>\mu</math> इसके कठोरता   से जुड़े घटकों के मध्य   किनारों की संख्या है।<ref name=Purdom>{{cite journal | doi=10.1007/BF01940892 | url= | first=Paul |last=Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| journal=[[BIT Numerical Mathematics]] | volume=10 | number=1 | pages=76&ndash;94 | date=Mar 1970 }}</ref><ref>{{cite report | url=https://minds.wisconsin.edu/handle/1793/57514 | author=Paul W. Purdom Jr. | title=एक सकर्मक समापन एल्गोरिथ्म| institution=[[University of Wisconsin-Madison]] | type=Computer Sciences Technical Report | volume=33 | date=Jul 1968 }}</ref><ref>{{cite web
 | url=https://algowiki-project.org/algowiki/en/index.php?title=Purdom%27s_algorithm&oldid=10286
 | title="Purdom's algorithm" on AlgoWiki}}</ref><ref>{{cite web
 | url=https://algowiki-project.org/algowiki/en/index.php?title=Transitive_closure_of_a_directed_graph&oldid=1475
 | title="Transitive closure of a directed graph" on AlgoWiki}}</ref>
-हाल के शोध ने [[MapReduce]] प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल तरीकों का पता लगाया है।<ref>(Afrati et al. 2011)</ref>
+वर्तमान में  शोध ने [[MapReduce|मैपरेडइयूस]]    प्रतिमान के आधार पर वितरित सिस्टम पर ट्रांजिटिव क्लोजर की गणना करने के कुशल विधियों  का पता लगाया है।<ref>(Afrati et al. 2011)</ref>
 == यह भी देखें ==
 *[[पैतृक संबंध]]
@@ Line 91: / Line 98: @@
 * [[ प्रतिवर्ती समापन ]]
 * [[सममित समापन]]
-* सकर्मक कमी (आर के सकर्मक समापन के रूप में इसके सकर्मक समापन वाला सबसे छोटा संबंध)
+* सकर्मक कमी (एक सबसे छोटा संबंध जिसमें ''R'' का सकर्मक समापन इसके सकर्मक समापन के रूप में होता है)
 == संदर्भ ==

Anonymous

Search

सकर्मक समापन: Difference between revisions

Namespaces

More

Page actions

Revision as of 11:33, 10 July 2023

Contents

सकर्मक संबंध और उदाहरण

अस्तित्व और विवरण

गुण

ग्राफ़ सिद्धांत में

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

डेटाबेस क्वेरी भाषाओं में

एल्गोरिदम

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

सकर्मक समापन: Difference between revisions

Revision as of 11:33, 10 July 2023

सकर्मक संबंध और उदाहरण

अस्तित्व और विवरण

गुण

ग्राफ़ सिद्धांत में

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

डेटाबेस क्वेरी भाषाओं में

एल्गोरिदम

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories