गम्यता - Revision history

Manidh at 08:33, 3 August 2023

2023-08-03T08:33:54Z

@@ Line 147: / Line 147: @@
 ==संदर्भ                                                                                                                                                                                                                                                             ==
 {{reflist}}
 [[Category:Created On 27/06/2023]]
-[[Category:Vigyan Ready]]
+[[Category:Lua-based templates]]

Indicwiki: 8 revisions imported from :alpha:गम्यता

2023-08-03T05:34:18Z

8 revisions imported from alpha:गम्यता

← Older revision	Revision as of 11:04, 3 August 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-08-02T11:03:00Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 16:33, 2 August 2023
Line 153:		Line 153:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]
			[[Category:Vigyan Ready]]

alpha>Saurabh at 16:08, 30 July 2023

2023-07-30T16:08:13Z

Show changes

alpha>Saurabh at 05:14, 10 July 2023

2023-07-10T05:14:20Z

← Older revision		Revision as of 10:44, 10 July 2023
Line 6:		Line 6:

	== परिभाषा ==		== परिभाषा ==
	एक निर्देशित ग्राफ़ <math>G = (V, E)</math> के लिए , शीर्ष ~~सेट~~ <math>V</math> के साथ और किनारा ~~सेट~~ <math>E</math>, गम्यता सम्बन्ध (गणित) का <math>G</math> का [[सकर्मक समापन]] <math>E</math> है , जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय <math>(s,t)</math> शीर्षों में से <math>V</math> जिसके लिए शीर्षों का क्रम उपस्थित है <math>v_0 = s, v_1, v_2, ..., v_k = t</math> ऐसे कि किनारा<math>(v_{i-1},v_i)</math> सभी <math>1 \leq i \leq k</math> के लिए <math>E</math> में है.<ref name="skiena">{{citation		एक निर्देशित ग्राफ़ <math>G = (V, E)</math> के लिए , शीर्ष समुच्चय <math>V</math> के साथ और किनारा समुच्चय <math>E</math>, गम्यता सम्बन्ध (गणित) का <math>G</math> का [[सकर्मक समापन]] <math>E</math> है , जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय <math>(s,t)</math> शीर्षों में से <math>V</math> जिसके लिए शीर्षों का क्रम उपस्थित है <math>v_0 = s, v_1, v_2, ..., v_k = t</math> ऐसे कि किनारा<math>(v_{i-1},v_i)</math> सभी <math>1 \leq i \leq k</math> के लिए <math>E</math> में है.<ref name="skiena">{{citation
	\| last = Skiena \| first = Steven S.		\| last = Skiena \| first = Steven S.
	\| contribution = 15.5 Transitive Closure and Reduction		\| contribution = 15.5 Transitive Closure and Reduction
Line 80:		Line 80:
	\| year = 2004\| s2cid = 18864647 }}.</ref> यह विधि समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है <math>O(1)</math> व्यय करने के बाद का समय <math>O(n \log{n})</math> डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय <math>O(n \log{n})</math> आकार यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।		\| year = 2004\| s2cid = 18864647 }}.</ref> यह विधि समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है <math>O(1)</math> व्यय करने के बाद का समय <math>O(n \log{n})</math> डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय <math>O(n \log{n})</math> आकार यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।

	समग्र दृष्टिकोण प्रत्येक शीर्ष के साथ तथाकथित विभाजक पथों का अपेक्षाकृत छोटा ~~सेट~~ जोड़ना है जैसे कि शीर्ष से कोई भी पथ <math>v</math> किसी अन्य शीर्ष पर <math>w</math> से जुड़े विभाजकों में से कम से कम से निकलना होगा <math>v</math> या <math>w</math>. पहुंच योग्यता से संबंधित अनुभागों की रूपरेखा इस प्रकार है।		समग्र दृष्टिकोण प्रत्येक शीर्ष के साथ तथाकथित विभाजक पथों का अपेक्षाकृत छोटा समुच्चय जोड़ना है जैसे कि शीर्ष से कोई भी पथ <math>v</math> किसी अन्य शीर्ष पर <math>w</math> से जुड़े विभाजकों में से कम से कम से निकलना होगा <math>v</math> या <math>w</math>. पहुंच योग्यता से संबंधित अनुभागों की रूपरेखा इस प्रकार है।

	एक ग्राफ दिया गया <math>G</math>, एल्गोरिथ्म इच्छानुसार शीर्ष से प्रारंभ होकर शीर्षों को परतों <math>v_0</math> में व्यवस्थित करने से प्रारंभ होता है . परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से प्रारंभ करके)। <math>v_0</math>) और फिर सभी शीर्ष जो पिछले चरण तक पहुंचते हैं जब तक कि सभी शीर्षों को परत को नहीं सौंपा जाता है। परतों के निर्माण से, प्रत्येक शीर्ष अधिकतम दो परतों में दिखाई देता है, और प्रत्येक पथ (ग्राफ़ सिद्धांत) विभिन्न प्रकार के पथ, या डिपाथ, में <math>G</math> दो आसन्न परतों के अन्दर <math>L_i</math> और <math>L_{i+1}</math> समाहित है . माना <math>k</math> बनाई गई अंतिम परत बनें, अर्थात, इसके लिए सबसे कम मान <math>k</math> ऐसा है कि <math>\bigcup_{i=0}^{k} L_i = V</math>.		एक ग्राफ दिया गया <math>G</math>, एल्गोरिथ्म इच्छानुसार शीर्ष से प्रारंभ होकर शीर्षों को परतों <math>v_0</math> में व्यवस्थित करने से प्रारंभ होता है . परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से प्रारंभ करके)। <math>v_0</math>) और फिर सभी शीर्ष जो पिछले चरण तक पहुंचते हैं जब तक कि सभी शीर्षों को परत को नहीं सौंपा जाता है। परतों के निर्माण से, प्रत्येक शीर्ष अधिकतम दो परतों में दिखाई देता है, और प्रत्येक पथ (ग्राफ़ सिद्धांत) विभिन्न प्रकार के पथ, या डिपाथ, में <math>G</math> दो आसन्न परतों के अन्दर <math>L_i</math> और <math>L_{i+1}</math> समाहित है . माना <math>k</math> बनाई गई अंतिम परत बनें, अर्थात, इसके लिए सबसे कम मान <math>k</math> ऐसा है कि <math>\bigcup_{i=0}^{k} L_i = V</math>.
