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

From Vigyanwiki
No edit summary
No edit summary
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]
[[File:Heawood graph and map on torus.png|thumb|[[हेवुड ग्राफ]]़ और संबंधित मानचित्र टोरस में सन्निहित है।]]


Line 35: Line 32:


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


==शब्दावली==
==शब्दावली==
Line 100: Line 93:
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
[[Category: टोपोलॉजिकल ग्राफ सिद्धांत]] [[Category: ग्राफ़ एल्गोरिदम]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:Created On 01/07/2023]]
[[Category:Created On 01/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:ग्राफ़ एल्गोरिदम]]
[[Category:टोपोलॉजिकल ग्राफ सिद्धांत]]

Latest revision as of 18:12, 12 July 2023

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


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

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

यहां एक सतह -मैनिफोल्ड से जुड़ी एक कॉम्पैक्ट है।

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

अक्सर, एक एम्बेडिंग को वर्णित प्रकार के अभ्यावेदन के समतुल्य वर्ग ( के होमोमोर्फिज्म के तहत) के रूप में माना जाता है।

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

यह आलेख केवल ग्राफ़ एम्बेडिंग की सख्त परिभाषा से संबंधित है। ग्राफ ड्राइंग और क्रॉसिंग नंबर (ग्राफ सिद्धांत) लेखों में अशक्त परिभाषा पर चर्चा की गई है।

शब्दावली

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

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

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

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

किसी ग्राफ़ का अधिकतम जीनस अधिकतम पूर्णांक होता है, जिससे ग्राफ़ जीनस की ओरिएंटेबल सतह में -सेल एम्बेडेड हो सकता है।

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

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

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

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

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

ग्राफ़ जीनस खोजने की समस्या एनपी-हार्ड है (यह निर्धारित करने की समस्या कि -वर्टेक्स ग्राफ़ में जीनस है या नहीं, एनपी-पूर्ण है)।[8]

एक ही समय में ग्राफ जीनस समस्या निश्चित-पैरामीटर ट्रैक्टेबल है, अथार्त , बहुपद समय एल्गोरिदम को यह जांचने के लिए जाना जाता है कि क्या एक ग्राफ को किसी दिए गए निश्चित जीनस की सतह में एम्बेड किया जा सकता है और साथ ही एम्बेडिंग भी खोजी जा सकती है।

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

1999 में यह बताया गया कि फिक्स्ड-जीनस स्थिति को ग्राफ आकार में रैखिक समय और जीनस में दोहरा घातीय कार्य में हल किया जा सकता है।[11]


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

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

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

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

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

गैलरी


यह भी देखें

संदर्भ

  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