ग्राफ एम्बेडिंग

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

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

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

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

अनौपचारिक रूप से, किसी ग्राफ़ को किसी सतह पर एम्बेड करना सतह पर ग्राफ़ को इस तरह से चित्रित करना है कि इसके किनारे केवल अपने अंतिम बिंदुओं पर ही प्रतिच्छेद कर सकता है। यह सर्वविदित है कि किसी भी परिमित ग्राफ को 3-आयामी यूक्लिडियन स्पेस $\mathbb {R} ^{3}$ में एम्बेड किया जा सकता है। एक समतल ग्राफ वह है जिसे 2-आयामी यूक्लिडियन स्पेस $\mathbb {R} ^{2}.$ में एम्बेड किया जा सकता है।

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

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

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

शब्दावली

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

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

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

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

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

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

Main article: घूर्णन प्रणाली

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

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

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

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

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

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

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

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

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

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

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

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

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

गैलरी

• 

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

• 

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

• 

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

यह भी देखें

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