रॉबिन्स का प्रमेय
ग्राफ़ सिद्धांत में, रॉबिंस प्रमेय का नाम किसके नाम पर रखा गया है? Herbert Robbins (1939), बताता है कि जिन ग्राफ़ में मजबूत अभिविन्यास होता है वे बिल्कुल के-एज-कनेक्टेड ग्राफ़|2-एज-कनेक्टेड ग्राफ़ होते हैं। अर्थात्, अप्रत्यक्ष ग्राफ़ के प्रत्येक किनारे के लिए एक दिशा चुनना संभव है G, इसे एक निर्देशित ग्राफ़ में बदलना जिसमें प्रत्येक शीर्ष से प्रत्येक दूसरे शीर्ष तक का पथ है, यदि और केवल यदि G जुड़ा हुआ ग्राफ़ है और इसमें कोई ब्रिज (ग्राफ़ सिद्धांत) नहीं है।
ओरिएंटेबल ग्राफ़
मजबूत अभिविन्यास वाले ग्राफ़ के रॉबिन्स के लक्षण वर्णन को कान के अपघटन का उपयोग करके सिद्ध किया जा सकता है, जो इस कार्य के लिए रॉबिन्स द्वारा पेश किया गया एक उपकरण है।
यदि ग्राफ़ में एक पुल है, तो यह दृढ़ता से उन्मुख नहीं हो सकता है, इससे कोई फर्क नहीं पड़ता कि पुल के लिए कौन सा अभिविन्यास चुना गया है, पुल के दो समापन बिंदुओं में से एक से दूसरे तक कोई रास्ता नहीं होगा।
दूसरी दिशा में, यह दिखाना आवश्यक है कि प्रत्येक कनेक्टेड ब्रिजलेस ग्राफ को दृढ़ता से उन्मुख किया जा सकता है। जैसा कि रॉबिंस ने साबित किया है, ऐसे प्रत्येक ग्राफ़ में उप-ग्राफ के अनुक्रम में एक विभाजन होता है जिसे कान कहा जाता है, जिसमें अनुक्रम में पहला उप-ग्राफ एक चक्र होता है और प्रत्येक बाद का उप-ग्राफ एक पथ होता है, जिसमें दो पथ समापन बिंदु होते हैं जो अनुक्रम में पहले के कानों से संबंधित होते हैं। . (दो पथ समापन बिंदु बराबर हो सकते हैं, जिस स्थिति में सबग्राफ एक चक्र है।) प्रत्येक कान के भीतर किनारों को उन्मुख करना ताकि यह एक निर्देशित चक्र या एक निर्देशित पथ बना सके जिससे समग्र ग्राफ का दृढ़ता से जुड़ा हुआ अभिविन्यास हो सके।[1]
संबंधित परिणाम
रॉबिन्स प्रमेय का मिश्रित ग्राफ़ तक विस्तार Boesch & Tindell (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.
