रॉबिन्स का प्रमेय: Difference between revisions
No edit summary |
No edit summary |
||
| Line 24: | Line 24: | ||
किसी दिए गए ब्रिजलेस अप्रत्यक्ष ग्राफ का एक शक्तिशाली अभिविन्यास ग्राफ की [[गहराई-पहली खोज]] करके, पेड़ की जड़ से दूर गहराई-पहली खोज पेड़ में सभी किनारों को उन्मुख करके, और शेष सभी किनारों को उन्मुख करके [[रैखिक समय]] में पाया जा सकता है (जो गहराई-प्रथम खोज वृक्ष में एक पूर्वज और एक वंशज को आवश्यक रूप से जोड़ना चाहिए) वंशज से पूर्वज तक।<ref>{{harvtxt|Vishkin|1985}} credits this observation to {{harvtxt|Atallah|1984}}, and {{harvtxt|Balakrishnan|1996}} credits it to {{harvtxt|Roberts|1978}}. But as {{harvtxt|Clark|Holton|1991}} point out, the same algorithm is already included (with the assumption of [[k-vertex-connected graph|2-vertex-connectivity]] rather than 2-edge-connectivity) in the seminal earlier work of {{harvtxt|Hopcroft|Tarjan|1973}} on depth-first search.</ref> चूँकि यह एल्गोरिदम [[समानांतर कंप्यूटर]] के लिए उपयुक्त नहीं है, किंतु उन पर गहराई से पहली खोज करने की कठिनाई के कारण, वैकल्पिक एल्गोरिदम उपलब्ध हैं जो समानांतर मॉडल में समस्या को कुशलता से हल करते हैं।<ref>{{harvtxt|Vishkin|1985}}.</ref> समानांतर एल्गोरिदम को मिश्रित ग्राफ़ के दृढ़ता से जुड़े झुकावों को खोजने के लिए भी जाना जाता है।<ref>{{harvtxt|Soroker|1988}}.</ref> | किसी दिए गए ब्रिजलेस अप्रत्यक्ष ग्राफ का एक शक्तिशाली अभिविन्यास ग्राफ की [[गहराई-पहली खोज]] करके, पेड़ की जड़ से दूर गहराई-पहली खोज पेड़ में सभी किनारों को उन्मुख करके, और शेष सभी किनारों को उन्मुख करके [[रैखिक समय]] में पाया जा सकता है (जो गहराई-प्रथम खोज वृक्ष में एक पूर्वज और एक वंशज को आवश्यक रूप से जोड़ना चाहिए) वंशज से पूर्वज तक।<ref>{{harvtxt|Vishkin|1985}} credits this observation to {{harvtxt|Atallah|1984}}, and {{harvtxt|Balakrishnan|1996}} credits it to {{harvtxt|Roberts|1978}}. But as {{harvtxt|Clark|Holton|1991}} point out, the same algorithm is already included (with the assumption of [[k-vertex-connected graph|2-vertex-connectivity]] rather than 2-edge-connectivity) in the seminal earlier work of {{harvtxt|Hopcroft|Tarjan|1973}} on depth-first search.</ref> चूँकि यह एल्गोरिदम [[समानांतर कंप्यूटर]] के लिए उपयुक्त नहीं है, किंतु उन पर गहराई से पहली खोज करने की कठिनाई के कारण, वैकल्पिक एल्गोरिदम उपलब्ध हैं जो समानांतर मॉडल में समस्या को कुशलता से हल करते हैं।<ref>{{harvtxt|Vishkin|1985}}.</ref> समानांतर एल्गोरिदम को मिश्रित ग्राफ़ के दृढ़ता से जुड़े झुकावों को खोजने के लिए भी जाना जाता है।<ref>{{harvtxt|Soroker|1988}}.</ref> | ||
==अनुप्रयोग== | ==अनुप्रयोग== | ||
रॉबिन्स ने मूल रूप से शहरों में वन-वे सड़कों के डिजाइन के लिए एक एप्लिकेशन द्वारा अपने काम को प्रेरित किया जाता है। [[ग्रिड ब्रेसिंग]] के सिद्धांत में, [[संरचनात्मक कठोरता]] में एक और अनुप्रयोग उत्पन्न होता है। यह सिद्धांत लचीले जोड़ों पर जुड़ी कठोर छड़ों से निर्मित एक वर्गाकार ग्रिड बनाने की समस्या से संबंधित है, जो ग्रिड के विकर्णों पर [[क्रॉस ब्रेसिंग]] के रूप में अधिक छड़ें या तार जोड़कर कठोर होता है। यदि संबंधित अप्रत्यक्ष ग्राफ जुड़ा हुआ है तो अतिरिक्त छड़ों का एक सेट ग्रिड को कठोर बनाता है, और यदि इसके अतिरिक्त यह ब्रिजलेस है तो यह दोगुना ब्रेस्ड (यदि कोई किनारा हटा दिया जाता है तो कठोर रहता है) | रॉबिन्स ने मूल रूप से शहरों में वन-वे सड़कों के डिजाइन के लिए एक एप्लिकेशन द्वारा अपने काम को प्रेरित किया जाता है। [[ग्रिड ब्रेसिंग]] के सिद्धांत में, [[संरचनात्मक कठोरता]] में एक और अनुप्रयोग उत्पन्न होता है। यह सिद्धांत लचीले जोड़ों पर जुड़ी कठोर छड़ों से निर्मित एक वर्गाकार ग्रिड बनाने की समस्या से संबंधित है, जो ग्रिड के विकर्णों पर [[क्रॉस ब्रेसिंग]] के रूप में अधिक छड़ें या तार जोड़कर कठोर होता है। यदि संबंधित अप्रत्यक्ष ग्राफ जुड़ा हुआ है तो अतिरिक्त छड़ों का एक सेट ग्रिड को कठोर बनाता है, और यदि इसके अतिरिक्त यह ब्रिजलेस है तो यह दोगुना ब्रेस्ड (यदि कोई किनारा हटा दिया जाता है तो कठोर रहता है) होता है। अनुरूप रूप से, जोड़े गए तारों का एक सेट (जो उन बिंदुओं के बीच की दूरी को कम करने के लिए झुक सकता है जो वे जुड़ते हैं, किंतु विस्तार नहीं कर सकते) यदि संबंधित निर्देशित ग्राफ दृढ़ता से जुड़ा हुआ है तो ग्रिड को कठोर बनाता है।{{sfnp|Baglivo|Graver|1983}} इसलिए, इस अनुप्रयोग के लिए रॉबिन्स के प्रमेय की पुनर्व्याख्या करते हुए, दोगुनी ब्रेस्ड संरचनाएं वास्तव में वे संरचनाएं हैं जिनकी छड़ें कठोर रहते हुए तारों द्वारा प्रतिस्थापित की जा सकती हैं। | ||
==टिप्पणियाँ | ==टिप्पणियाँ == | ||
{{reflist|colwidth=30em}} | {{reflist|colwidth=30em}} | ||
Revision as of 09:54, 20 July 2023
ग्राफ़ सिद्धांत में रॉबिन्स प्रमेय का नाम हर्बर्ट रॉबिंस (1939) के नाम पर रखा गया है, जिसमें कहा गया है कि जिन ग्राफ़ में शक्तिशाली अभिविन्यास होते हैं वे वास्तव में 2-किनारे से जुड़े ग्राफ़ होते हैं। अर्थात्, अप्रत्यक्ष ग्राफ़ G के प्रत्येक किनारे के लिए एक दिशा चुनना संभव है, इसे एक निर्देशित ग्राफ़ में बदलना, जिसमें प्रत्येक शीर्ष से प्रत्येक दूसरे शीर्ष तक का पथ हो, यदि और केवल यदि G जुड़ा हुआ है और इसमें कोई पुल नहीं है।
ओरिएंटेबल ग्राफ़
शक्तिशाली अभिविन्यास वाले ग्राफ़ के रॉबिन्स के लक्षण वर्णन को इयर के अपघटन का उपयोग करके सिद्ध किया जा सकता है, जो इस कार्य के लिए रॉबिन्स द्वारा प्रस्तुत किया गया एक उपकरण है।
यदि ग्राफ़ में एक पुल है, तो यह दृढ़ता से उन्मुख नहीं हो सकता है, इससे कोई अंतर नहीं पड़ता कि पुल के लिए कौन सा अभिविन्यास चुना गया है, पुल के दो समापन बिंदुओं में से एक से दूसरे तक कोई रास्ता नहीं होगा।
दूसरी दिशा में, यह दिखाना आवश्यक है कि प्रत्येक कनेक्टेड ब्रिजलेस ग्राफ को दृढ़ता से उन्मुख किया जा सकता है। जैसा कि रॉबिंस ने सिद्ध किया है, ऐसे प्रत्येक ग्राफ़ में उप-ग्राफ के अनुक्रम में एक विभाजन होता है जिसे इयर कहा जाता है, जिसमें अनुक्रम में पहला उप-ग्राफ एक चक्र होता है और प्रत्येक बाद का उप-ग्राफ एक पथ होता है, जिसमें दो पथ समापन बिंदु होते हैं जो अनुक्रम में पहले के इयरों से संबंधित होते हैं। . (दो पथ समापन बिंदु समान हो सकते हैं, जिस स्थिति में सबग्राफ एक चक्र है।) प्रत्येक इयर के अंदर किनारों को उन्मुख करना जिससे यह एक निर्देशित चक्र या एक निर्देशित पथ बना सके जिससे समग्र ग्राफ का दृढ़ता से जुड़ा हुआ अभिविन्यास हो सकता है ।[1]
संबंधित परिणाम
बोएश और टिंडेल (1980) द्वारा मिश्रित ग्राफ़ के लिए रॉबिन्स प्रमेय के विस्तार से पता चलता है कि, यदि G एक ग्राफ़ है जिसमें कुछ किनारों को निर्देशित किया जा सकता है और अन्य को अप्रत्यक्ष किया जा सकता है, और G में प्रत्येक शीर्ष से प्रत्येक दूसरे शीर्ष तक किनारे के झुकाव का सम्मान करने वाला एक पथ होता है, तो G
के किसी भी अप्रत्यक्ष किनारे को जो पुल नहीं है, उसे G की कनेक्टिविटी को बदले बिना निर्देशित किया जा सकता है। विशेष रूप से, एक ब्रिजलेस अप्रत्यक्ष ग्राफ को एक लुब्ध एल्गोरिथ्म द्वारा दृढ़ता से जुड़े हुए निर्देशित ग्राफ में बनाया जा सकता है जो किनारों को निर्देशित करता है शीर्षों के प्रत्येक जोड़े के बीच पथों के अस्तित्व को संरक्षित करते हुए एक-एक करके; ऐसे एल्गोरिदम के लिए ऐसी स्थिति में फंसना असंभव है जिसमें कोई अतिरिक्त अभिविन्यास निर्णय नहीं लिया जा सकता है।
एल्गोरिदम और जटिलता
किसी दिए गए ब्रिजलेस अप्रत्यक्ष ग्राफ का एक शक्तिशाली अभिविन्यास ग्राफ की गहराई-पहली खोज करके, पेड़ की जड़ से दूर गहराई-पहली खोज पेड़ में सभी किनारों को उन्मुख करके, और शेष सभी किनारों को उन्मुख करके रैखिक समय में पाया जा सकता है (जो गहराई-प्रथम खोज वृक्ष में एक पूर्वज और एक वंशज को आवश्यक रूप से जोड़ना चाहिए) वंशज से पूर्वज तक।[2] चूँकि यह एल्गोरिदम समानांतर कंप्यूटर के लिए उपयुक्त नहीं है, किंतु उन पर गहराई से पहली खोज करने की कठिनाई के कारण, वैकल्पिक एल्गोरिदम उपलब्ध हैं जो समानांतर मॉडल में समस्या को कुशलता से हल करते हैं।[3] समानांतर एल्गोरिदम को मिश्रित ग्राफ़ के दृढ़ता से जुड़े झुकावों को खोजने के लिए भी जाना जाता है।[4]
अनुप्रयोग
रॉबिन्स ने मूल रूप से शहरों में वन-वे सड़कों के डिजाइन के लिए एक एप्लिकेशन द्वारा अपने काम को प्रेरित किया जाता है। ग्रिड ब्रेसिंग के सिद्धांत में, संरचनात्मक कठोरता में एक और अनुप्रयोग उत्पन्न होता है। यह सिद्धांत लचीले जोड़ों पर जुड़ी कठोर छड़ों से निर्मित एक वर्गाकार ग्रिड बनाने की समस्या से संबंधित है, जो ग्रिड के विकर्णों पर क्रॉस ब्रेसिंग के रूप में अधिक छड़ें या तार जोड़कर कठोर होता है। यदि संबंधित अप्रत्यक्ष ग्राफ जुड़ा हुआ है तो अतिरिक्त छड़ों का एक सेट ग्रिड को कठोर बनाता है, और यदि इसके अतिरिक्त यह ब्रिजलेस है तो यह दोगुना ब्रेस्ड (यदि कोई किनारा हटा दिया जाता है तो कठोर रहता है) होता है। अनुरूप रूप से, जोड़े गए तारों का एक सेट (जो उन बिंदुओं के बीच की दूरी को कम करने के लिए झुक सकता है जो वे जुड़ते हैं, किंतु विस्तार नहीं कर सकते) यदि संबंधित निर्देशित ग्राफ दृढ़ता से जुड़ा हुआ है तो ग्रिड को कठोर बनाता है।[5] इसलिए, इस अनुप्रयोग के लिए रॉबिन्स के प्रमेय की पुनर्व्याख्या करते हुए, दोगुनी ब्रेस्ड संरचनाएं वास्तव में वे संरचनाएं हैं जिनकी छड़ें कठोर रहते हुए तारों द्वारा प्रतिस्थापित की जा सकती हैं।
टिप्पणियाँ
- ↑ Gross & Yellen (2006).
- ↑ Vishkin (1985) credits this observation to Atallah (1984), and Balakrishnan (1996) credits it to Roberts (1978). But as Clark & Holton (1991) point out, the same algorithm is already included (with the assumption of 2-vertex-connectivity rather than 2-edge-connectivity) in the seminal earlier work of Hopcroft & Tarjan (1973) on depth-first search.
- ↑ Vishkin (1985).
- ↑ Soroker (1988).
- ↑ Baglivo & Graver (1983).
संदर्भ
- Atallah, Mikhail J. (1984), "Parallel strong orientation of an undirected graph", Information Processing Letters, 18 (1): 37–39, doi:10.1016/0020-0190(84)90072-3, MR 0742079.
- Baglivo, Jenny A.; Graver, Jack E. (1983), "3.10 Bracing structures", Incidence and Symmetry in Design and Architecture, Cambridge Urban and Architectural Studies, Cambridge, UK: Cambridge University Press, pp. 76–87, ISBN 9780521297844
- Balakrishnan, V. K. (1996), "4.6 Strong Orientation of Graphs", Introductory Discrete Mathematics, Mineola, NY: Dover Publications Inc., p. 135, ISBN 978-0-486-69115-2, MR 1402469.
- Boesch, Frank; Tindell, Ralph (1980), "Robbins's theorem for mixed multigraphs", The American Mathematical Monthly, 87 (9): 716–719, doi:10.2307/2321858, JSTOR 2321858, MR 0602828.
- Clark, John; Holton, Derek Allan (1991), "7.4 Traffic Flow", A first look at graph theory, Teaneck, NJ: World Scientific Publishing Co. Inc., pp. 254–260, ISBN 978-981-02-0489-1, MR 1119781.
- Gross, Jonathan L.; Yellen, Jay (2006), "Characterization of strongly orientable graphs", Graph Theory and its Applications, Discrete Mathematics and its Applications (2nd ed.), Boca Raton, FL: Chapman & Hall/CRC, pp. 498–499, ISBN 978-1-58488-505-4, MR 2181153.
- Hopcroft, John; Tarjan, Robert (1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM, 16 (6): 372–378, doi:10.1145/362248.362272, S2CID 14772567.
- Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, JSTOR 2303897.
- Roberts, Fred S. (1978), "Chapter 2. The One-Way Street Problem", Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), pp. 7–14, ISBN 9780898710267, MR 0508050.
- Soroker, Danny (1988), "Fast parallel strong orientation of mixed graphs and related augmentation problems", Journal of Algorithms, 9 (2): 205–223, doi:10.1016/0196-6774(88)90038-7, MR 0936106.
- Vishkin, Uzi (1985), "On efficient parallel strong orientation", Information Processing Letters, 20 (5): 235–240, doi:10.1016/0020-0190(85)90025-0, MR 0801988.
