दो ग्राफों के बीच दूरी संपादित करें

Question

मैं सोच रहा हूं कि, तारों की तरह, जहां हमारे पास दो तारों के बीच लेवेनशेटिन दूरी (या दूरी संपादित करें) है, क्या ग्राफ के लिए कुछ समान है?

मेरा मतलब है, एक स्केलर उपाय जो ग्राफ़ G2 पर ग्राफ G1 को बदलने के लिए परमाणु संचालन (नोड और किनारों सम्मिलन/हटाना) की संख्या को पहचानता है।

Answer 1

नोट:

Levenshtein दूरी (या संपादित दूरी) दो तार

के बीच है लेकिन ग्राफ़ में आप कम से कम एन के बीच खोज करनी चाहिए! स्थिति जो आपको प्रत्येक किनारे और vertex की पहचान मिलती है। आप आसानी से अद्वितीय ग्राफिक्स द्वारा दो ग्राफ के बीच तुलना कर सकते हैं, लेकिन मास्टर प्रश्न प्रत्येक चरम और किनारे के लिए पहचान परिभाषित करता है। यह प्रश्न (प्रत्येक चरम के लिए पहचान ढूंढें और किनारे को दो ग्राफ़ में बदलना चाहिए) बहुत कठिन है और था आइसोमोर्फिज्म समस्या (एनपी-पूर्ण) कहा जाता है। आप आइसोमोर्फिज्म ग्राफ के बारे में खोज सकते हैं।

Answer 2

एक सामान्य ग्राफ के लिए यह एक एनपी-पूर्ण समस्या है क्योंकि दूसरों ने उनके उत्तर में उल्लेख किया है। लेकिन पेड़ के ग्राफ के लिए अच्छी तरह से ज्ञात बहुपद एल्गोरिदम हैं। उनमें से सबसे प्रसिद्ध हो सकता है "झांग शाशा" एल्गोरिदम जो 1 9 8 9 में प्रकाशित हुआ था।

Answer 3

मुझे लगता है कि ग्राफ संपादन दूरी वह उपाय है जिसे आप ढूंढ रहे थे।

ग्राफ़ संपादित दूरी उपायों संचालन ग्राफ संपादित की न्यूनतम संख्या एक से दूसरे ग्राफ बदलने के लिए, और अनुमति के संचालन ग्राफ संपादित में शामिल हैं:

• सम्मिलित करें/एक अलग शिखर
• सम्मिलित हटाना/बढ़त हटाना
• एक शीर्ष/बढ़त के लेबल (यदि लेबल रेखांकन)

बदलें हालांकि, कंप्यूटिंग दो रेखांकन के बीच ग्राफ संपादित दूरी एनपी कठिन है। यह कंप्यूटिंग के लिए सबसे कुशल एल्गोरिदम एक ए *-आधारित एल्गोरिदम है, और अन्य उप-इष्टतम एल्गोरिदम हैं।

Answer 4

आप कागज A survey of graph edit distance