ग्राफ थ्योरी क्या है, और ग्राफ को इस तरह कैसे परिभाषित किया जाता है?

1736 में, स्विस भौतिक विज्ञानी-गणितज्ञ लियोनहार्ड यूलर (1707-1783) के काम के आधार पर, यह देखा गया कि कोने का एक क्रम परिभाषित करता है एक पथ, हालाँकि, यदि उक्त पथ में किनारों को दोहराए बिना अलग-अलग कोने होते हैं, तो इसे पथ या पथ कहा जाता है यूलेरियन; यदि अतिरिक्त रूप से हम प्रत्येक किनारे को केवल एक बार पार करते हुए प्रारंभिक बिंदु पर पहुंचते हैं, तो हमारे पास एक ऑयलेरियन चक्र (सर्किट) होता है।

उद्धरण (एपीए)

सिकंदर बरज़ा | जुलाई. 2022
भौतिकी में डिग्री

इसके भाग के लिए, हम एक ग्राफ को एक क्रमित युग्म के रूप में परिभाषित करते हैं (जाता है) कहाँ पे वी ग्राफ़ के सभी शीर्षों या नोड्स के (गैर-रिक्त) सेट को निर्दिष्ट करता है, जबकि ए ग्राफ़ के शीर्षों को जोड़ने वाले सभी किनारों या रेखाओं के समुच्चय (यह खाली हो सकता है) को निर्दिष्ट करता है। सेट के तत्व ए एक अनियंत्रित जोड़ी {v, w} के रूप में नामित किया जा सकता है जहां v और w तत्व (नोड्स या शिखर) हैं वी, इस तरह यह तब कहा जाता है कि v और w आसन्न शीर्ष हैं (वे एक किनारे से जुड़े हुए हैं)।

ग्राफ सिद्धांत लोकप्रिय सरलता की समस्या के लिए यूलर द्वारा दिए गए उत्तर से उत्पन्न होता है जो सोचता था कि सात पुलों को कैसे पार किया जाए कोनिग्सबर्ग (उस समय जर्मनी का हिस्सा, और वर्तमान में रूस में कलिनिनग्राद) के समुदाय के दो द्वीपों में शामिल हो गए, उनके बीच और मुख्य भूमि के साथ दो का उपयोग किए बिना कई बार एक ही पुल और शुरुआती बिंदु पर पहुंचना (मुख्य भूमि पर स्थित) जो कुछ भी हो, यह निर्धारित करते हुए कि इस मामले में, अंत में, नहीं सकता है।

कोनिग्सबर्ग के सात पुलों की समस्या

यूलर ने कोनिग्सबर्ग को एक ग्राफ के रूप में प्रतिरूपित किया जहां प्रत्येक बिंदु (शीर्ष या नोड) एक पुल का प्रतिनिधित्व करता है और प्रत्येक रेखा (किनारे) भूमि पर एक पथ:

इस समस्या का समाधान क्या है?

वहाँ एक नहीं है समाधान जो लागू की गई शर्तों को पूरा करता है, क्योंकि, जैसा कि यूलर ने दिखाया है, कोने सम डिग्री के नहीं हैं, अर्थात, रेखाओं की एक सम संख्या प्रत्येक बिंदु को प्रभावित नहीं करती है _[3]. ऐसा प्रतीत नहीं होता है कि हम इस रूप में परिभाषित संरचना के साथ बहुत कुछ कर सकते हैं, हालांकि, जैसा कि अक्सर होता है गणित, कभी-कभी चीजें वैसी नहीं होती जैसी वे दिखती हैं। इस प्रकार, सबसे विपुल, अनुप्रस्थ और अंतःविषय क्षेत्रों में से एक _[4] मानव ज्ञान, ग्राफ सिद्धांत।

यूलेरियन ग्राफ या यूलरियन प्रक्षेपवक्र के साथ?

निम्नलिखित रेखांकन सभी में ऑयलेरियन पथ हैं _[5]. क्या इन सभी में ऑयलेरियन चक्र होते हैं?

आइए तीसरा ग्राफ लें:

आइए शीर्षों को क्रमांकित करें:

