ग्राफ एम्बेडिंग: Difference between revisions

From Vigyanwiki
(Created page with "{{Use American English|date = February 2019}} {{Short description|Embedding a graph in a topological space, often Euclidean}} {{Use mdy dates|date = February 2019}} File:He...")
 
No edit summary
Line 1: Line 1:
{{Use American English|date = February 2019}}
 
{{Short description|Embedding a graph in a topological space, often Euclidean}}
 
{{Use mdy dates|date = February 2019}}


[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]टोपोलॉजिकल ग्राफ़ सिद्धांत में, एक ग्राफ़ (असतत गणित) का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) <math>G</math> एक सतह पर (गणित) <math>\Sigma</math> का प्रतिनिधित्व है <math>G</math> पर <math>\Sigma</math> के किन बिंदुओं में <math>\Sigma</math> [[ग्राफ सिद्धांत]] और सरल चाप ([[होमियोमोर्फिज्म]] छवियां) से जुड़े हैं <math>[0,1]</math>) ग्राफ़ सिद्धांत से इस प्रकार जुड़े हैं कि:
[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]टोपोलॉजिकल ग्राफ़ सिद्धांत में, एक ग्राफ़ (असतत गणित) का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) <math>G</math> एक सतह पर (गणित) <math>\Sigma</math> का प्रतिनिधित्व है <math>G</math> पर <math>\Sigma</math> के किन बिंदुओं में <math>\Sigma</math> [[ग्राफ सिद्धांत]] और सरल चाप ([[होमियोमोर्फिज्म]] छवियां) से जुड़े हैं <math>[0,1]</math>) ग्राफ़ सिद्धांत से इस प्रकार जुड़े हैं कि:
Line 36: Line 35:
के शीर्ष और किनारे <math>G</math> क्षेत्रों (या फलक (ग्राफ़ सिद्धांत)) का एक परिवार है।<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=978-0-486-41741-7}}.</ref> 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के लिए होमियोमॉर्फिक होता है।<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=978-3-540-00203-1}}.</ref> एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।
के शीर्ष और किनारे <math>G</math> क्षेत्रों (या फलक (ग्राफ़ सिद्धांत)) का एक परिवार है।<ref name="gt01">{{citation|last1=Gross|first1=Jonathan|last2=Tucker|first2=Thomas W.|authorlink2= Thomas W. Tucker| title=Topological Graph Theory|publisher=Dover Publications|year=2001|isbn=978-0-486-41741-7}}.</ref> 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के लिए होमियोमॉर्फिक होता है।<ref>{{citation|last1=Lando|first1=Sergei K.|last2=Zvonkin|first2=Alexander K.|title=Graphs on Surfaces and their Applications|publisher=Springer-Verlag|year=2004|isbn=978-3-540-00203-1}}.</ref> एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।


