सड़क और नेटवर्क चुनने के लिए एल्गोरिदम। स्टेनर नेटवर्क। यैंडेक्स में व्लादिमीर प्रोटैसोव द्वारा व्याख्यान

आज हम बड़े नेटवर्क के सिद्धांत के पहले कार्यों में से एक के बारे में बात करेंगे, जिसे सरलतम बुनियादी स्तर पर पूरी तरह से हल किया जा सकता है, लेकिन जो इससे कम दिलचस्प नहीं है। यह सड़कों की सबसे छोटी प्रणाली या स्टेनर समस्या है।

यह पहली बार दिखाई दिया जब बड़े नेटवर्क के लिए अभी भी कोई व्यावहारिक आवश्यकता नहीं थी: 20 वीं शताब्दी के तीसवें दशक में। वास्तव में, स्टीनर ने 19 वीं शताब्दी में भी इसका अध्ययन करना शुरू किया था। यह एक विशुद्ध रूप से ज्यामितीय समस्या थी, जिसके व्यावहारिक अनुप्रयोग कुछ दशकों बाद ही ज्ञात हुए।

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



कार्य स्वयं बहुत सरल रूप से तैयार किया गया है। विमान पर कई बिंदु हैं जिन्हें छोटी से छोटी कुल लंबाई की सड़कों की एक प्रणाली द्वारा जोड़ा जाना चाहिए ताकि इन सड़कों को किसी भी बिंदु से किसी अन्य तक पहुंचाया जा सके। अंकों की संख्या परिमित है।

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




यदि हम श्रृंखलाओं में गाँवों को जोड़ते हैं, तो हम जिस वर्ग के बारे में सोच सकते हैं, उसके तीन किनारों से कम नहीं है। इस कनेक्शन के साथ, हमारे पास ठीक 12 किलोमीटर होगा। इसे तिरछे से जोड़ा जा सकता है, लेकिन यह केवल खराब हो जाएगा, क्योंकि विकर्ण पक्ष की तुलना में लंबा है।



यदि आप एक अतिरिक्त चोटी रखते हैं, तो इससे आप किसी भी चार गांवों में जा सकते हैं। अगर हम तिरछे विपरीत चोटियों को जोड़ने वाली सड़कों को लेते हैं, तो त्रिकोण की असमानता से, उनकी लंबाई का योग विकर्ण की लंबाई से अधिक होगा। अन्य दो के लिए, लंबाई का योग भी विकर्ण की लंबाई से अधिक है। तदनुसार, हमारे पास सभी सड़कों का योग ∙2 √ 4 =2 = 8√2≈11.31 होगा। कुछ इस तरह, ग्यारहवें ग्रेडर ने तर्क दिया, जिन्होंने सड़कों की ऐसी प्रणाली के अस्तित्व की असंभवता को साबित करने की कोशिश की।



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



इस कार्य को अंत में करने के लिए, हम पहले समाधान में एक त्रुटि पाते हैं, जहां हमें लगता है कि यह साबित हो गया है कि 8√2 से कम कुछ भी नहीं हो सकता है। बस यह कि इस निर्णय ने उसी साइट के पुन: उपयोग की संभावना को ध्यान में नहीं रखा।

तीन अंक

त्रिभुज के लिए स्टाइनर नेटवर्क 17 वीं शताब्दी में जैकब स्टीनर के खुद से 200 साल पहले जाना जाता था। यह तथाकथित Fermat-Toricelli-Steiner बिंदु है।

हम एक सहायक कथन को साबित करके शुरू करते हैं, जिसे कभी-कभी पोम्पी प्रमेय कहा जाता है। यदि हम एक समबाहु त्रिभुज और समतल पर किसी अन्य बिंदु पर विमान पर चढ़ते हैं, तो दो खड़ग A और B की दूरी का योग हमेशा तीसरे शीर्ष C: MA + MB। MC की दूरी से अधिक या बराबर होता है। इसके अलावा, MA + MB = MC केवल यदि बिंदु M, खण्डित वृत्त के चाप पर स्थित है जिसमें बिंदु C नहीं है। एएमबी कोण 120 ° होना चाहिए। अन्यथा, एमए + एमबी> एमसी।



बेशक, जब एक समबाहु त्रिभुज की बात आती है, तो कुछ शीर्षों के सापेक्ष 60 ° का एक चक्कर अक्सर ऐसी समस्याओं में हमारी मदद करता है। हम यह करेंगे: शीर्ष पर स्थित एएमडी के सापेक्ष हैच त्रिकोण को चालू करें। पॉइंट B पॉइंट C पर जाएगा, और पॉइंट M से पॉइंट M 'पर जाएगा। परिणामस्वरूप, हमें वह AM = AM '= MM', और M'C = MB मिलता है। अब हम MM'C त्रिकोण पर सामान्य त्रिभुज असमानता को लागू कर सकते हैं। इसमें दो पक्षों M'M और M'C का योग MC से बड़ा होता है। तदनुसार, एमए + एमबी MB एम.सी. और समानता कब प्राप्त की जाती है? समानता तब प्राप्त होती है जब बिंदु M 'लाइन MC को हिट करता है, अर्थात। जब एएमसी कोण 120 ° है।



