ग्राफ - ग्राफ में एंबेडेड और टॉपोलॉजिकल के बीच अंतर क्या हैं?

Question

Algorithm Design Manual में, पृष्ठ 178 ग्राफ़ के कुछ गुणों का वर्णन है, और उनमें से एक अंतर्निहित है और Topological:

बनाम Topological

एंबेडेड

एक ग्राफ एम्बेडेड है अगर कोने और किनारों ज्यामितीय पदों आवंटित कर रहे हैं । इस प्रकार, ग्राफ का कोई भी चित्र एक एम्बेडिंग है, जो एल्गोरिदमिक महत्व हो सकता है या नहीं भी हो सकता है।

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

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

मैं काफी यह समझ में नहीं आता:

1. सबसे पहले, embedded यहाँ वास्तव में क्या मतलब है? जब तक कि शिखर के पास अपनी ज्यामितीय स्थिति होती है, तो क्या मैं एम्बेडेड ग्राफ को कॉल कर सकता हूं?
2. any drawing of a graph is an embedding का क्या अर्थ है? क्या इसका मतलब यह है कि मैंने बिंदु 1 में क्या कहा था?
3. Topological का अर्थ क्या है? मुझे नहीं लगता कि यह इस वर्णन में समझाया गया है।
4. इस विवरण में दिए गए उदाहरणों ने वास्तव में मुझे बहुत भ्रमित कर दिया। क्या कोई मुझे ग्राफ के लिए इन दो शर्तों को समझने के लिए सरल शब्दों का उपयोग कर सकता है?
5. क्या इन दो शब्दों को समझना वाकई महत्वपूर्ण है?

धन्यवाद

Answer 1

1. मैं आपको याद दिलाना है कि एक ग्राफ बस कोने का एक सेट और उन पर परिभाषित किनारों का एक सेट है, तो कोने उनकी खुद की एक ज्यामितीय स्थिति नहीं है। ग्राफ के चित्र को एम्बेडिंग कहा जाता है, एक खींचे गए ग्राफ को एम्बेडेड कहा जाता है।
2. इसका मतलब है कि ग्राफ को चित्रित करने का कोई भी तरीका उस ग्राफ का एम्बेडिंग कहलाता है।
3. एक स्थलीय ग्राफ एक ग्राफ है जिसका चरम और किनारों क्रमशः अंक और arcs हैं।

Answer 2

स्कीनिया भौगोलिक दोस्ती ग्राफ का उपयोग एम्बेडेड ग्राफ के लिए एक उदाहरण के रूप में करता है क्योंकि प्रत्येक वर्टेक्स इस दुनिया में भौगोलिक बिंदु से जुड़ा हुआ है जहां मित्र रहते हैं।

पुस्तक से उद्धरण - क्या मेरे दोस्त मेरे पास रहते हैं? - भूगोल से सामाजिक नेटवर्क तलाकशुदा नहीं हैं। आपके कई मित्र केवल आपके मित्र हैं क्योंकि वे आपके पास रहने के लिए होते हैं (उदाहरण के लिए पड़ोसियों) या आप के पास रहने के लिए उपयोग किया जाता है (उदाहरण के लिए, कॉलेज रूममेट्स)।

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

Answer 3

एमएसजे के उत्तर के अतिरिक्त।

ग्राफ़ = G(V, E), जहां V शिखर का सेट है और और E कोने की जोड़ी वी से इस Skiena अनुसार ग्राफ की परिभाषा है निर्धारित है। ध्यान दें कि इस ग्राफ को कैसे दिखता है इसका कोई उल्लेख नहीं है (यानी इसकी टोपोलॉजी का कोई उल्लेख नहीं है)।

उदाहरण (ध्यान दें जहां a, b में स्थित हैं कि यह परिभाषित नहीं करता है का कहना है कि पहला, दूसरा समन्वय प्रणाली)

V = { a, b, c, d, e, f } और E = { (a,b), (b,c), (a,e) }

करने के लिए एक ग्राफ आप इसे ज्यामितीय पदों जैसे आवंटित 'आकर्षित' एक्स, वाई समन्वय प्रणाली में।

| 
|   b (2,3) 
| a(1,2) 
| 
| 
|____________________________ 
Fig 1 

चित्र 1 बस एक एम्बेडिंग जहाँ हम शिखर जोड़े में के बीच E

अंतर निर्दिष्ट बना रहे है एम्बेडेड और संस्थानिक ग्राफ कैसे करता है "टोपोलॉजी" होने के लिए आता है। किसी भी "एम्बेडिंग" में आप ऊपर वर्णित अनुसार ज्यामितीय स्थान मैन्युअल रूप से असाइन करते हैं, लेकिन स्थलीय ग्राफ में आप एक "नियम" को परिभाषित करते हैं, जिस पर ग्राफ की टोपोलॉजी स्वयं परिभाषित होती है। जैसे आप G(V,E) निर्दिष्ट करते हैं और एक नियम परिभाषित करते हैं, "प्रत्येक नोड पर बिल्कुल एक बार जाएं" कहें टोपोलॉजी को परिभाषित करता है जिसे "पूर्ण ग्राफ" कहा जाता है।