ग्राफ़ का जीनस (असतत गणित) न्यूनतम पूर्णांक है <math>n</math> इस तरह कि ग्राफ़ को जीनस (गणित) की सतह में एम्बेड किया जा सकता है <math>n</math>. विशेष रूप से, एक समतलीय ग्राफ़ में जीनस होता है <math>0</math>, क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे [[ टोरस्र्स ]] पर एम्बेड किया जा सकता है उसे [[टोरॉयडल ग्राफ]] कहा जाता है।
ग्राफ़ का जीनस (असतत गणित) न्यूनतम पूर्णांक है <math>n</math> इस तरह कि ग्राफ़ को जीनस (गणित) की सतह में एम्बेड किया जा सकता है <math>n</math>. विशेष रूप से, एक समतलीय ग्राफ़ में जीनस होता है <math>0</math>, क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे [[ टोरस्र्स |टोरस्र्स]] पर एम्बेड किया जा सकता है उसे [[टोरॉयडल ग्राफ]] कहा जाता है।


ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है <math>n</math>.<ref name="gt01"/>
ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है <math>n</math> ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है <math>n</math>.<ref name="gt01"/>
Line 46: Line 45:
==कॉम्बिनेटोरियल एम्बेडिंग==
==कॉम्बिनेटोरियल एम्बेडिंग==
{{main|Rotation system}}
{{main|Rotation system}}
एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के [[चक्रीय क्रम]] को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान [[ रोटेशन प्रणाली ]] वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, रोटेशन सिस्टम को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=1995|volume=894|pages=76–83|doi=10.1007/3-540-58950-3_358|title-link=International Symposium on Graph Drawing|isbn=978-3-540-58950-1|doi-access=free}}.</ref><ref>{{citation|first1=Christian|last1=Duncan|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Stephen|last3=Kobourov|title=Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=2010|pages=45–56|doi=10.1007/978-3-642-11805-0_7|volume=5849|chapter=Planar Drawings of Higher-Genus Graphs|isbn=978-3-642-11804-3|title-link=International Symposium on Graph Drawing|arxiv=0908.1608}}.</ref>
एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के [[चक्रीय क्रम]] को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान [[ रोटेशन प्रणाली |रोटेशन प्रणाली]] वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, रोटेशन सिस्टम को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।<ref>{{citation|first1=Petra|last1=Mutzel|author1-link=Petra Mutzel|first2=René|last2=Weiskircher|title=Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings|year=2000|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=1858|pages=95–104|doi=10.1007/3-540-44968-X_10|chapter=Computing Optimal Embeddings for Planar Graphs|isbn=978-3-540-67787-1}}.</ref><ref>{{citation|last=Didjev|first=Hristo N.|contribution=On drawing a graph convexly in the plane|title=Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=1995|volume=894|pages=76–83|doi=10.1007/3-540-58950-3_358|title-link=International Symposium on Graph Drawing|isbn=978-3-540-58950-1|doi-access=free}}.</ref><ref>{{citation|first1=Christian|last1=Duncan|first2=Michael T.|last2=Goodrich|author2-link=Michael T. Goodrich|first3=Stephen|last3=Kobourov|title=Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|year=2010|pages=45–56|doi=10.1007/978-3-642-11805-0_7|volume=5849|chapter=Planar Drawings of Higher-Genus Graphs|isbn=978-3-642-11804-3|title-link=International Symposium on Graph Drawing|arxiv=0908.1608}}.</ref>
एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। हालाँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ मामलों में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह हमेशा पेड़ों के एम्बेडिंग के मामले में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को हमेशा विपरीत दिशाओं में पार किया जाता है।
एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। हालाँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ मामलों में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह हमेशा पेड़ों के एम्बेडिंग के मामले में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को हमेशा विपरीत दिशाओं में पार किया जाता है।


सेलुलर एम्बेडिंग के लिए अन्य समकक्ष प्रतिनिधित्व में [[रिबन ग्राफ]], एक एम्बेडेड ग्राफ के कोने और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर गठित एक टोपोलॉजिकल स्पेस, [[ग्राफ़-एन्कोडेड मानचित्र]] मानचित्र, प्रत्येक किनारे के लिए चार कोने के साथ एक किनारे-रंगीन [[ घन ग्राफ ]] शामिल है। एम्बेडेड ग्राफ़.
सेलुलर एम्बेडिंग के लिए अन्य समकक्ष प्रतिनिधित्व में [[रिबन ग्राफ]], एक एम्बेडेड ग्राफ के कोने और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर गठित एक टोपोलॉजिकल स्पेस, [[ग्राफ़-एन्कोडेड मानचित्र]] मानचित्र, प्रत्येक किनारे के लिए चार कोने के साथ एक किनारे-रंगीन [[ घन ग्राफ |घन ग्राफ]] शामिल है। एम्बेडेड ग्राफ़.


==कम्प्यूटेशनल जटिलता==
==कम्प्यूटेशनल जटिलता==