अब हम सीधे तीन बिंदुओं के लिए स्टाइनर समस्या से गुजरते हैं। इसे निम्नानुसार तैयार किया जाता है। त्रिकोण सेट है। आपको विमान पर एक बिंदु खोजने की आवश्यकता है, जिसमें से इस त्रिभुज के कोने तक की दूरी सबसे छोटी है। टीए + टीबी + टीसी → मिनट।



ये क्या बात है? हम त्रिभुज के कुछ उल्लेखनीय बिंदुओं को जानते हैं: उत्कीर्ण और परिधि वाले हलकों के केंद्र, मध्य बिंदुओं के मध्य बिंदु, ऊंचाइयों के प्रतिच्छेदन बिंदु। दुर्भाग्य से, उनमें से कोई भी एक बिंदु की भूमिका के लिए उपयुक्त नहीं है जिसमें सबसे छोटी दूरी है। यह बिंदु बहुत ही खास है, और इसे अलग तरह से कहा जाता है: टॉरिकेली पॉइंट, फ़र्मेट पॉइंट, स्टीनर पॉइंट। यह एक ऐसे बिंदु का प्रतिनिधित्व करता है जहां से त्रिभुज के सभी तीन कोने एक ही कोण पर दिखाई देते हैं - 120 °। आइए देखें कि ऐसा क्यों है। पहली बार, किसी त्रिभुज के सभी कोणों के लिए सबसे छोटी दूरी के साथ एक बिंदु की समस्या का हल पहली बार 17 वीं शताब्दी के मध्य में इतालवी भौतिक विज्ञानी और गणितज्ञ विन्सेन्ज़ो विवियन की पुस्तक में प्रलेखित किया गया था। हालांकि, यह ज्ञात है कि इस समस्या का समाधान पहले भी विवियन के एक दोस्त, इवेंजेलिस्ता टोरिकेली द्वारा प्राप्त किया गया था - ये दोनों गैलीलियो के छात्र थे। पुस्तक में दिया गया समाधान ज्यामितीय नहीं था, यह भौतिक सिद्धांतों पर आधारित था। टोरीसेली से पहले, पियरे फरमेट इस समस्या को जानते थे, और शायद यह हल हो गया था: वे पत्राचार में थे, और टोरिसेली ने इस कार्य के बारे में फ़र्मैट से ठीक-ठीक पता लगाया, लेकिन क्या नकारात्मक का अपना समाधान नहीं है।

इस समस्या का पहला ज्यामितीय समाधान केवल 200 वर्षों के बाद दिखाई दिया, और इसके लेखक जैकब स्टेनर थे। वह ज्यामितीय तरीकों से विशेष रूप से ज्यामितीय समस्याओं को हल करने वाले पहले सिंथेटिक ज्यामिति में से एक था। स्टीनर का निर्णय ऊपर माना गया पोम्पे प्रमेय पर आधारित था।

क्या कोई ऐसा बिंदु है जहां से त्रिभुज के सभी कोण 120 ° के कोण पर दिखाई देते हैं? यह हमेशा मौजूद नहीं होता है, लेकिन केवल अगर त्रिकोण के सभी कोण सख्ती से 120 डिग्री से कम हैं।

यदि त्रिभुज के सभी कोण> 120 ° हैं, तो एक एकल Toricelli बिंदु है। हम बीसी के सापेक्ष बाहरी दिशा में एक समभुज त्रिभुज का निर्माण करते हैं। हम एक वृत्त का निर्माण करते हैं जो बिंदु B, A 'और C से होकर गुजरेगा। यदि इस मामले में Toricelli करंट मौजूद है, तो उसे इस वृत्त पर स्थित होना चाहिए, बिंदु B और C. के बीच चाप पर, उत्कीर्ण चतुष्कोण में विपरीत कोणों का योग 180 ° होता है। क्रमशः त्रिभुज BA'C समबाहु है, इसमें सभी कोण 60 ° हैं। इसलिए, यदि हम बिंदु B और C के बीच चाप पर एक बिंदु रखते हैं, और फिर चतुर्भुज को समाप्त करते हैं, तो शीर्ष A 'के विपरीत कोण 120 ° होगा।



