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