ग्राफ़ जीनस को खोजने की समस्या [[ एनपी कठिन ]] है (यह निर्धारित करने की समस्या कि क्या कोई <math>n</math>-वर्टेक्स ग्राफ में जीनस है <math>g</math> एनपी-पूर्ण है)।<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>
ग्राफ़ जीनस को खोजने की समस्या [[ एनपी कठिन |एनपी कठिन]] है (यह निर्धारित करने की समस्या कि क्या कोई <math>n</math>-वर्टेक्स ग्राफ में जीनस है <math>g</math> एनपी-पूर्ण है)।<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>
साथ ही, ग्राफ़ जीनस समस्या [[फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी]] है। फिक्स्ड-पैरामीटर ट्रैक्टेबल, यानी, बहुपद समय एल्गोरिदम यह जांचने के लिए जाने जाते हैं कि ग्राफ़ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है या नहीं और साथ ही एम्बेडिंग भी ढूंढी जा सकती है। .
साथ ही, ग्राफ़ जीनस समस्या [[फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी]] है। फिक्स्ड-पैरामीटर ट्रैक्टेबल, यानी, बहुपद समय एल्गोरिदम यह जांचने के लिए जाने जाते हैं कि ग्राफ़ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है या नहीं और साथ ही एम्बेडिंग भी ढूंढी जा सकती है। .


Line 64: Line 63:
यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।<ref name="3d-gd"/>
यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।<ref name="3d-gd"/>


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


वैकल्पिक रूप से, किसी भी परिमित ग्राफ को उसके शीर्षों को [[सामान्य स्थिति]] में रखकर तीन आयामों में सीधी रेखा के किनारों के साथ बिना किसी क्रॉसिंग के खींचा जा सकता है ताकि कोई भी चार समतलीय न हो। उदाहरण के लिए, इसे ith शीर्ष को बिंदु (i,i) पर रखकर प्राप्त किया जा सकता है<sup>2</sup>,i<sup>3</sup>) [[क्षण वक्र]] का।
वैकल्पिक रूप से, किसी भी परिमित ग्राफ को उसके शीर्षों को [[सामान्य स्थिति]] में रखकर तीन आयामों में सीधी रेखा के किनारों के साथ बिना किसी क्रॉसिंग के खींचा जा सकता है ताकि कोई भी चार समतलीय न हो। उदाहरण के लिए, इसे ith शीर्ष को बिंदु (i,i) पर रखकर प्राप्त किया जा सकता है<sup>2</sup>,i<sup>3</sup>) [[क्षण वक्र]] का।

Revision as of 07:50, 7 July 2023


हेवुड ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।

टोपोलॉजिकल ग्राफ़ सिद्धांत में, एक ग्राफ़ (असतत गणित) का एक एम्बेडिंग (इम्बेडिंग भी लिखा जाता है) एक सतह पर (गणित) का प्रतिनिधित्व है पर के किन बिंदुओं में ग्राफ सिद्धांत और सरल चाप (होमियोमोर्फिज्म छवियां) से जुड़े हैं ) ग्राफ़ सिद्धांत से इस प्रकार जुड़े हैं कि:

  • एक किनारे से जुड़े चाप के अंतिम बिंदु के अंतिम शीर्षों से जुड़े बिंदु हैं
  • किसी भी चाप में अन्य शीर्षों से जुड़े बिंदु शामिल नहीं हैं,
  • दो चाप कभी भी ऐसे बिंदु पर प्रतिच्छेद नहीं करते जो किसी भी चाप का आंतरिक भाग हो।

यहाँ एक सतह एक सघन स्थान है[citation needed], जुड़ा हुआ स्थान -कई गुना.

