रेडिएटर संख्या

स्ट्राहलर स्ट्रीम क्रम दर्शाने वाला आरेख

गणित में, गणितीय वृक्ष (ग्राफ सिद्धांत) की स्ट्राहलर संख्या या हॉर्टन-स्ट्राहलर संख्या इसकी शाखा जटिलता का एक संख्यात्मक माप है।

इन नंबरों को सबसे पहले जल विज्ञान में नदियों और झरनों की जटिलता को मापने के एक तरीके के रूप में विकसित किया गया था Robert E. Horton (1945) और Arthur Newell Strahler (1952, 1957). इस एप्लिकेशन में, उन्हें स्ट्राहलर स्ट्रीम ऑर्डर के रूप में संदर्भित किया जाता है और सहायक नदी के पदानुक्रम के आधार पर स्ट्रीम आकार को परिभाषित करने के लिए उपयोग किया जाता है। उच्च-स्तरीय प्रोग्रामिंग भाषाओं के संकलक के लिए रजिस्टर आवंटन और सामाजिक नेटवर्क के विश्लेषण में एल प्रणाली और पदानुक्रमित जैविक संरचनाओं जैसे (जैविक) पेड़ों और पशु श्वसन और परिसंचरण प्रणालियों के विश्लेषण में भी वही संख्याएं उत्पन्न होती हैं।

परिभाषा

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

• यदि नोड एक पत्ता है (इसकी कोई संतान नहीं है), तो इसका स्ट्राहलर नंबर एक है।
• यदि नोड में स्ट्राहलर संख्या i वाला एक बच्चा है, और अन्य सभी बच्चों की स्ट्राहलर संख्या i से कम है, तो नोड का स्ट्राहलर संख्या फिर से i है।
• यदि नोड में स्ट्राहलर संख्या i वाले दो या दो से अधिक बच्चे हैं, और अधिक संख्या वाले कोई संतान नहीं है, तो नोड की स्ट्राहलर संख्या i + 1 है।

किसी पेड़ की स्ट्राहलर संख्या उसके मूल नोड की संख्या होती है।

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

स्ट्राहलर नंबर i वाले किसी भी नोड में स्ट्राहलर नंबर i - 1 के साथ कम से कम दो वंशज होने चाहिए, स्ट्राहलर नंबर i - 2, आदि के साथ कम से कम चार वंशज होने चाहिए, और कम से कम 2^{i − 1}पत्ती वंशज। इसलिए, n नोड्स वाले पेड़ में, सबसे बड़ी संभव स्ट्राहलर संख्या लॉग है₂एन+1. हालाँकि, जब तक पेड़ एक पूर्ण द्विआधारी वृक्ष नहीं बनाता, तब तक इसकी स्ट्राहलर संख्या इस सीमा से कम होगी। एन-नोड बाइनरी ट्री मेंयादृच्छिक बाइनरी पेड़ ट्री चुना जाता है, रूट का अपेक्षित सूचकांक उच्च संभावना के साथ लॉग के बहुत करीब होता है₄एन।

अनुप्रयोग

नदी नेटवर्क

जल विज्ञान के लिए स्ट्राहलर धारा क्रम के अनुप्रयोग में, नदी नेटवर्क के भीतर एक धारा या नदी के प्रत्येक खंड को एक पेड़ में एक नोड के रूप में माना जाता है, और अगले खंड को उसके मूल के रूप में नीचे की ओर माना जाता है। जब दो प्रथम क्रम की धाराएँ एक साथ आती हैं, तो वे दूसरे क्रम की धारा बनाती हैं। जब दो दूसरे क्रम की धाराएँ एक साथ आती हैं, तो वे तीसरे क्रम की धारा बनाती हैं। निचले क्रम की धाराएँ उच्च क्रम की धारा में शामिल होने से उच्च धारा का क्रम नहीं बदलती हैं। इस प्रकार, यदि प्रथम-क्रम की धारा दूसरे-क्रम की धारा से जुड़ती है, तो यह दूसरे-क्रम की धारा बनी रहती है। ऐसा तब तक नहीं है जब तक कि एक दूसरे क्रम की धारा दूसरे दूसरे क्रम की धारा के साथ संयोजित न हो जाए कि वह तीसरे क्रम की धारा बन जाए। गणितीय पेड़ों की तरह, सूचकांक i वाले एक खंड को कम से कम 2 द्वारा खिलाया जाना चाहिए^{i − 1}सूचकांक 1 की विभिन्न सहायक नदियाँ। श्रेव ने नोट किया कि हॉर्टन और स्ट्राहलर के नियमों की किसी भी टोपोलॉजिकली यादृच्छिक वितरण से अपेक्षा की जानी चाहिए। रिश्तों की एक बाद की समीक्षा ने इस तर्क की पुष्टि की, यह स्थापित करते हुए कि, कानूनों द्वारा वर्णित गुणों से, स्ट्रीम नेटवर्क की संरचना या उत्पत्ति की व्याख्या करने के लिए कोई निष्कर्ष नहीं निकाला जा सकता है। एक जलधारा के रूप में अर्हता प्राप्त करने के लिए जलवैज्ञानिक विशेषता या तो आवर्ती या बारहमासी धारा होनी चाहिए। आवर्ती (या रुक-रुक कर) धाराओं में वर्ष के कम से कम भाग के लिए चैनल में पानी रहता है। किसी धारा या नदी का सूचकांक 1 (बिना सहायक नदी वाली धारा) से 12 (विश्व स्तर पर सबसे शक्तिशाली नदी, अमेज़ॅन नदी, इसके मुहाने पर) तक हो सकता है। ओहियो नदी क्रम आठ की है और मिसिसिपी नदी क्रम 10 की है। अनुमान है कि ग्रह पर 80% धाराएँ पहले से तीसरे क्रम की हेडवाटर धाराएँ हैं। यदि नदी नेटवर्क का द्विभाजन अनुपात अधिक है, तो बाढ़ की संभावना अधिक है। एकाग्रता का समय भी कम होगा। अलग-अलग अनुपातों को देखकर, द्विभाजन अनुपात यह भी दिखा सकता है कि जल निकासी बेसिन के किन हिस्सों में बाढ़ आने की संभावना अधिक है। अधिकांश ब्रिटिश नदियों का द्विभाजन अनुपात 3 और 5 के बीच है।