तब हम देखते हैं कि अनुक्रम {3,4,6,2,1,3,7,6,5,4,2} द्वारा परिभाषित पथ एक ऑयलेरियन पथ है, क्योंकि यह किनारों को दोहराए बिना पूरे ग्राफ से गुजरता है, लेकिन यह एक यूलेरियन चक्र नहीं है, क्योंकि यह शुरुआती बिंदु तक नहीं पहुंचता है। यदि हम शीर्षों को अलग-अलग क्रमांकित करते तो क्या होता? ज्यादा नहीं, सिवाय इसके कि अब पथ एक अलग उत्तराधिकार द्वारा परिभाषित किया जाएगा। यदि हम अपने प्रारंभिक समाधान में प्रस्तावित पथ से भिन्न पथों का अनुसरण करते तो क्या होता? यह प्रश्न उत्तर देने के लिए थोड़ा अधिक जटिल है, और इसमें एल्गोरिदम शामिल हैं जो सॉफ्टवेयर इंजीनियर आमतौर पर प्रसन्न होते हैं। प्रोग्रामिंग.

यहां जो उजागर हुआ है, उसके अधिक कठोर प्रमाण के लिए हमें निम्नलिखित परिणाम का उल्लेख करना होगा:

"होना जी जुड़ा हुआ ग्राफ _[6]. तो ठीक जी लीजिये सर्किट आयलर, प्रत्येक शीर्ष की घात सम होती है, जबकि if जी एक यूलर पथ है, G के विषम अंश के ठीक दो शीर्ष हैं _[7] (बिल्कुल वे कोने जहां से रास्ता शुरू होता है और खत्म होता है)".

फिर हम यह सत्यापित कर सकते हैं कि, वास्तव में, हम जो ग्राफ लेते हैं, उसमें केवल शीर्ष 3 और 6 की विषम घात होती है (यह हो सकता है, भले ही कोने की संख्या अलग हो), इसलिए कहा गया है कि ग्राफ का पथ है यूलेरियन _[8]. शेष रेखांकन के लिए हम एक समान तरीके से आगे बढ़ सकते हैं और सत्यापित कर सकते हैं कि क्या वास्तव में उनके पास पथ हैं और यूलेरियन चक्र, या दूसरे तरीके से कहें, तो क्या हम पेंसिल उठाए बिना और दोहराए बिना ऐसे ग्राफ खींच सकते हैं रेखाएं? इस प्रश्न का उत्तर अब तक जो समझाया जा चुका है, उससे निकाला जा सकता है, हालाँकि, यह एक अभ्यास है ठीक मोटर कौशल, सरलता और धैर्य के संदर्भ में दिलचस्प, मैं पाठक को 6 या अधिक के रेखांकन खोजने और आकर्षित करने के लिए आमंत्रित करता हूं के साथ शिखर प्रक्षेपवक्र यूलेरियन।

क्या अन्य प्रकार के ग्राफ हैं? क्या ग्राफ सिद्धांत में 'वास्तविक' दुनिया में अनुप्रयोग हैं?

ये ग्राफ़ जिनकी हमने बहुत संक्षेप में समीक्षा की है, वे कई प्रकार के ग्राफ़ में से एक हैं जो हमें ग्राफ़ सिद्धांत में मिलते हैं। हम पेड़ जैसे ग्राफ भी पा सकते हैं, जो सेट में बहुत प्रतिनिधि हैं जहां उनके तत्वों को पदानुक्रम में और गणना गणना में वर्गीकृत किया जा सकता है और संभावना_[9], डिग्राफ, हैमिल्टनियन ग्राफ _[10], आदि।

साइको में ग्राफिक मॉडल और नेटवर्क की छवि। रुइज़, एना मारिया द्वारा।

ये पहेली, अगर हम उन्हें कॉल करना चाहते हैं, तो आज की दुनिया में विविध परिस्थितियों में बहुत अधिक प्रयोज्यता है: जीवविज्ञान मोलेकुलर _[11], कम्प्यूटिंग_[12], दूरसंचार _[13] और नेटवर्क विश्लेषण _[14]. यह पूछने लायक है: क्या यह कम से कम उत्सुक नहीं है कि लगभग एक समस्या है तुच्छ क्या गणित के सबसे दिलचस्प और विशिष्ट परिणामों में से एक होगा? शायद, इसके लिए मानवता के सबसे शानदार दिमागों में से एक का योगदान आवश्यक था।