अनौपचारिक रूप से, किसी ग्राफ़ को किसी सतह पर एम्बेड करना सतह पर ग्राफ़ को इस तरह से चित्रित करना है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद कर सकें। यह सर्वविदित है कि किसी भी परिमित ग्राफ को 3-आयामी यूक्लिडियन अंतरिक्ष में एम्बेड किया जा सकता है .[1] एक समतलीय ग्राफ वह है जिसे 2-आयामी यूक्लिडियन अंतरिक्ष में एम्बेड किया जा सकता है अक्सर, एम्बेडिंग को एक तुल्यता वर्ग (होमोमॉर्फिज्म के तहत) के रूप में माना जाता है ) अभी वर्णित प्रकार के अभ्यावेदन।

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

शब्दावली

एक ग्राफ का एक बंद सतह पर जड़ा हुआ है , से जुड़े बिंदुओं और चापों के मिलन का पूरक के शीर्ष और किनारे क्षेत्रों (या फलक (ग्राफ़ सिद्धांत)) का एक परिवार है।[3] 2-सेल एम्बेडिंग, सेल्युलर एम्बेडिंग या मैप एक एम्बेडिंग है जिसमें प्रत्येक चेहरा एक खुली डिस्क के लिए होमियोमॉर्फिक होता है।[4] एक बंद 2-सेल एम्बेडिंग एक एम्बेडिंग है जिसमें प्रत्येक चेहरे का बंद होना एक बंद डिस्क के होमियोमॉर्फिक है।

ग्राफ़ का जीनस (असतत गणित) न्यूनतम पूर्णांक है इस तरह कि ग्राफ़ को जीनस (गणित) की सतह में एम्बेड किया जा सकता है . विशेष रूप से, एक समतलीय ग्राफ़ में जीनस होता है , क्योंकि इसे स्वयं-क्रॉसिंग के बिना एक गोले पर खींचा जा सकता है। एक ग्राफ जिसे टोरस्र्स पर एम्बेड किया जा सकता है उसे टोरॉयडल ग्राफ कहा जाता है।