जल निकायों के वृक्ष नेटवर्क में गलत और सही रूपांतरण की तुलना

Gleyzer et al. (2004) वर्णन करें कि भौगोलिक सूचना प्रणाली अनुप्रयोग में स्ट्राहलर स्ट्रीम ऑर्डर मानों की गणना कैसे करें। यह एल्गोरिदम RivEX, एक ESRI Arcgis 10.7 टूल द्वारा कार्यान्वित किया गया है। उनके एल्गोरिदम का इनपुट पानी के पिंडों की केंद्र रेखाओं का एक नेटवर्क है, जिसे नोड्स पर जुड़े आर्क (या किनारों) के रूप में दर्शाया जाता है। झील की सीमाओं और नदी के किनारों को चाप के रूप में उपयोग नहीं किया जाना चाहिए, क्योंकि ये आम तौर पर गलत टोपोलॉजी के साथ एक गैर-वृक्ष नेटवर्क बनाएंगे।

वैकल्पिक धारा क्रम श्रेव द्वारा विकसित किया गया है और हॉजकिंसन एट अल। स्ट्रीम/लिंक लंबाई के विश्लेषण के साथ स्ट्राहलर और श्रेवे सिस्टम की एक सांख्यिकीय तुलना, स्मार्ट द्वारा दी गई है।

अन्य पदानुक्रमित प्रणालियाँ

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

• Arenas et al. (2004) सामाजिक नेटवर्क के विश्लेषण में हॉर्टन-स्ट्राहलर सूचकांक के अनुप्रयोग का वर्णन करें।
• Ehrenfeucht, Rozenberg & Vermeir (1981) ने एल-सिस्टम के विश्लेषण के लिए स्ट्राहलर नंबरिंग का एक प्रकार लागू किया (पत्तियों पर एक के बजाय शून्य से शुरू), जिसे उन्होंने ट्री-रैंक कहा।
• स्ट्रैलर नंबरिंग को पेड़ों की शाखा संरचनाओं जैसे जैविक पदानुक्रमों पर भी लागू किया गया है और जानवरों की श्वसन और संचार प्रणाली।

आवंटन पंजीकृत करें

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

संबंधित पैरामीटर

द्विभाजन अनुपात

किसी पेड़ की स्ट्राहलर संख्याओं के साथ द्विभाजन अनुपात जुड़े होते हैं, संख्याएँ बताती हैं कि एक पेड़ संतुलित होने के कितने करीब है। पदानुक्रम में प्रत्येक क्रम के लिए, ith द्विभाजन अनुपात है

${\frac {n_{i}}{n_{i+1}}}$

कहां एन_iक्रम i के साथ नोड्स की संख्या को दर्शाता है।

समग्र पदानुक्रम का द्विभाजन अनुपात विभिन्न क्रमों पर द्विभाजन अनुपातों के औसत से लिया जा सकता है। एक पूर्ण बाइनरी पेड़ में, द्विभाजन अनुपात 2 होगा, जबकि अन्य पेड़ों में बड़ा द्विभाजन अनुपात होगा। यह एक आयामहीन संख्या है.

पथविड्थ

