ग्राफ आइसोमोर्फिज्म मुद्दों को संभालने के लिए एक मानक विधि प्रत्येक ग्राफ को एक विशिष्ट स्ट्रिंग प्रतिनिधित्व में मैप करना है जिसे इसका कोड या कैनोनिकल लेबल कहा जाता है। एक कैनोनिकल लेबल में यह गुण होता है कि यदि दो ग्राफ आइसोमोर्फिक हैं, तो उनके कोड समान होने चाहिए।
यह गुण हमें ग्राफ के कैनोनिकल लेबल्स का विश्लेषण करके ग्राफ आइसोमोर्फिज्म का परीक्षण करने में सक्षम बनाता है। ग्राफ के कैनोनिकल लेबल के निर्माण की दिशा में पहला चरण ग्राफ के लिए एक आसन्न मैट्रिक्स विवरण खोजना है। यह दिए गए ग्राफ के लिए इस तरह के मैट्रिक्स का एक उदाहरण दिखाता है।
एक ग्राफ के एक से अधिक आसन्न मैट्रिक्स विवरण हो सकते हैं क्योंकि आसन्न मैट्रिक्स में वर्टिसेज को ऑर्डर करने के कई तरीके हैं। पहली पंक्ति और कॉलम वर्टेक्स a से संबंधित हैं जिसमें 3 एज हैं, दूसरी पंक्ति और कॉलम एक अन्य वर्टेक्स a से संबंधित हैं जिसमें 2 एज हैं, आदि। एक ग्राफ के सभी आसन्न मैट्रिक्स विवरण प्राप्त करने के लिए, मैट्रिक्स की पंक्तियों के सभी संभावित क्रमपरिवर्तनों पर विचार करना आवश्यक है।
उदाहरण - निम्नलिखित मैट्रिक्स पर विचार करें
M = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
निम्नलिखित क्रमपरिवर्तन मैट्रिक्स का उपयोग M की पहली पंक्ति (और कॉलम) को तीसरी पंक्ति के साथ बदलने के लिए किया जा सकता है:
P13 = 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1
जहां P13 आइडेंटिटी मैट्रिक्स की पहली और तीसरी पंक्ति को एक्सचेंज करके प्राप्त किया जाता है। पहली और तीसरी पंक्तियों (और कॉलम) को एक्सचेंज करने के लिए, क्रमपरिवर्तन मैट्रिक्स को M से गुणा किया जाता है:
M′ = P13T X M X P13= 11 10 9 12 7 6 5 8 3 2 1 4 15 14 13 16
दूसरा चरण प्रत्येक आसन्न मैट्रिक्स के लिए स्ट्रिंग विवरण तय करना है। चूंकि आसन्न मैट्रिक्स सममित है, मैट्रिक्स के ऊपरी त्रिकोणीय भाग के आधार पर स्ट्रिंग विवरण उत्पन्न करना कुशल है।
कोड को कॉलमवाइज़ फैशन में ऊपरी त्रिकोणीय मैट्रिक्स की प्रविष्टियों को जोड़कर प्राप्त किया जाता है। अंतिम चरण ग्राफ के सभी स्ट्रिंग विवरणों को सहसंबंधित करना और उसको चुनना है जिसका लेक्सिकोग्राफिक मूल्य सबसे कम (या सबसे अधिक) है।
पिछला दृष्टिकोण महंगा प्रतीत होता है क्योंकि इसने हमें एक ग्राफ के सभी संभावित आसन्न मैट्रिक्स निर्धारित करने और उनके प्रत्येक स्ट्रिंग विवरण का मूल्यांकन करके कैनोनिकल लेबल खोजने की आवश्यकता होती है। इसके अलावा, प्रत्येक ग्राफ के लिए kl क्रमपरिवर्तनों पर विचार किया जाना चाहिए जिसमें k वर्टिसेज शामिल हैं।
इस कार्य की जटिलता को कम करने के लिए विभिन्न विधियाँ विकसित की गई हैं जिनमें पहले से गणना किए गए कैनोनिकल लेबल को कैश करना और वर्टेक्स लेबल और वर्टेक्स की डिग्री जैसे अधिक डेटा को शामिल करके कैनोनिकल लेबल तय करने के लिए आवश्यक क्रमपरिवर्तनों की संख्या को कम करना शामिल है।
