ज्यामितीय ग्राफ सिद्धांत

व्यापक अर्थों में ज्यामितीय ग्राफ़ सिद्धांत, ग्राफ़ सिद्धांत का एक बड़ा और अनाकार उपक्षेत्र है, जो ज्यामितीय साधनों द्वारा परिभाषित ग्राफ़ (असतत गणित) से संबंधित है। एक सख्त अर्थ में, ज्यामितीय ग्राफ सिद्धांत ज्यामितीय ग्राफ के संयोजी और ज्यामितीय गुणों का अध्ययन करता है, जिसका अर्थ है कि यूक्लिडियन विमान में खींचे गए रेखांकन संभवतः सीधी-रेखा किनारे (ज्यामिति), और स्थलीय रेखांकन के साथ होते हैं, जहां किनारों को मनमाना निरंतर घटता जोड़ने की अनुमति होती है। शीर्ष (ग्राफ सिद्धांत) , इस प्रकार यह ज्यामितिक और टोपोलॉजिकल ग्राफ (Pach 2013) का सिद्धांत है। ज्यामितीय रेखांकन को स्थानिक नेटवर्क के रूप में भी जाना जाता है।

विभिन्न प्रकार के ज्यामितीय रेखांकन

एक प्लानर स्ट्रेट-लाइन ग्राफ एक ग्राफ़ है जिसमें कोने यूक्लिडियन प्लेन में बिंदुओं के रूप में एम्बेडेड होते हैं, और किनारों को गैर-क्रॉसिंग लाइन सेगमेंट के रूप में एम्बेड किया जाता है। फेरी के प्रमेय में कहा गया है कि किसी भी प्लानर ग्राफ को प्लानर स्ट्रेट लाइन ग्राफ के रूप में दर्शाया जा सकता है। एक प्वाइंट सेट त्रिकोण एक प्लेनर स्ट्रेट लाइन ग्राफ है जिसमें कोई और किनारा नहीं जोड़ा जा सकता है, इसलिए कहा जाता है क्योंकि हर चेहरा एक त्रिकोण है; इसका एक विशेष मामला Delaunay त्रिभुज है, एक ग्राफ जो समतल में बिंदुओं के एक सेट से दो बिंदुओं को एक किनारे से जोड़कर परिभाषित किया जाता है, जब भी केवल उन दो बिंदुओं वाला एक वृत्त मौजूद होता है।

बहुतल या polytope का 1-कंकाल (टोपोलॉजी) उक्त पॉलीहेड्रॉन या पॉलीटॉप के कोने और किनारों का सेट है। किसी भी उत्तल पॉलीहेड्रॉन का कंकाल एक प्लानर ग्राफ है, और किसी भी के-आयामी उत्तल पॉलीटॉप का कंकाल एक के-वर्टेक्स-कनेक्टेड ग्राफ | के-कनेक्टेड ग्राफ है। इसके विपरीत, स्टीनिट्ज़ के प्रमेय में कहा गया है कि कोई भी 3-कनेक्टेड प्लानर ग्राफ उत्तल पॉलीहेड्रॉन का कंकाल है; इस कारण से, ग्राफ़ के इस वर्ग को बहुफलकीय ग्राफ ़ के रूप में भी जाना जाता है।

एक यूक्लिडियन ग्राफ एक ग्राफ है जिसमें कोने विमान में बिंदुओं का प्रतिनिधित्व करते हैं, और किनारों को उन बिंदुओं के बीच यूक्लिडियन दूरी के बराबर लंबाई दी जाती है। यूक्लिडियन न्यूनतम फैला हुआ पेड़ यूक्लिडियन पूर्ण ग्राफ का न्यूनतम फैला हुआ पेड़ है। दूरियों पर शर्तों द्वारा ग्राफ़ को परिभाषित करना भी संभव है; विशेष रूप से, एक इकाई दूरी का ग्राफ उन बिंदुओं के जोड़े को जोड़कर बनाया जाता है जो विमान में एक दूसरे से एक इकाई दूरी पर होते हैं। हैडविगर-नेल्सन समस्या इन ग्राफों की रंगीन संख्या से संबंधित है।

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

बिंदुओं और रेखाओं के एक परिवार के एक लेवी ग्राफ में इनमें से प्रत्येक वस्तु के लिए एक शीर्ष और प्रत्येक घटना बिंदु-रेखा जोड़ी के लिए एक किनारा होता है। प्रक्षेपी विन्यास के लेवी ग्राफ कई महत्वपूर्ण सममित रेखांकन और केज (ग्राफ सिद्धांत) की ओर ले जाते हैं।