Line 87:		Line 87:
	G_{k-1}</math> के रूप में व्यक्त किया जाता है जहां प्रत्येक <math>G_i = r_i \cup L_i \cup L_{i+1}</math> और जहाँ <math>r_i</math> पिछले सभी स्तरों <math>L_0 \ldots L_{i-1}</math> का संकुचन है एक ही शीर्ष में. क्योंकि प्रत्येक द्विपथ अधिकतम दो निरंतर परतों में प्रकट होता है, और क्योंकि प्रत्येक <math>G_i</math> प्रत्येक द्विपथ में दो निरंतर परतों द्वारा निर्मित होता है <math>G</math> कम से कम में अपनी संपूर्णता <math>G_i</math> में प्रकट होता है (और निरंतर 2 से अधिक ऐसे ग्राफ़ नहीं)		G_{k-1}</math> के रूप में व्यक्त किया जाता है जहां प्रत्येक <math>G_i = r_i \cup L_i \cup L_{i+1}</math> और जहाँ <math>r_i</math> पिछले सभी स्तरों <math>L_0 \ldots L_{i-1}</math> का संकुचन है एक ही शीर्ष में. क्योंकि प्रत्येक द्विपथ अधिकतम दो निरंतर परतों में प्रकट होता है, और क्योंकि प्रत्येक <math>G_i</math> प्रत्येक द्विपथ में दो निरंतर परतों द्वारा निर्मित होता है <math>G</math> कम से कम में अपनी संपूर्णता <math>G_i</math> में प्रकट होता है (और निरंतर 2 से अधिक ऐसे ग्राफ़ नहीं)

	प्रत्येक के लिए <math>G_i</math>, तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं <math>1/2</math> मूल के शीर्ष. जैसा <math>G_i</math> विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। माना <math>S</math> दीपपथों का यह ~~सेट~~ हो। इस बात का प्रमाण कि ऐसे विभाजक सदैव पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।		प्रत्येक के लिए <math>G_i</math>, तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं <math>1/2</math> मूल के शीर्ष. जैसा <math>G_i</math> विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। माना <math>S</math> दीपपथों का यह समुच्चय हो। इस बात का प्रमाण कि ऐसे विभाजक सदैव पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।

	प्रत्येक के लिए <math>Q \in S</math>, की निर्देशित प्रकृति <math>Q</math> पथ के आरंभ से अंत तक इसके शीर्षों का प्राकृतिक अनुक्रमण प्रदान करता है। प्रत्येक शीर्ष के लिए <math>v</math> में <math>G_i</math>, हम पहले शीर्ष का पता लगाते हैं <math>Q</math> द्वारा पहुंच योग्य <math>v</math>, और अंतिम शीर्ष <math>Q</math> जो <math>v</math> पहुँच जाता है . अर्थात हम देख रहे हैं कि कितनी जल्दी <math>Q</math> हम से प्राप्त कर सकते हैं <math>v</math>, और कितनी दूर हम <math>Q</math> अंदर रह सकते हैं और अभी भी वापस आएँ <math>v</math>. यह जानकारी संग्रहित की जाती है प्रत्येक <math>v</math>. फिर शीर्षों के किसी भी जोड़े के लिए <math>u</math> और <math>w</math>, <math>u</math> तक पहुँच सकते हैं <math>w</math> के जरिए <math>Q</math> यदि <math>u</math> से जुड़ता है <math>Q</math> से जल्दी <math>w</math> से <math>Q</math> जुड़ता है .		प्रत्येक के लिए <math>Q \in S</math>, की निर्देशित प्रकृति <math>Q</math> पथ के आरंभ से अंत तक इसके शीर्षों का प्राकृतिक अनुक्रमण प्रदान करता है। प्रत्येक शीर्ष के लिए <math>v</math> में <math>G_i</math>, हम पहले शीर्ष का पता लगाते हैं <math>Q</math> द्वारा पहुंच योग्य <math>v</math>, और अंतिम शीर्ष <math>Q</math> जो <math>v</math> पहुँच जाता है . अर्थात हम देख रहे हैं कि कितनी जल्दी <math>Q</math> हम से प्राप्त कर सकते हैं <math>v</math>, और कितनी दूर हम <math>Q</math> अंदर रह सकते हैं और अभी भी वापस आएँ <math>v</math>. यह जानकारी संग्रहित की जाती है प्रत्येक <math>v</math>. फिर शीर्षों के किसी भी जोड़े के लिए <math>u</math> और <math>w</math>, <math>u</math> तक पहुँच सकते हैं <math>w</math> के जरिए <math>Q</math> यदि <math>u</math> से जुड़ता है <math>Q</math> से जल्दी <math>w</math> से <math>Q</math> जुड़ता है .

