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

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

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

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

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

• 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