एक बंद बहुभुज का दृश्यता ग्राफ प्रत्येक जोड़े को एक किनारे से जोड़ता है जब भी कोने को जोड़ने वाला रेखा खंड पूरी तरह से बहुभुज में स्थित होता है। यह ज्ञात नहीं है कि कुशलतापूर्वक परीक्षण कैसे किया जाए कि एक अप्रत्यक्ष ग्राफ को दृश्यता ग्राफ के रूप में प्रदर्शित किया जा सकता है या नहीं।

एक आंशिक घन एक ग्राफ है जिसके लिए कोने को अतिविम के कोने से जोड़ा जा सकता है, इस तरह से कि ग्राफ में दूरी संबंधित हाइपरक्यूब शिखर के बीच हैमिंग दूरी के बराबर होती है। संयोजी संरचनाओं के कई महत्वपूर्ण परिवार, जैसे कि एक ग्राफ के एसाइक्लिक ओरिएंटेशन या हाइपरप्लेन व्यवस्था में क्षेत्रों के बीच निकटता, को आंशिक क्यूब ग्राफ के रूप में दर्शाया जा सकता है। एक आंशिक घन का एक महत्वपूर्ण विशेष मामला कटा हुआ ऑक्टाहेड्रोन का कंकाल है, एक ग्राफ जिसमें कोने क्रमबद्ध वस्तुओं के एक सेट के क्रमपरिवर्तन का प्रतिनिधित्व करते हैं और किनारे क्रम में आसन्न वस्तुओं के स्वैप का प्रतिनिधित्व करते हैं। माध्य रेखांकन सहित ग्राफ़ के कई अन्य महत्वपूर्ण वर्गों में मीट्रिक एम्बेडिंग से संबंधित परिभाषाएँ हैं (Bandelt & Chepoi 2008).

एक फ्लिप ग्राफ एक बिंदु सेट के त्रिकोणासन से बना एक ग्राफ है, जिसमें प्रत्येक शीर्ष एक त्रिभुज का प्रतिनिधित्व करता है और दो त्रिभुज एक किनारे से जुड़े होते हैं यदि वे एक किनारे के दूसरे किनारे के प्रतिस्थापन से भिन्न होते हैं। चतुर्भुजों या छद्मत्रिभुजों में विभाजनों के लिए और उच्च-आयामी त्रिभुजों के लिए संबंधित फ़्लिप ग्राफ़ को परिभाषित करना भी संभव है। एक उत्तल बहुभुज के त्रिकोणासन का फ्लिप ग्राफ associahedron या स्टैशेफ पॉलीटॉप का कंकाल बनाता है। बिंदु सेट त्रिभुज का फ्लिप ग्राफ़ # बिंदु सेट के नियमित त्रिभुज (उच्च-आयामी उत्तल हल्स के अनुमान) को तथाकथित माध्यमिक पॉलीटॉप के कंकाल के रूप में भी प्रदर्शित किया जा सकता है।

यह भी देखें

• सामयिक ग्राफ सिद्धांत
• रासायनिक ग्राफ
• स्थानिक नेटवर्क

संदर्भ

• Bandelt, Hans-Jürgen; Chepoi, Victor (2008). "Metric graph theory and geometry: a survey" (PDF). Surveys on Discrete and Computational Geometry - Twenty Years Later. Contemporary Mathematics. Vol. 453. American Mathematical Society. pp. 49–86.
• Pach, János, ed. (2004). Towards a Theory of Geometric Graphs. Contemporary Mathematics. Vol. 342. American Mathematical Society.
• Pach, János (2013). "The beginnings of geometric graph theory". Erdös centennial. Bolyai Soc. Math. Stud. Vol. 25. Budapest: János Bolyai Math. Soc. pp. 465–484. doi:10.1007/978-3-642-39286-3_17. MR 3203608.
• Pisanski, Tomaž; Randić, Milan (2000). "Bridges between geometry and graph theory". In Gorini, C. A. (ed.). Geometry at Work: Papers in Applied Geometry. Washington, DC: Mathematical Association of America. pp. 174–194. Archived from the original on 2007-09-27.

बाहरी संबंध

• Media related to ज्यामितीय ग्राफ सिद्धांत at Wikimedia Commons