alpha>Saurabh at 04:55, 10 July 2023

2023-07-10T04:55:48Z

Show changes

alpha>Saurabh at 04:51, 10 July 2023

2023-07-10T04:51:53Z

← Older revision		Revision as of 10:21, 10 July 2023
Line 114:		Line 114:
	यदि <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ <math>O(n)</math> को प्रीप्रोसेस कर सकते हैं केवल समय और स्टोरेज <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देता है शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</math> साधारण के साथ समय तुलना करती है।		यदि <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ <math>O(n)</math> को प्रीप्रोसेस कर सकते हैं केवल समय और स्टोरेज <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देता है शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</math> साधारण के साथ समय तुलना करती है।

	प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम नया शीर्ष <math>s</math> जोड़ते हैं जिसमें प्रत्येक 0-डिग्री शीर्ष पर किनारा है, और अन्य नया शीर्ष है <math>t</math> प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के ~~साथ।~~ ध्यान दें कि के गुण <math>G</math> हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, अर्थात, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं ~~होगा।~~ प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम काउंटर आरंभ करते हैं <math>i = n + 1</math> और डेप्थ-फर्स्ट ट्रैवर्सल प्रारंभ करें <math>s</math>. इस ट्रैवर्सल के ~~दौरान~~, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है <math>i</math>, और <math>i</math> फिर घटाया जाता है. ध्यान दें कि <math>t</math> सदैव मूल्य के साथ लेबल किया जाता है <math>n+1</math> और <math>s</math> सदैव इसके ~~साथ लेबल किया जाता है~~ <math>0</math>. फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, किन्तु इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।		प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम नया शीर्ष <math>s</math> जोड़ते हैं जिसमें प्रत्येक 0-डिग्री शीर्ष पर किनारा है, और अन्य नया शीर्ष है <math>t</math> प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के साथ ध्यान दें कि के गुण <math>G</math> हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, अर्थात, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं होता है। प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम काउंटर आरंभ करते हैं <math>i = n + 1</math> और डेप्थ-फर्स्ट ट्रैवर्सल प्रारंभ करें <math>s</math>. इस ट्रैवर्सल के समय, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है <math>i</math>, और <math>i</math> फिर घटाया जाता है. ध्यान दें कि <math>t</math> सदैव मूल्य के साथ लेबल किया जाता है <math>n+1</math> और <math>s</math> सदैव इसके <math>0</math> साथ लेबल किया जाता है . फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, किन्तु इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।

	पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक
	~~शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</math>.~~
	दो शीर्ष दिए गए हैं <math>u</math> और <math>v</math>, और उनके लेबल <math>L(u) = (a_1, a_2)</math> और <math>L(v) =(b_1, b_2)</math>, हम ऐसा कहते हैं <math>L(u) < L(v)</math> यदि और केवल यदि <math>a_1 \leq b_1</math>, <math>a_2 \leq
	~~b_2</math>, और कम से कम घटक उपस्थित है <math>a_1</math> या <math>a_2</math> जो सख्ती से है~~
	~~से कम <math>b_1</math> या <math>b_2</math>, क्रमश।~~

	~~इस विधि का मुख्य परिणाम तो यही बताता~~ है <math>v</math> ~~से पहुंचा जा सकता है~~ <math>u</math> ~~यदि व~~		पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</math>.दो शीर्ष <math>u</math> और <math>v</math> दिए गए हैं , और उनके लेबल <math>L(u) = (a_1, a_2)</math> और <math>L(v) =(b_1, b_2)</math>, हम ऐसा कहते हैं <math>L(u) < L(v)</math> यदि और केवल यदि <math>a_1 \leq b_1</math>, <math>a_2 \leq
	~~केवल~~ <math>L(u) < L(v)</math>~~जिसकी गणना आसानी~~ से ~~की जा सकती~~ है <math>~~O(1)~~</math> ~~समय।~~		b_2</math>, और कम से कम घटक उपस्थित <math>a_1</math> या <math>a_2</math> है जो कठोर क्रमश <math>b_1</math> या <math>b_2</math>, है

	~~==संबंधित समस्याएँ==~~		इस विधि का मुख्य परिणाम तो यही बताता है <math>v</math> से पहुंचा जा सकता है <math>u</math> यदि व केवल <math>L(u) < L(v)</math>जिसकी गणना <math>O(1)</math> समय सरलता से की जा सकती है ।

	एक संबंधित समस्या कुछ संख्याओं के साथ गम्यता प्रश्नों को हल करना है <math>k</math> शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष ~~कर सकते हैं~~ <math>u</math> अभी भी शीर्ष पर पहुंचें <math>v</math> ~~भले ही~~ शीर्ष <math>s_1, s_2, ..., s_k</math> विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के अतिरिक्त किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, किन्तु कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है।<ref>{{citation		==संबंधित समस्याएँ ==

			एक संबंधित समस्या कुछ संख्याओं के साथ गम्यता प्रश्नों को हल करना है <math>k</math> शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष <math>u</math> कर सकते हैं अभी भी शीर्ष पर पहुंचें <math>v</math> संभवतः शीर्ष <math>s_1, s_2, ..., s_k</math> विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के अतिरिक्त किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, किन्तु कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है।<ref>{{citation
	\| last1 = Demetrescu \| first1 = Camil		\| last1 = Demetrescu \| first1 = Camil
	\| last2 = Thorup \| first2 = Mikkel \| author2-link = Mikkel Thorup		\| last2 = Thorup \| first2 = Mikkel \| author2-link = Mikkel Thorup
Line 143:		Line 140:
	\| title = Connectivity in Networks and Compact Labeling Schemes for Emergency Planning		\| title = Connectivity in Networks and Compact Labeling Schemes for Emergency Planning
	\| location = Universite de Bordeaux		\| location = Universite de Bordeaux
	\| url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref>		\| url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref> गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (जिससे इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।
	गम्यता प्रश्नों से संबंधित अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर गम्यता संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (~~ताकि~~ इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।

	== यह भी देखें ==		== यह भी देखें ==
	* [[गैमॉइड]]		* [[गैमॉइड]]
	* सेंट~~-कनेक्टिविटी\|एसटी~~-कनेक्टिविटी		* सेंट-कनेक्टिविटी

	==संदर्भ==		==संदर्भ ==
	{{reflist}}		{{reflist}}
	[[Category: ग्राफ़ कनेक्टिविटी]]		[[Category: ग्राफ़ कनेक्टिविटी]]

alpha>Saurabh at 04:33, 10 July 2023

2023-07-10T04:33:00Z

Show changes

alpha>Saurabh at 04:06, 10 July 2023

2023-07-10T04:06:13Z

Show changes

alpha>Indicwiki: Created page with "{{Short description|Whether one vertex can be reached from another in a graph}} ग्राफ सिद्धांत में, रीचैबिलिटी एक..."

2023-06-27T12:28:27Z

Created page with "{{Short description|Whether one vertex can be reached from another in a graph}} ग्राफ सिद्धांत में, रीचैबिलिटी एक..."

New page

{{Short description|Whether one vertex can be reached from another in a graph}}

[[ग्राफ सिद्धांत]] में, रीचैबिलिटी एक ग्राफ के भीतर एक वर्टेक्स (ग्राफ सिद्धांत) से दूसरे तक जाने की क्षमता को संदर्भित करती है। एक शिखर <math>s</math> एक शिखर तक पहुंच सकता है <math>t</math> (और <math>t</math> से पहुंचा जा सकता है <math>s</math>) यदि ग्राफ़ सिद्धांत # मूल शीर्ष (अर्थात एक पथ (ग्राफ़ सिद्धांत)) की शब्दावली का एक क्रम मौजूद है जो से शुरू होता है <math>s</math> और के साथ समाप्त होता है <math>t</math>.

एक अप्रत्यक्ष ग्राफ़ में, शीर्षों के सभी युग्मों के बीच पहुंच को ग्राफ़ के [[कनेक्टेड घटक (ग्राफ़ सिद्धांत)]] की पहचान करके निर्धारित किया जा सकता है। ऐसे ग्राफ़ में शीर्षों का कोई भी जोड़ा एक दूसरे तक पहुंच सकता है यदि वे एक ही जुड़े हुए घटक से संबंधित हों; इसलिए, ऐसे ग्राफ़ में, पहुंच योग्यता सममित है (<math>s</math> पहुँचती है <math>t</math> आईएफएफ <math>t</math> पहुँचती है <math>s</math>). अप्रत्यक्ष ग्राफ़ के जुड़े घटकों को रैखिक समय में पहचाना जा सकता है। इस आलेख का शेष भाग एक [[निर्देशित ग्राफ]]़ में जोड़ीवार पहुंच योग्यता निर्धारित करने की अधिक कठिन समस्या पर केंद्रित है (जो, संयोग से, सममित होने की आवश्यकता नहीं है)।

== परिभाषा ==
एक निर्देशित ग्राफ़ के लिए <math>G = (V, E)</math>, वर्टेक्स सेट के साथ <math>V</math> और किनारा सेट <math>E</math>, रीचैबिलिटी रिलेशन (गणित) का <math>G</math> का [[सकर्मक समापन]] है <math>E</math>, जिसका अर्थ है सभी क्रमित जोड़ियों का समुच्चय <math>(s,t)</math> शीर्षों में से <math>V</math> जिसके लिए शीर्षों का एक क्रम मौजूद है <math>v_0 = s, v_1, v_2, ..., v_k = t</math> ऐसे कि किनारा <math>(v_{i-1},v_i)</math> में है <math>E</math> सभी के लिए <math>1 \leq i \leq k</math>.<ref name="skiena">{{citation
| last = Skiena | first = Steven S.
| contribution = 15.5 Transitive Closure and Reduction
| edition = 2nd
| isbn = 9781848000698
| pages = 495–497
| publisher = Springer
| title = The Algorithm Design Manual
| url = https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA495
| year = 2011}}.</ref>
अगर <math>G</math> [[निर्देशित अचक्रीय ग्राफ]] है, तो इसका रीचैबिलिटी संबंध आंशिक क्रम है; किसी भी [[आंशिक आदेश]] को इस तरह से परिभाषित किया जा सकता है, उदाहरण के लिए इसकी [[सकर्मक कमी]] के पहुंच योग्यता संबंध के रूप में।<ref>{{citation
| last = Cohn | first = Paul Moritz
| isbn = 9781852335878
| page = 17
| publisher = Springer
| title = Basic Algebra: Groups, Rings, and Fields
| url = https://books.google.com/books?id=VESm0MJOiDQC&pg=PA17
| year = 2003}}.</ref> इसका एक उल्लेखनीय परिणाम यह है कि चूंकि आंशिक आदेश सममित-विरोधी हैं, यदि <math>s</math> तक पहुँच सकते हैं <math>t</math>, तो हम उसे जानते हैं <math>t</math> नहीं पहूंच सकता <math>s</math>. सहज रूप से, यदि हम यात्रा कर सकें <math>s</math> को <math>t</math> और वापस <math>s</math>, तब <math>G</math> इसमें एक चक्र (ग्राफ़ सिद्धांत) शामिल होगा, जो इस बात का खंडन करता है कि यह चक्रीय है।
अगर <math>G</math> निर्देशित है, लेकिन चक्रीय नहीं है (अर्थात इसमें कम से कम एक चक्र शामिल है), तो इसका पहुंच योग्यता संबंध आंशिक आदेश के बजाय [[पूर्व आदेश]] के अनुरूप होगा।<ref>{{citation
| last = Schmidt | first = Gunther
| isbn = 9780521762687
| page = 77
| publisher = Cambridge University Press
| series = Encyclopedia of Mathematics and Its Applications
| title = Relational Mathematics
| url = https://books.google.com/books?id=E4dREBTs5WsC&pg=PA559
| volume = 132
| year = 2010}}.</ref>

== एल्गोरिदम ==
रीचैबिलिटी निर्धारित करने के लिए एल्गोरिदम दो वर्गों में आते हैं: वे जिनमें [[डेटा प्री-प्रोसेसिंग]] की आवश्यकता होती है और वे जो नहीं करते हैं।

यदि आपके पास बनाने के लिए केवल एक (या कुछ) प्रश्न हैं, तो अधिक जटिल डेटा संरचनाओं का उपयोग छोड़ना और वांछित जोड़ी की पहुंच की सीधे गणना करना अधिक कुशल हो सकता है। इसे चौड़ाई पहली खोज या [[पुनरावृत्तीय गहनता गहराई-पहली खोज]] जैसे एल्गोरिदम का उपयोग करके [[रैखिक समय]] में पूरा किया जा सकता है।<ref>{{citation
| last = Gersting | first = Judith L. | author-link = Judith Gersting
| edition = 6th
| isbn = 9780716768647
| page = 519
| publisher = Macmillan
| title = Mathematical Structures for Computer Science
| url = https://books.google.com/books?id=lvAo3AeJikQC&pg=PA519
| year = 2006}}.</ref>
यदि आप कई प्रश्न पूछ रहे होंगे, तो अधिक परिष्कृत विधि का उपयोग किया जा सकता है; विधि का सटीक चुनाव विश्लेषण किए जा रहे ग्राफ़ की प्रकृति पर निर्भर करता है। प्रीप्रोसेसिंग समय और कुछ अतिरिक्त भंडारण स्थान के बदले में, हम एक डेटा संरचना बना सकते हैं जो किसी भी जोड़े पर पहुंच योग्य प्रश्नों का उत्तर कम से कम समय में दे सकती है। <math>O(1)</math> समय। तीन अलग-अलग, तेजी से विशिष्ट स्थितियों के लिए तीन अलग-अलग एल्गोरिदम और डेटा संरचनाएं नीचे उल्लिखित हैं।

=== फ़्लॉइड-वॉर्शल एल्गोरिथम ===

फ्लोयड-वॉर्शल एल्गोरिथ्म<ref>{{citation
| last1 = Cormen | first1 = Thomas H. | author1-link = Thomas H. Cormen
| last2 = Leiserson | first2 = Charles E. | author2-link = Charles E. Leiserson
| last3 = Rivest | first3 = Ronald L. | author3-link = Ronald L. Rivest
| last4 = Stein | first4 = Clifford | author4-link = Clifford Stein
| contribution = Transitive closure of a directed graph
| edition = 2nd
| isbn = 0-262-03293-7
| pages = 632–634
| publisher = MIT Press and McGraw-Hill
| title = [[Introduction to Algorithms]]
| year = 2001}}.</ref> किसी भी निर्देशित ग्राफ के ट्रांजिटिव क्लोजर की गणना करने के लिए इसका उपयोग किया जा सकता है, जो उपरोक्त परिभाषा के अनुसार रीचैबिलिटी संबंध को जन्म देता है।

एल्गोरिदम की आवश्यकता है <math>O(|V|^3)</math> समय और <math>O(|V|^2)</math> सबसे खराब स्थिति में अंतरिक्ष. यह एल्गोरिदम पूरी तरह से पहुंच योग्यता में रुचि नहीं रखता है क्योंकि यह शीर्षों के सभी जोड़े के बीच सबसे छोटी पथ दूरी की भी गणना करता है। नकारात्मक चक्र वाले ग्राफ़ के लिए, सबसे छोटा पथ अपरिभाषित हो सकता है, लेकिन जोड़ियों के बीच पहुंच को अभी भी नोट किया जा सकता है।

=== थोरुप का एल्गोरिदम ===

[[ समतलीय ग्राफ ]]़ निर्देशित ग्राफ़ के लिए, एक बहुत तेज़ विधि उपलब्ध है, जैसा कि 2004 में [[मिकेल थोरुप]] द्वारा वर्णित है।<ref>{{citation
| last = Thorup | first = Mikkel | author-link = Mikkel Thorup
| doi = 10.1145/1039488.1039493
| issue = 6
| journal = [[Journal of the ACM]]
| mr = 2145261
| pages = 993–1024
| title = Compact oracles for reachability and approximate distances in planar digraphs
| volume = 51
| year = 2004| s2cid = 18864647 }}.</ref> यह विधि एक समतलीय ग्राफ़ पर पहुंच योग्यता संबंधी प्रश्नों का उत्तर दे सकती है <math>O(1)</math> खर्च करने के बाद का समय <math>O(n \log{n})</math> डेटा संरचना बनाने के लिए प्रीप्रोसेसिंग समय <math>O(n \log{n})</math> आकार। यह एल्गोरिदम अनुमानित न्यूनतम पथ दूरी के साथ-साथ मार्ग की जानकारी भी प्रदान कर सकता है।

समग्र दृष्टिकोण प्रत्येक शीर्ष के साथ तथाकथित विभाजक पथों का एक अपेक्षाकृत छोटा सेट जोड़ना है जैसे कि शीर्ष से कोई भी पथ <math>v</math> किसी अन्य शीर्ष पर <math>w</math> से जुड़े विभाजकों में से कम से कम एक से गुजरना होगा <math>v</math> या <math>w</math>. पहुंच योग्यता से संबंधित अनुभागों की एक रूपरेखा इस प्रकार है।

एक ग्राफ दिया गया <math>G</math>, एल्गोरिथ्म एक मनमाना शीर्ष से शुरू होकर शीर्षों को परतों में व्यवस्थित करने से शुरू होता है <math>v_0</math>. परतों को पहले पिछले चरण से पहुंच योग्य सभी शीर्षों पर विचार करके वैकल्पिक चरणों में बनाया गया है (केवल से शुरू करके)। <math>v_0</math>) और फिर सभी शीर्ष जो पिछले चरण तक पहुंचते हैं जब तक कि सभी शीर्षों को एक परत को नहीं सौंपा जाता है। परतों के निर्माण से, प्रत्येक शीर्ष अधिकतम दो परतों में दिखाई देता है, और प्रत्येक पथ (ग्राफ़ सिद्धांत)#विभिन्न प्रकार के पथ, या डिपाथ, में <math>G</math> दो आसन्न परतों के भीतर समाहित है <math>L_i</math> और <math>L_{i+1}</math>. होने देना <math>k</math> बनाई गई अंतिम परत बनें, अर्थात, इसके लिए सबसे कम मान <math>k</math> ऐसा है कि <math>\bigcup_{i=0}^{k} L_i = V</math>.

ग्राफ को फिर से डिग्राफ की एक श्रृंखला के रूप में व्यक्त किया जाता है <math>G_0, G_1, \ldots,
G_{k-1}</math> जहां प्रत्येक <math>G_i = r_i \cup L_i \cup L_{i+1}</math> और कहाँ <math>r_i</math> पिछले सभी स्तरों का संकुचन है <math>L_0 \ldots L_{i-1}</math> एक ही शिखर में. क्योंकि प्रत्येक द्विपथ अधिकतम दो लगातार परतों में प्रकट होता है, और क्योंकि
प्रत्येक <math>G_i</math> प्रत्येक द्विपथ में दो लगातार परतों द्वारा निर्मित होता है <math>G</math> कम से कम एक में अपनी संपूर्णता में प्रकट होता है <math>G_i</math> (और लगातार 2 से अधिक ऐसे ग्राफ़ नहीं)

प्रत्येक के लिए <math>G_i</math>, तीन विभाजकों की पहचान की जाती है, जिन्हें हटाए जाने पर, ग्राफ़ को तीन घटकों में तोड़ देते हैं, जिनमें से प्रत्येक में अधिकतम होते हैं <math>1/2</math> मूल के शीर्ष. जैसा <math>G_i</math> विपरीत डिपाथ की दो परतों से बनाया गया है, प्रत्येक विभाजक में 2 डिपाथ तक हो सकते हैं, सभी विभाजकों पर कुल मिलाकर 6 डिपाथ हो सकते हैं। होने देना <math>S</math> दीपपथों का यह सेट हो। इस बात का प्रमाण कि ऐसे विभाजक हमेशा पाए जा सकते हैं, लिप्टन और टार्जन के समतल विभाजक प्रमेय से संबंधित है, और ये विभाजक रैखिक समय में स्थित हो सकते हैं।

प्रत्येक के लिए <math>Q \in S</math>, की निर्देशित प्रकृति <math>Q</math> पथ के आरंभ से अंत तक इसके शीर्षों का प्राकृतिक अनुक्रमण प्रदान करता है। प्रत्येक शीर्ष के लिए <math>v</math> में <math>G_i</math>, हम पहले शीर्ष का पता लगाते हैं <math>Q</math> द्वारा पहुंच योग्य <math>v</math>, और अंतिम शीर्ष <math>Q</math> जो पहुँच जाता है <math>v</math>. यानी हम देख रहे हैं कि कितनी जल्दी <math>Q</math> हम से प्राप्त कर सकते हैं <math>v</math>, और कितनी दूर
हम अंदर रह सकते हैं <math>Q</math> और अभी भी वापस आएँ <math>v</math>. यह जानकारी संग्रहित की जाती है
प्रत्येक <math>v</math>. फिर शीर्षों के किसी भी जोड़े के लिए <math>u</math> और <math>w</math>, <math>u</math> तक पहुँच सकते हैं <math>w</math> के जरिए <math>Q</math> अगर <math>u</math> से जुड़ता है <math>Q</math> से जल्दी <math>w</math> से जुड़ता है <math>Q</math>.

प्रत्येक शीर्ष को रिकर्सन के प्रत्येक चरण के लिए उपरोक्त के रूप में लेबल किया गया है जो बनाता है
<math>G_0 \ldots, G_k</math>. चूँकि इस पुनरावृत्ति में लघुगणकीय गहराई है, कुल
<math>O(\log{n})</math> अतिरिक्त जानकारी प्रति शीर्ष पर संग्रहीत की जाती है। इस बिंदु से, ए
पहुंच योग्यता के लिए लघुगणकीय समय क्वेरी प्रत्येक जोड़ी को देखने जितनी सरल है
एक सामान्य, उपयुक्त के लिए लेबल की <math>Q</math>. फिर मूल पेपर को ट्यून करने का काम करता है
क्वेरी समय नीचे तक <math>O(1)</math>.

इस पद्धति के विश्लेषण को संक्षेप में प्रस्तुत करने में, पहले लेयरिंग पर विचार करें
शीर्षों को विभाजित करने का प्रयास करें ताकि प्रत्येक शीर्ष पर केवल विचार किया जा सके <math>O(1)</math>
बार. एल्गोरिदम का विभाजक चरण ग्राफ़ को घटकों में तोड़ देता है
जो कि अधिकतम हैं <math>1/2</math> मूल ग्राफ़ का आकार, जिसके परिणामस्वरूप a
लघुगणक पुनरावर्तन गहराई. प्रत्यावर्तन के प्रत्येक स्तर पर, केवल रैखिक कार्य
विभाजकों के साथ-साथ उनके बीच संभावित कनेक्शन की पहचान करने की आवश्यकता है
शिखर. समग्र परिणाम है <math>O(n \log n)</math> केवल प्रीप्रोसेसिंग समय के साथ
<math>O(\log{n})</math> प्रत्येक शीर्ष के लिए अतिरिक्त जानकारी संग्रहीत की गई।

=== कामेडा का एल्गोरिदम ===

[[File:Graph suitable for Kameda's method.svg|thumb|right|200px|कामेडा की विधि के लिए एक उपयुक्त डिग्राफ <math>s</math> और <math>t</math> जोड़ा गया.]]

[[File:Kameda's algorithm run.svg|thumb|right|200px|कामेडा के एल्गोरिथ्म के चलने के बाद ऊपर जैसा ही ग्राफ, प्रत्येक शीर्ष के लिए डीएफएस लेबल दिखा रहा है]]1975 में टी. कामेडा के कारण, पूर्व-प्रसंस्करण के लिए और भी तेज़ विधि,<ref>{{citation
| last = Kameda | first = T
| journal = [[Information Processing Letters]]
| volume = 3
| number = 3
| pages = 75–77
| title = On the vector representation of the reachability in planar directed graphs
| year = 1975
| doi=10.1016/0020-0190(75)90019-8}}.</ref>
यदि ग्राफ [[समतलीय ग्राफ]], निर्देशित एसाइक्लिक ग्राफ है, तो इसका उपयोग किया जा सकता है, और निम्नलिखित अतिरिक्त गुण भी प्रदर्शित करता है: सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री और सभी 0-निर्देशित ग्राफ # इंडिग्री और आउटडिग्री शीर्ष ग्राफ सिद्धांत की एक ही शब्दावली पर दिखाई देते हैं #चेहरा (अक्सर बाहरी चेहरा माना जाता है), और उस चेहरे की सीमा को दो भागों में विभाजित करना संभव है जैसे कि सभी 0-डिग्री कोने एक भाग पर दिखाई देते हैं, और सभी
0-आउटडिग्री शीर्ष दूसरे पर दिखाई देते हैं (अर्थात दो प्रकार के शीर्ष वैकल्पिक नहीं होते हैं)।

अगर <math>G</math> इन गुणों को प्रदर्शित करता है, तो हम केवल ग्राफ़ को प्रीप्रोसेस कर सकते हैं
<math>O(n)</math> केवल समय और भंडारण <math>O(\log{n})</math> प्रति शीर्ष अतिरिक्त बिट्स, उत्तर देना
शीर्षों के किसी भी जोड़े के लिए पहुंच योग्यता संबंधी प्रश्न <math>O(1)</math> एक साधारण के साथ समय
तुलना।

प्रीप्रोसेसिंग निम्नलिखित चरणों का पालन करती है। हम एक नया शीर्ष जोड़ते हैं <math>s</math> जिसमें प्रत्येक 0-डिग्री शीर्ष पर एक किनारा है, और एक अन्य नया शीर्ष है <math>t</math> प्रत्येक 0-आउटडिग्री शीर्ष से किनारों के साथ। ध्यान दें कि के गुण <math>G</math> हमें समतलता बनाए रखते हुए ऐसा करने की अनुमति दें, यानी, इन परिवर्धन के बाद भी कोई किनारा क्रॉसिंग नहीं होगा। प्रत्येक शीर्ष के लिए हम ग्राफ़ की समतलता के क्रम में आसन्नताओं (आउट-किनारों) की सूची संग्रहीत करते हैं (उदाहरण के लिए, ग्राफ़ के एम्बेडिंग के संबंध में दक्षिणावर्त)। फिर हम एक काउंटर आरंभ करते हैं <math>i = n + 1</math> और डेप्थ-फर्स्ट ट्रैवर्सल शुरू करें <math>s</math>. इस ट्रैवर्सल के दौरान, प्रत्येक शीर्ष की आसन्न सूची को आवश्यकतानुसार बाएं से दाएं देखा जाता है। जैसे ही ट्रैवर्सल के स्टैक से कोने निकाले जाते हैं, उन्हें मान के साथ लेबल किया जाता है <math>i</math>, और <math>i</math> फिर घटाया जाता है. ध्यान दें कि <math>t</math> हमेशा मूल्य के साथ लेबल किया जाता है <math>n+1</math> और <math>s</math> हमेशा इसके साथ लेबल किया जाता है <math>0</math>. फिर गहराई-पहले ट्रैवर्सल को दोहराया जाता है, लेकिन इस बार प्रत्येक शीर्ष की आसन्न सूची को दाएं से बाएं ओर देखा जाता है।

पूरा हो जाने पर, <math>s</math> और <math>t</math>, और उनके घटना किनारों को हटा दिया जाता है। प्रत्येक
शेष शीर्ष मानों के साथ 2-आयामी लेबल संग्रहीत करता है <math>1</math> को <math>n</math>.
दो शीर्ष दिए गए हैं <math>u</math> और <math>v</math>, और उनके लेबल <math>L(u) = (a_1, a_2)</math> और <math>L(v) =(b_1, b_2)</math>, हम ऐसा कहते हैं <math>L(u) < L(v)</math> अगर और केवल अगर <math>a_1 \leq b_1</math>, <math>a_2 \leq
b_2</math>, और कम से कम एक घटक मौजूद है <math>a_1</math> या <math>a_2</math> जो सख्ती से है
से कम <math>b_1</math> या <math>b_2</math>, क्रमश।

इस विधि का मुख्य परिणाम तो यही बताता है <math>v</math> से पहुंचा जा सकता है <math>u</math> अगर व
केवल <math>L(u) < L(v)</math>जिसकी गणना आसानी से की जा सकती है <math>O(1)</math> समय।

==संबंधित समस्याएँ==

एक संबंधित समस्या कुछ संख्याओं के साथ रीचैबिलिटी प्रश्नों को हल करना है <math>k</math> शीर्ष विफलताओं का. उदाहरण के लिए: शीर्ष कर सकते हैं <math>u</math> अभी भी शीर्ष पर पहुंचें <math>v</math> भले ही शिखर <math>s_1, s_2, ..., s_k</math> विफल हो गए हैं और अब उपयोग नहीं किया जा सकता? एक समान समस्या शीर्ष विफलताओं या दोनों के मिश्रण के बजाय किनारे विफलताओं पर विचार कर सकती है। चौड़ाई-पहली खोज तकनीक ऐसे प्रश्नों पर भी उतनी ही अच्छी तरह काम करती है, लेकिन एक कुशल ओरेकल का निर्माण करना अधिक चुनौतीपूर्ण है।<ref>{{citation
| last1 = Demetrescu | first1 = Camil
| last2 = Thorup | first2 = Mikkel | author2-link = Mikkel Thorup
| last3 = Chowdhury | first3 = Rezaul Alam
| last4 = Ramachandran | first4 = Vijaya
| doi = 10.1137/S0097539705429847
| issue = 5
| journal = [[SIAM Journal on Computing]]
| mr = 2386269
| pages = 1299–1318
| title = Oracles for distances avoiding a failed node or link
| volume = 37
| year = 2008| citeseerx = 10.1.1.329.5435}}.</ref><ref>{{citation
| last1 = Halftermeyer | first1 = Pierre
| title = Connectivity in Networks and Compact Labeling Schemes for Emergency Planning
| location = Universite de Bordeaux
| url = https://tel.archives-ouvertes.fr/tel-01110316/document }}.</ref>
रीचैबिलिटी प्रश्नों से संबंधित एक अन्य समस्या ग्राफ़ के कुछ हिस्से में परिवर्तन होने पर रीचैबिलिटी संबंधों में परिवर्तनों की त्वरित पुनर्गणना करना है। उदाहरण के लिए, यह [[कचरा संग्रहण (कंप्यूटर विज्ञान)]] के लिए एक प्रासंगिक चिंता का विषय है, जिसे चल रहे एप्लिकेशन के प्रदर्शन संबंधी चिंताओं के साथ मेमोरी के पुनर्ग्रहण (ताकि इसे पुनः आवंटित किया जा सके) को संतुलित करने की आवश्यकता है।

== यह भी देखें ==
* [[गैमॉइड]]
* सेंट-कनेक्टिविटी|एसटी-कनेक्टिविटी

==संदर्भ==
{{reflist}}
[[Category: ग्राफ़ कनेक्टिविटी]]

[[Category: Machine Translated Page]]
[[Category:Created On 27/06/2023]]