Graph canonization
ग्राफ सिद्धांत में, गणित की एक शाखा, ग्राफ कैनोनाइजेशन एक दिए गए ग्राफ जी के कैनॉनिकल रूप को खोजने की समस्या है। एक कैनॉनिकल रूप एक लेबल किया गया ग्राफ कैनन (जी) है जो जी के लिए आइसोमोर्फिक है, जैसे कि प्रत्येक ग्राफ जो जी के लिए आइसोमोर्फिक है, उसका जी के समान कैनॉनिकल रूप है। इस प्रकार, ग्राफ कैनोनाइजेशन समस्या के समाधान से, कोई भी ग्राफ आइसोमोर्फिज्म की समस्या को भी हल कर सकता हैः यह परीक्षण करने के लिए कि क्या दो ग्राफ जी और एच आइसोमोर्फिक हैं, उनके कैननिकल रूपों कैनन (जी) और कैनन (एच) की गणना करें, और परीक्षण करें कि क्या ये दो कैनॉनिकल रूप समान हैं। ग्राफ का विहित रूप एक पूर्ण ग्राफ अपरिवर्तनीय का एक उदाहरण हैः प्रत्येक दो समरूपी ग्राफों का एक ही विहित रूप होता है, और प्रत्येक दो गैर-समरूपी ग्राफों के अलग-अलग विहित रूप होते हैं। इसके विपरीत, ग्राफ के प्रत्येक पूर्ण अपरिवर्तनीय का उपयोग एक विहित रूप के निर्माण के लिए किया जा सकता है। एन-वर्टेक्स ग्राफ के शीर्ष समूह को 1 से एन तक के पूर्णांकों के साथ पहचाना जा सकता है, और इस तरह की पहचान का उपयोग करते हुए ग्राफ के एक विहित रूप को इसके शीर्षों के क्रमपरिवर्तन के रूप में भी वर्णित किया जा सकता है। ग्राफ के विहित रूपों को विहित लेबलिंग भी कहा जाता है, और ग्राफ कैनाइज़ेशन को कभी-कभी ग्राफ कैनाइज़ेशन के रूप में भी जाना जाता है। कम्प्यूटेशनल जटिलता स्पष्ट रूप से, ग्राफ कैनाइज़ेशन समस्या कम से कम कम्प्यूटेशनल रूप से उतनी ही कठिन है जितनी कि ग्राफ समरूपता समस्या। वास्तव में, ग्राफ समरूपता ग्राफ कैनाइज़ेशन के लिए भी AC0-कम करने योग्य है। हालाँकि, यह अभी भी एक खुला सवाल है कि क्या दोनों समस्याएं बहुपद समय समकक्ष हैं। जबकि ग्राफ समरूपता के लिए (नियतात्मक) बहुपद एल्गोरिदम का अस्तित्व अभी भी कम्प्यूटेशनल जटिलता सिद्धांत में एक खुली समस्या है, 1977 में लेज़लो बाबई ने बताया कि कम से कम 1-एक्सप (-ओ (एन)) की संभावना के साथ, एक सरल शीर्ष वर्गीकरण एल्गोरिदम केवल दो परिष्करण चरणों के बाद सभी एन-वर्टेक्स ग्राफ के सेट से यादृच्छिक रूप से समान रूप से चुने गए ग्राफ की एक विहित लेबलिंग का उत्पादन करता है। छोटे संशोधन और एक अतिरिक्त गहराई-प्रथम खोज चरण रैखिक अपेक्षित समय में इस तरह के समान रूप से चुने गए यादृच्छिक ग्राफों की विहित लेबलिंग का उत्पादन करते हैं। यह परिणाम इस तथ्य पर कुछ प्रकाश डालता है कि क्यों कई रिपोर्ट किए गए ग्राफ समरूपता एल्गोरिदम व्यवहार में अच्छा व्यवहार करते हैं। यह संभावित जटिलता सिद्धांत में एक महत्वपूर्ण सफलता थी जो अपने पांडुलिपि रूप में व्यापक रूप से जानी जाने लगी और जिसे एक संगोष्ठी में रिपोर्ट किए जाने के लंबे समय बाद भी "अप्रकाशित पांडुलिपि" के रूप में उद्धृत किया गया था। एक सामान्य रूप से ज्ञात कैनॉनिकल रूप समरूपता वर्ग के भीतर लेक्सिकोग्राफिक रूप से सबसे छोटा ग्राफ है, जो एक रैखिक स्ट्रिंग के रूप में माने जाने वाले लेक्सिकोग्राफिक रूप से सबसे छोटे आसन्न मैट्रिक्स के साथ वर्ग का ग्राफ है। हालांकि, शब्दकोश की दृष्टि से सबसे छोटे ग्राफ की गणना एन. पी.-हार्ड है। पेड़ों के लिए, ओ (एन) स्थान की आवश्यकता वाला एक संक्षिप्त बहुपद कैनोनाइजेशन एल्गोरिथ्म प्रस्तुत किया जाता है। प्रत्येक शीर्ष को स्ट्रिंग 01 के साथ लेबल करके शुरू करें। प्रत्येक गैर-पत्ती x के लिए बार-बार x के लेबल से अग्रणी 0 और पीछे 1 को हटा दें; फिर x के लेबल को सभी आसन्न पत्तियों के लेबल के साथ लेक्सिकोग्राफिक क्रम में क्रमबद्ध करें। इन क्रमबद्ध लेबलों को संयोजित करें, एक अग्रणी 0 और पीछे 1 को वापस जोड़ें, इसे x का नया लेबल बनाएं, और आस-पास के पत्तों को हटा दें। यदि दो शीर्ष शेष हैं, तो उनके लेबल को शब्दकोश क्रम में जोड़ दें। अनुप्रयोग ग्राफ कैनोनाइजेशन कई ग्राफ समरूपता एल्गोरिदम का सार है। प्रमुख उपकरणों में से एक नौटी है। ग्राफ कैनाइज़ेशन का एक सामान्य अनुप्रयोग ग्राफिकल डेटा माइनिंग में है, विशेष रूप से रासायनिक डेटाबेस अनुप्रयोगों में। रासायनिक पदार्थों के लिए कई पहचानकर्ता, जैसे कि एस. एम. आई. एल. ई. एस. और आई. एन. सी. एच. आई. अपनी गणना में कैनोनिकलाइजेशन चरणों का उपयोग करते हैं, जो अनिवार्य रूप से ग्राफ का कैनोनिकलाइजेशन है जो अणु का प्रतिनिधित्व करता है। इन पहचानकर्ताओं को आणविक जानकारी को कूटबद्ध करने और डेटाबेस और वेब पर ऐसी जानकारी की खोज को सुविधाजनक बनाने के लिए एक मानक (और कभी-कभी मानव-पठनीय) तरीका प्रदान करने के लिए डिज़ाइन किया गया है। संदर्भ ग्राफ सिद्धांत