एक मनमाना अप्रत्यक्ष ग्राफ G की पथ चौड़ाई को सबसे छोटी संख्या w के रूप में परिभाषित किया जा सकता है, जैसे कि एक अंतराल ग्राफ H मौजूद है जिसमें G को एक सबग्राफ के रूप में शामिल किया गया है, H में सबसे बड़े क्लिक (ग्राफ सिद्धांत) में w + 1 कोने हैं। पेड़ों के लिए (उनके अभिविन्यास और जड़ को भूलकर अप्रत्यक्ष ग्राफ़ के रूप में देखा जाता है) पथ चौड़ाई स्ट्राहलर संख्या से भिन्न होती है, लेकिन इसके साथ निकटता से संबंधित होती है: पथ चौड़ाई डब्ल्यू और स्ट्राहलर संख्या एस वाले पेड़ में, ये दो संख्याएं असमानताओं से संबंधित होती हैं

w ≤ s ≤ 2w + 2.

चक्रों के साथ ग्राफ़ को संभालने की क्षमता, न कि केवल पेड़ों के साथ, स्ट्राहलर संख्या की तुलना में पथ-चौड़ाई को अतिरिक्त बहुमुखी प्रतिभा प्रदान करती है। हालाँकि, स्ट्राहलर संख्या के विपरीत, पथविड्थ केवल पूरे ग्राफ़ के लिए परिभाषित किया गया है, और ग्राफ़ में प्रत्येक नोड के लिए अलग से नहीं।

यह भी देखें

• नदी का मुख्य तना, आम तौर पर उच्चतम स्ट्राहलर संख्या वाली शाखा का अनुसरण करके पाया जाता है
• Pfafstetter कोडिंग प्रणाली

संदर्भ

• Arenas, A.; Danon, L.; Díaz-Guilera, A.; Gleiser, P. M.; Guimerá, R. (2004), "Community analysis in social networks", European Physical Journal B, 38 (2): 373–380, arXiv:cond-mat/0312040, Bibcode:2004EPJB...38..373A, doi:10.1140/epjb/e2004-00130-1, S2CID 9764926.
• Borchert, Rolf; Slade, Norman A. (1981), "Bifurcation ratios and the adaptive geometry of trees", Botanical Gazette, 142 (3): 394–401, doi:10.1086/337238, hdl:1808/9253, JSTOR 2474363, S2CID 84145477.
• Devroye, Luc; Kruszewski, Paul (1995), "A note on the Horton–Strahler number for random trees", Information Processing Letters, 56 (2): 95–99, doi:10.1016/0020-0190(95)00114-R.
• Devroye, L.; Kruszewski, P. (1996), "On the Horton–Strahler number for random tries", RAIRO Informatique Théorique et Applications, 30 (5): 443–456, doi:10.1051/ita/1996300504431, MR 1435732
• Ehrenfeucht, A.; Rozenberg, G.; Vermeir, D. (1981), "On ETOL systems with finite tree-rank", SIAM Journal on Computing, 10 (1): 40–58, doi:10.1137/0210004, MR 0605602.
• Ershov, A. P. (1958), "On programming of arithmetic operations", Communications of the ACM, 1 (8): 3–6, doi:10.1145/368892.368907, S2CID 15986378.
• Flajolet, P.; Raoult, J. C.; Vuillemin, J. (1979), "The number of registers required for evaluating arithmetic expressions", Theoretical Computer Science, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4.
• Gleyzer, A.; Denisyuk, M.; Rimmer, A.; Salingar, Y. (2004), "A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks", Journal of the American Water Resources Association, 40 (4): 937–946, Bibcode:2004JAWRA..40..937G, doi:10.1111/j.1752-1688.2004.tb01057.x, S2CID 128399321.
• Horsfield, Keith (1976), "Some mathematical properties of branching trees with application to the respiratory system", Bulletin of Mathematical Biology, 38 (3): 305–315, doi:10.1007/BF02459562, PMID 1268383, S2CID 189888885.
• Horton, R. E. (1945), "Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology", Geological Society of America Bulletin, 56 (3): 275–370, doi:10.1130/0016-7606(1945)56[275:EDOSAT]2.0.CO;2, S2CID 129509551.
• Lanfear, K. J. (1990), "A fast algorithm for automatically computing Strahler stream order", Journal of the American Water Resources Association, 26 (6): 977–981, Bibcode:1990JAWRA..26..977L, doi:10.1111/j.1752-1688.1990.tb01432.x.
• Luttenberger, Michael; Schlund, Maxmilian (2011), An extension of Parikh's theorem beyond idempotence, arXiv:1112.2864, Bibcode:2011arXiv1112.2864L
• Strahler, A. N. (1952), "Hypsometric (area-altitude) analysis of erosional topology", Geological Society of America Bulletin, 63 (11): 1117–1142, doi:10.1130/0016-7606(1952)63[1117:HAAOET]2.0.CO;2.
• Strahler, A. N. (1957), "Quantitative analysis of watershed geomorphology", Transactions of the American Geophysical Union, 38 (6): 913–920, Bibcode:1957TrAGU..38..913S, doi:10.1029/tr038i006p00913.
• Waugh, David (2002), Geography, An Integrated Approach (3rd ed.), Nelson Thornes.