ग्राफ़ (असतत गणित) का गैर-उन्मुख जीनस न्यूनतम पूर्णांक है ऐसा कि ग्राफ़ को (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में एम्बेड किया जा सकता है .[3]

ग्राफ़ का यूलर जीनस न्यूनतम पूर्णांक है ऐसा कि ग्राफ़ को (ओरिएंटेबल) जीनस की ओरिएंटेबल सतह में एम्बेड किया जा सकता है या (गैर-उन्मुख) जीनस की एक गैर-उन्मुख सतह में . एक ग्राफ उन्मुख रूप से सरल होता है यदि इसका यूलर जीनस इसके गैर-उन्मुख जीनस से छोटा है।

ग्राफ़ (असतत गणित) का अधिकतम जीनस अधिकतम पूर्णांक है ऐसा कि ग्राफ हो सकता है -सेल जीनस (गणित) की एक उन्मुख सतह में एम्बेडेड है .

कॉम्बिनेटोरियल एम्बेडिंग

Main article: Rotation system

एक एम्बेडेड ग्राफ़ एक ही शीर्ष पर आपतित किनारों के चक्रीय क्रम को विशिष्ट रूप से परिभाषित करता है। इन सभी चक्रीय आदेशों के समुच्चय को घूर्णन प्रणाली कहा जाता है। समान रोटेशन प्रणाली वाले एंबेडिंग्स को समतुल्य माना जाता है और एंबेडिंग्स के संबंधित समतुल्य वर्ग को कॉम्बिनेटोरियल एंबेडिंग कहा जाता है (टोपोलॉजिकल एंबेडिंग शब्द के विपरीत, जो बिंदुओं और वक्रों के संदर्भ में पिछली परिभाषा को संदर्भित करता है)। कभी-कभी, रोटेशन सिस्टम को ही कॉम्बिनेटोरियल एम्बेडिंग कहा जाता है।[5][6][7] एक एम्बेडेड ग्राफ़ किनारों के प्राकृतिक चक्रीय क्रम को भी परिभाषित करता है जो एम्बेडिंग के चेहरों की सीमाओं का गठन करता है। हालाँकि इन फेस-आधारित आदेशों को संभालना कम सरल है, क्योंकि कुछ मामलों में कुछ किनारों को फेस सीमा के साथ दो बार पार किया जा सकता है। उदाहरण के लिए, यह हमेशा पेड़ों के एम्बेडिंग के मामले में होता है, जिनका एक ही चेहरा होता है। इस संयुक्त उपद्रव को दूर करने के लिए, कोई यह मान सकता है कि प्रत्येक किनारे को लंबाई में दो आधे-किनारों, या किनारों में विभाजित किया गया है। इस परिपाटी के तहत सभी फेस सीमा ट्रैवर्सल में प्रत्येक आधे किनारे को केवल एक बार पार किया जाता है और एक ही किनारे के दो आधे किनारों को हमेशा विपरीत दिशाओं में पार किया जाता है।

सेलुलर एम्बेडिंग के लिए अन्य समकक्ष प्रतिनिधित्व में रिबन ग्राफ, एक एम्बेडेड ग्राफ के कोने और किनारों के लिए टोपोलॉजिकल डिस्क को एक साथ जोड़कर गठित एक टोपोलॉजिकल स्पेस, ग्राफ़-एन्कोडेड मानचित्र मानचित्र, प्रत्येक किनारे के लिए चार कोने के साथ एक किनारे-रंगीन घन ग्राफ शामिल है। एम्बेडेड ग्राफ़.

कम्प्यूटेशनल जटिलता

ग्राफ़ जीनस को खोजने की समस्या एनपी कठिन है (यह निर्धारित करने की समस्या कि क्या कोई -वर्टेक्स ग्राफ में जीनस है एनपी-पूर्ण है)।[8] साथ ही, ग्राफ़ जीनस समस्या फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी है। फिक्स्ड-पैरामीटर ट्रैक्टेबल, यानी, बहुपद समय एल्गोरिदम यह जांचने के लिए जाने जाते हैं कि ग्राफ़ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है या नहीं और साथ ही एम्बेडिंग भी ढूंढी जा सकती है। .

इस संबंध में पहली सफलता 1979 में हुई, जब समय जटिलता के एल्गोरिदम परओ(जी)) को स्वतंत्र रूप से कंप्यूटिंग के सिद्धांत पर वार्षिक एसीएम संगोष्ठी में प्रस्तुत किया गया था: आई. फिलोटी और गैरी मिलर (कंप्यूटर वैज्ञानिक)|जी.एल. मिलर और दूसरा जॉन रीफ़ द्वारा। उनके दृष्टिकोण बिल्कुल अलग थे, लेकिन कार्यक्रम समिति के सुझाव पर उन्होंने एक संयुक्त पत्र प्रस्तुत किया।[9] हालाँकि, वेंडी मायरवॉल्ड और विलियम लॉरेंस कोके ने 2011 में साबित किया कि फिलोटी, मिलर और रीफ द्वारा दिया गया एल्गोरिदम गलत था।[10] 1999 में यह बताया गया कि फिक्स्ड-जीनस मामले को ग्राफ आकार में रैखिक समय और जीनस में दोहरा घातीय कार्य में हल किया जा सकता है।[11]


उच्च-आयामी स्थानों में ग्राफ़ का एम्बेडिंग

यह ज्ञात है कि किसी भी परिमित ग्राफ को त्रि-आयामी स्थान में एम्बेड किया जा सकता है।[1]

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

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

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

