গ্রাফ আইসোমরফিজম সমস্যা হ্যান্ডল করার একটি স্ট্যান্ডার্ড পদ্ধতি হলো প্রতিটি গ্রাফকে একটি নির্দিষ্ট স্ট্রিং রিপ্রেজেন্টেশনে ম্যাপ করা যাকে এর কোড বা ক্যানোনিক্যাল লেবেল বলা হয়। একটি ক্যানোনিক্যাল লেবেলের প্রপার্টি হলো যদি দুটি গ্রাফ আইসোমরফিক হয়, তবে তাদের কোডগুলো সমান হবে।
এই প্রপার্টি আমাদের গ্রাফ আইসোমরফিজম টেস্ট করতে সক্ষম করে গ্রাফগুলোর ক্যানোনিক্যাল লেবেল বিশ্লেষণ করে। একটি গ্রাফের ক্যানোনিক্যাল লেবেল তৈরি করার প্রথম ধাপ হলো গ্রাফের জন্য একটি এডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন খুঁজে বের করা। প্রদত্ত গ্রাফের জন্য এমন একটি ম্যাট্রিক্সের উদাহরণ দেখানো হয়েছে।
এক গ্রাফের একাধিক এডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন হতে পারে কারণ এডজেসেন্সি ম্যাট্রিক্সে ভার্টেক্স অর্ডার করার একাধিক পদ্ধতি আছে। প্রথম রো এবং কলম ভার্টেক্স a-র সাথে মিলে যেটির ৩টি এজ, দ্বিতীয় রো এবং কলম অন্য একটি ভার্টেক্স a-র সাথে মিলে যেটির ২টি এজ, ইত্যাদি। একটি গ্রাফের সব এডজেসেন্সি ম্যাট্রিক্স রিপ্রেজেন্টেশন বের করতে, ম্যাট্রিক্সের রোের সব সম্ভাব পারমুটেশন বিবেচনা করতে হয়।
উদাহরণ
নিচের ম্যাট্রিক্স বিবেচনা করুন:
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
দ্বিতীয় ধাপ হলো প্রতিটি এডজেসেন্সি ম্যাট্রিক্সের জন্য স্ট্রিং রিপ্রেজেন্টেশন নির্ধারণ করা। যেহেতু এডজেসেন্সি ম্যাট্রিক্স সিমেট্রিক, এর আপার ট্রায়্যাঙ্গুলার অংশের ওপর ভিত্তি করে স্ট্রিং রিপ্রেজেন্টেশন জেনারেট করা দক্ষ। কোডটি আপার ট্রায়্যাঙ্গুলার ম্যাট্রিক্সের এন্ট্রিগুলো কলামওয়াইজ কনক্যাটেনেট করে প্রাপ্ত করা হয়। শেষ ধাপ হলো গ্রাফের সব স্ট্রিং রিপ্রেজেন্টেশন তুলনা করে সেটি বেছে নেওয়া যেটির লেক্সিকোগ্রাফিক ভ্যালু সবচেয়ে কম (বা বেশি)।
পূর্বের পদ্ধতি ব্যয়বহুল দেখায় কারণ এতে একটি গ্রাফের সব সম্ভাব্য এডজেসেন্সি ম্যাট্রিক্স নির্ধারণ এবং তাদের স্ট্রিং রিপ্রেজেন্টেশন ইভ্যালুয়েট করে ক্যানোনিক্যাল লেবেল খুঁজে বের করতে হয়। উপরন্তু, k ভার্টেক্স বিশিষ্ট প্রতিটি গ্রাফের জন্য k! পারমুটেশন বিবেচনা করতে হয়।
এই টাস্কের কমপ্লেক্সিটি কমাতে বিভিন্ন পদ্ধতি উন্নত করা হয়েছে যেন ক্যাশে করা হয় পূর্বে কম্পিউট করা ক্যানোনিক্যাল লেবেল এবং পারমুটেশনের সংখ্যা কমানো যায় ভার্টেক্স লেবেল এবং ভার্টেক্স ডিগ্রি এর মতো আরও তথ্য ইনকর্পোরেট করে।
