आसन्नता मैट्रिक्स

Question

के बजाय घटना मैट्रिक्स अधिक विस्तृत आसन्नता मैट्रिस के बजाय घटना मैट्रिक्स डेटा संरचनाओं का उपयोग करके हल करने के लिए ग्राफ पर किस तरह की समस्याएं तेज होती हैं (बड़ी-ओ के संदर्भ में)?

Answer 1

संरचनाओं के अंतरिक्ष जटिलताओं हैं:

संलग्नता: हे (वी^2) घटना: हे (VE)

परिणाम यह है कि एक घटना संरचना स्थान की बचत होती है, तो वहाँ कई और अधिक कोने हैं

किनारों की तुलना में।

आप कुछ विशिष्ट ग्राफ आपरेशन के समय जटिलता देख सकते हैं: समायो: अगर दो ओ (VE)

चेक: हे (वी) इंक

सभी कोने एक शीर्ष के निकट का पता लगाएं कोने आसन्न हैं: समायो: हे (1) इंक: हे (ई)

गणना एक शीर्ष के संयोजक: समायो: हे (वी) इंक: हे (ई)

और इसी तरह। किसी दिए गए एल्गोरिदम के लिए, आप ऊपर की तरह बिल्डिंग ब्लॉक का उपयोग करके गणना कर सकते हैं कि कौन सा प्रतिनिधित्व आपको बेहतर समग्र जटिलता देता है।

अंतिम नोट के रूप में, किसी भी प्रकार के मैट्रिक्स का उपयोग करके सभी के लिए बेहद अंतरिक्ष-अक्षम है, लेकिन ग्राफ का सबसे घना है, और मैं तब तक उपयोग करने की सलाह देता हूं जब तक कि आपने जानबूझकर सूचियों जैसे विकल्पों को खारिज कर दिया हो।

Answer 2

मुझे व्यक्तिगत रूप से किसी प्रोग्रामिंग प्रतियोगिता या शोध समस्या में घटना मैट्रिक्स प्रतिनिधित्व का असली एप्लिकेशन नहीं मिला है। मुझे लगता है कि कुछ प्रमेय साबित करने या कुछ विशेष समस्याओं के लिए उपयोगी हो सकता है। एक पुस्तक "स्पैनिंग पेड़ की संख्या को गिनने" का एक उदाहरण देती है जिसमें एक समस्या है जिसमें यह प्रतिनिधित्व उपयोगी है।

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

हालांकि हाइपर-ग्राफ में यह अधिक उपयोगी प्रतीत हो सकता है, लेकिन केवल तभी घना है।

तो मेरी राय है - यह केवल सैद्धांतिक कार्यों के लिए उपयोगी है।