गैलरी

  • पीटरसन ग्राफ़ और संबंधित मानचित्र प्रक्षेप्य तल में सन्निहित है। वृत्त पर विपरीत बिंदुओं की पहचान गैर-उन्मुख जीनस 1 की एक बंद सतह के रूप में की जाती है।

    पीटरसन ग्राफ़ और संबंधित मानचित्र प्रक्षेप्य तल में सन्निहित है। वृत्त पर विपरीत बिंदुओं की पहचान गैर-उन्मुख जीनस 1 की एक बंद सतह के रूप में की जाती है।

  • पप्पस ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।

    पप्पस ग्राफ़ और संबंधित मानचित्र टोरस में सन्निहित है।

  • डिग्री 7 क्लेन ग्राफ और संबंधित मानचित्र जीनस 3 की एक उन्मुख सतह में एम्बेडेड है।

    डिग्री 7 क्लेन ग्राफ और संबंधित मानचित्र जीनस 3 की एक उन्मुख सतह में एम्बेडेड है।


यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Cohen, Robert F.; Eades, Peter; Lin, Tao; Ruskey, Frank (1995), "Three-dimensional graph drawing", in Tamassia, Roberto; Tollis, Ioannis G. (eds.), Graph Drawing: DIMACS International Workshop, GD '94 Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer, pp. 1–11, doi:10.1007/3-540-58950-3_351, ISBN 978-3-540-58950-1.
  2. ↑ Katoh, Naoki; Tanigawa, Shin-ichi (2007), "Enumerating Constrained Non-crossing Geometric Spanning Trees", Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings, Lecture Notes in Computer Science, vol. 4598, Springer-Verlag, pp. 243–253, CiteSeerX 10.1.1.483.874, doi:10.1007/978-3-540-73545-8_25, ISBN 978-3-540-73544-1.
  3. ↑ 3.0 3.1 Gross, Jonathan; Tucker, Thomas W. (2001), Topological Graph Theory, Dover Publications, ISBN 978-0-486-41741-7.
  4. ↑ Lando, Sergei K.; Zvonkin, Alexander K. (2004), Graphs on Surfaces and their Applications, Springer-Verlag, ISBN 978-3-540-00203-1.
  5. ↑ Mutzel, Petra; Weiskircher, René (2000), "Computing Optimal Embeddings for Planar Graphs", Computing and Combinatorics, 6th Annual International Conference, COCOON 2000, Sydney, Australia, July 26–28, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1858, Springer-Verlag, pp. 95–104, doi:10.1007/3-540-44968-X_10, ISBN 978-3-540-67787-1.
  6. ↑ Didjev, Hristo N. (1995), "On drawing a graph convexly in the plane", Graph Drawing, DIMACS International Workshop, GD '94, Princeton, New Jersey, USA, October 10–12, 1994, Proceedings, Lecture Notes in Computer Science, vol. 894, Springer-Verlag, pp. 76–83, doi:10.1007/3-540-58950-3_358, ISBN 978-3-540-58950-1.
  7. ↑ Duncan, Christian; Goodrich, Michael T.; Kobourov, Stephen (2010), "Planar Drawings of Higher-Genus Graphs", Graph Drawing, 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Springer-Verlag, pp. 45–56, arXiv:0908.1608, doi:10.1007/978-3-642-11805-0_7, ISBN 978-3-642-11804-3.
  8. ↑ Thomassen, Carsten (1989), "The graph genus problem is NP-complete", Journal of Algorithms, 10 (4): 568–576, doi:10.1016/0196-6774(89)90006-0
  9. ↑ Filotti, I. S.; Miller, Gary L.; Reif, John (1979), "On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)", Proc. 11th Annu. ACM Symposium on Theory of Computing, pp. 27–37, doi:10.1145/800135.804395.
  10. ↑ Myrvold, Wendy; Kocay, William (March 1, 2011). "ग्राफ़ एम्बेडिंग एल्गोरिदम में त्रुटियाँ". Journal of Computer and System Sciences. 2 (77): 430–438. doi:10.1016/j.jcss.2010.06.002.
  11. ↑ Mohar, Bojan (1999), "A linear time algorithm for embedding graphs in an arbitrary surface", SIAM Journal on Discrete Mathematics, 12 (1): 6–26, CiteSeerX 10.1.1.97.9588, doi:10.1137/S089548019529248X
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ग्राफ_एम्बेडिंग&oldid=214226’