ग्राफ सिद्धांत
ग्राफ सिद्धांत ग्राफ़ों का अध्ययन करता है - किनारों से जुड़े शीर्षों की संरचनाएँ - युग्मित संबंधों और नेटवर्कों के गणितीय मॉडल के रूप में।
Definition
ग्राफ़ों का गणितीय अध्ययन, जो शीर्षों के समुच्चय होते हैं, साथ में किनारों का एक समुच्चय होता है जो प्रत्येक शीर्षों के एक युग्म को जोड़ता है, और उन कनेक्शनों की संरचना के तहत अपरिवर्तनीय गुणों का अध्ययन।
Scope
यह क्षेत्र ग्राफ़ों की संरचना, गुणधर्मों और मापदंडों को शामिल करता है: संयोजकता, पथ और चक्र, वृक्ष, समतलता, रंगाई, मिलान और प्रवाह, साथ ही इस बारे में चरम और संभाव्य प्रश्न कि ग्राफ़ गुणधर्म एक-दूसरे को कैसे बाधित करते हैं। यह असतत गणित के लिए केंद्रीय है और कंप्यूटर विज्ञान, संचालन अनुसंधान और प्राकृतिक व सामाजिक विज्ञानों में नेटवर्कों के लिए भाषा प्रदान करता है।
Sub-topics
Core questions
- किसी ग्राफ़ की संयोजकता, डिग्री अनुक्रम, या चक्र संरचना से कौन से संरचनात्मक गुणधर्म निकलते हैं?
- किसी ग्राफ़ को बिना क्रॉसिंग के समतल में कब खींचा जा सकता है या कुछ रंगों से रंगा जा सकता है?
- किसी दिए गए उपसंरचना से बचते हुए एक ग्राफ़ कितना बड़ा या सघन हो सकता है?
- पथ, मिलान और प्रवाह किसी नेटवर्क पर अनुकूलन कैसे करने देते हैं?
Key concepts
- शीर्ष, किनारे और डिग्री
- संयोजकता और घटक
- पथ, चक्र और वृक्ष
- समतलता
- ग्राफ़ रंगाई
- मिलान और प्रवाह
Clinical relevance
ग्राफ़ संचार और परिवहन नेटवर्कों, सामाजिक और जैविक अंतःक्रिया नेटवर्कों, सर्किट और निर्भरता संरचनाओं, और शेड्यूलिंग समस्याओं का मॉडल बनाते हैं, जिससे ग्राफ़ सिद्धांत कंप्यूटर विज्ञान और संचालन अनुसंधान में एक मूलभूत उपकरण बन जाता है।
History
ग्राफ़ सिद्धांत का पता यूलर के कोनिग्सबर्ग पुलों की समस्या के 1736 के समाधान से चलता है और 20वीं शताब्दी में रंगाई, संयोजकता, और एर्डोस, टुट्टे और अन्य के संभाव्य और संरचनात्मक तरीकों पर काम के माध्यम से परिपक्व हुआ।
Key figures
- Leonhard Euler
- William Tutte
- Bela Bollobas
Related topics
Seminal works
- diestel2017
- bollobas1998
Frequently asked questions
- एक ग्राफ़ और एक नेटवर्क में क्या अंतर है?
- एक ग्राफ़ शीर्षों और किनारों की अमूर्त गणितीय वस्तु है; एक नेटवर्क आमतौर पर एक ग्राफ़ को संदर्भित करता है जिसमें अतिरिक्त डेटा जैसे भार, क्षमताएं, या दिशाएं एक वास्तविक प्रणाली का मॉडल बनाती हैं।
- कोनिग्सबर्ग पुल समस्या क्यों महत्वपूर्ण थी?
- यूलर का प्रमाण कि कोई भी चाल सात पुलों में से प्रत्येक को ठीक एक बार पार नहीं कर सकती थी, ने समस्या को शीर्षों और किनारों तक अमूर्त कर दिया, जिससे ग्राफ़ सिद्धांत और टोपोलॉजी की नींव पड़ी।