लेकिन वास्तव में वह बिंदु कहां है ताकि 120 डिग्री के कोण पर सभी कोने दिखाई दे सकें। एसी पक्ष के सापेक्ष हमें इस बार एक और समबाहु त्रिभुज बनाने की जरूरत है। और बस इसे एक सर्कल में दर्ज करें। दो हलकों के चौराहे बिंदु Toricelli के बिंदु होंगे। हम पहले से ही निर्धारित कर चुके हैं कि बीटीसी कोण 120 ° है, एटीसी कोण उसी तरह से प्राप्त होता है और 120 ° के बराबर भी होता है। कुल में, सभी तीन कोणों को 360 ° देना चाहिए, जिसका अर्थ है कि BTA कोण भी 120 ° के बराबर है। इस प्रकार, हमने न केवल टोरिसेली बिंदु के अस्तित्व को साबित किया, बल्कि यह भी तथ्य यह है कि यह केवल एक ही हो सकता है, क्योंकि हमारे द्वारा निर्मित चाप एक से अधिक चौराहे बिंदु नहीं हो सकते हैं। सैद्धांतिक रूप से, वृत्त त्रिभुज ABC के बाहर प्रतिच्छेद कर सकते हैं, लेकिन ऐसा तभी हो सकता है, जब इसके कम से कम एक कोण 120 ° से अधिक हो।



इसलिए, हमने सीखा कि टोरिसेली बिंदु का स्थान कैसे खोजा जाए, लेकिन यह नहीं बताया कि त्रिकोण के कोने तक दूरी के न्यूनतम योग पर स्टेनर समस्या को हल करने के लिए इसका उपयोग क्यों किया जा सकता है। फिर से, त्रिभुज ABC को लें, जहाँ सभी कोण 120 ° से कम हों और पार्श्व AC के संबंध में एक बाह्य समबाहु त्रिभुज का निर्माण करें। चलो इसे AB'C कहते हैं। अगला, विमान पर एक मनमाना बिंदु M लें और इसे त्रिभुज ABC के तीनों कोने से जोड़ दें। पोम्पी प्रमेय द्वारा, एमए + एमसी। एमबी ’। इसलिए, एमए + एमबी + एमसी 'एमबी' + एमबी, और एमबी + एमबी '। बीबी'। चूंकि MB + MB 'BB से कम नहीं हो सकता', बिंदु M के पास त्रिभुज ABC की दूरी के सबसे छोटे योग केवल MB + MB '= BB' होंगे। ऐसी समानता किन परिस्थितियों में सही होगी? पोम्पी के प्रमेय के अनुसार, इसके लिए सबसे पहले यह आवश्यक है कि MA + MC MB के बराबर हो, अर्थात। कोण AMC 120 ° के बराबर होना चाहिए, और दूसरी बात, BM और MB के सेगमेंट का योग BB 'के बराबर होना चाहिए, अर्थात। बिंदु M को सेगमेंट BB पर लेटना चाहिए '। तदनुसार, एएमबी और बीएमसी के कोण भी 120 ° के बराबर होंगे। यह सब इस प्रकार से है कि एमबी + एमबी '= बीबी' केवल अगर बिंदु एम टॉरिकेली बिंदु के साथ मेल खाता है। यह तीन बिंदुओं के लिए स्टाइनर समस्या का समाधान है।



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

यह पता चला है कि Fermat-Toricelli-Steiner बिंदु वह सब है जो सबसे छोटी सड़क प्रणालियों के निर्माण के लिए आवश्यक है। मुख्य कार्य निम्नानुसार तैयार किया गया है। समतल पर बिंदुओं का एक परिमित सेट (k fin 2) दिया गया है। उन्हें सड़कों की सबसे छोटी प्रणाली से जोड़ना आवश्यक है। स्टाइनर ने स्वयं k = 3 के लिए इस समस्या को हल किया और k = 4. के लिए कुछ उदाहरण दिए। k solved 2 के लिए, स्टाइनर ने भी कोई समस्या नहीं बताई। यह समस्या दो चेक गणितज्ञ केसलर और जेर्निक द्वारा जैकब स्टीनर की मृत्यु के 70 साल बाद पहली बार सेट की गई थी। 1934 में, इस समस्या को एक चेक गणितीय पत्रिका में प्रकाशित किया गया था, लेकिन पहले कुछ वर्षों तक इसमें कोई दिलचस्पी नहीं थी। हालांकि, 1941 में, दो अमेरिकी गणितज्ञ उस समय पहले से ही जानते थे, हर्वित्ज और कौरेंट ने इसे अपनी पुस्तक में केसलर और यार्निक के संदर्भ में रखा था, जिसके बाद यह कार्य बहुत प्रसिद्ध हो गया।

व्याख्यान को अंत तक देखने के बाद, आप सीखेंगे कि विमान और अंतरिक्ष में सामान्य शब्दों में स्टीनर समस्या का समाधान कैसे किया जाता है।