Graph canonization
গ্রাফ তত্ত্বে, গণিতের একটি শাখা, গ্রাফ ক্যানোনাইজেশন হল প্রদত্ত গ্রাফ জি-এর একটি ক্যানোনিকাল ফর্ম খুঁজে বের করার সমস্যা। একটি ক্যানোনিকাল ফর্ম হল একটি লেবেলযুক্ত গ্রাফ ক্যানন (জি) যা জি-এর সমতুল্য, যাতে জি-এর সমতুল্য প্রতিটি গ্রাফের জি-এর মতো একই ক্যানোনিকাল ফর্ম থাকে। সুতরাং, গ্রাফ ক্যানোনাইজেশন সমস্যার সমাধান থেকে, গ্রাফ আইসোমরফিজমের সমস্যাটিও সমাধান করা যেতে পারেঃ দুটি গ্রাফ জি এবং এইচ সমতুল্য কিনা তা পরীক্ষা করার জন্য, তাদের ক্যাননিকাল ফর্ম ক্যানন (জি) এবং ক্যানন (এইচ) গণনা করুন এবং এই দুটি ক্যানোনিকাল ফর্ম অভিন্ন কিনা তা পরীক্ষা করুন। একটি গ্রাফের ক্যানোনিকাল ফর্ম একটি সম্পূর্ণ গ্রাফ অপরিবর্তনীয়ের একটি উদাহরণ-প্রতিটি দুটি আইসোমরফিক গ্রাফের একই ক্যানোনিকাল ফর্ম রয়েছে এবং প্রতিটি দুটি অ-আইসোমরফিক গ্রাফের বিভিন্ন ক্যানোনিকাল ফর্ম রয়েছে। বিপরীতভাবে, গ্রাফের প্রতিটি সম্পূর্ণ অপরিবর্তনীয় একটি প্রামাণিক রূপ তৈরি করতে ব্যবহার করা যেতে পারে। একটি এন-ভার্টেক্স গ্রাফের ভার্টেক্স সেটকে 1 থেকে এন পর্যন্ত পূর্ণসংখ্যার সাথে চিহ্নিত করা যেতে পারে এবং এই ধরনের সনাক্তকরণ ব্যবহার করে একটি গ্রাফের ক্যানোনিকাল রূপকে তার শীর্ষগুলির বিন্যাস হিসাবেও বর্ণনা করা যেতে পারে। গ্রাফের ক্যানোনিকাল রূপগুলিকে ক্যানোনিকাল লেবেলিংও বলা হয় এবং গ্রাফ ক্যানোনাইজেশন কখনও কখনও গ্রাফ ক্যানোনিকালাইজেশন নামেও পরিচিত। গণনামূলক জটিলতা স্পষ্টতই, গ্রাফ ক্যানোনাইজেশন সমস্যাটি অন্তত গ্রাফ আইসোমরফিজম সমস্যার মতোই গণনামূলকভাবে কঠিন। প্রকৃতপক্ষে, গ্রাফ আইসোমরফিজম গ্রাফ ক্যানোনাইজেশনের জন্য এসি0-হ্রাসযোগ্য। যাইহোক, এটি এখনও একটি উন্মুক্ত প্রশ্ন যে দুটি সমস্যা বহুপদী সময়ের সমতুল্য কিনা। যদিও গ্রাফ আইসোমরফিজমের জন্য (নির্ধারণমূলক) বহুপদী অ্যালগরিদমের অস্তিত্ব এখনও গণনামূলক জটিলতা তত্ত্বে একটি উন্মুক্ত সমস্যা, 1977 সালে লাস্লো বাবাই রিপোর্ট করেছিলেন যে কমপক্ষে 1-এক্সপ (-ও (এন)) সম্ভাবনার সাথে, একটি সাধারণ ভার্টেক্স শ্রেণিবিন্যাস অ্যালগরিদম সমস্ত এন-ভার্টেক্স গ্রাফের সেট থেকে এলোমেলোভাবে নির্বাচিত গ্রাফের একটি ক্যানোনিকাল লেবেলিং তৈরি করে মাত্র দুটি পরিমার্জন পদক্ষেপের পরে। ছোট পরিবর্তন এবং একটি অতিরিক্ত গভীরতা-প্রথম অনুসন্ধান পদক্ষেপ রৈখিক প্রত্যাশিত সময়ে এই ধরনের অভিন্নভাবে নির্বাচিত র্যান্ডম গ্রাফগুলির ক্যানোনিকাল লেবেলিং তৈরি করে। এই ফলাফলটি কেন অনেক রিপোর্ট করা গ্রাফ আইসোমরফিজম অ্যালগরিদম অনুশীলনে ভাল আচরণ করে তার উপর কিছুটা আলোকপাত করে। এটি সম্ভাবনাময় জটিলতা তত্ত্বের একটি গুরুত্বপূর্ণ অগ্রগতি ছিল যা তার পাণ্ডুলিপি আকারে ব্যাপকভাবে পরিচিত হয়ে ওঠে এবং যা একটি সিম্পোজিয়ামে রিপোর্ট করার অনেক পরেও একটি "অপ্রকাশিত পাণ্ডুলিপি" হিসাবে উল্লেখ করা হয়েছিল। একটি সাধারণভাবে পরিচিত ক্যানোনিকাল ফর্ম হল আইসোমরফিজম শ্রেণীর মধ্যে লেক্সিকোগ্রাফিকভাবে ক্ষুদ্রতম গ্রাফ, যা একটি রৈখিক স্ট্রিং হিসাবে বিবেচিত লেক্সিকোগ্রাফিকভাবে ক্ষুদ্রতম সংলগ্ন ম্যাট্রিক্স সহ ক্লাসের গ্রাফ। যাইহোক, অভিধানগতভাবে ক্ষুদ্রতম গ্রাফের গণনা এনপি-হার্ড। গাছের জন্য, ও (এন) স্থানের প্রয়োজন একটি সংক্ষিপ্ত বহুপদী ক্যানোনাইজেশন অ্যালগরিদম দ্বারা উপস্থাপিত হয়। প্রতিটি শীর্ষকে স্ট্রিং 01 দিয়ে লেবেল দিয়ে শুরু করুন। প্রতিটি অ-পাতার x-এর জন্য x-এর লেবেল থেকে অগ্রবর্তী 0 এবং পিছনের 1টি সরিয়ে ফেলুন; তারপর সমস্ত সংলগ্ন পাতার লেবেলের সাথে x-এর লেবেলকে অভিধানগত ক্রমে সাজান। এই সাজানো লেবেলগুলিকে একত্রিত করুন, একটি শীর্ষস্থানীয় 0 এবং পিছনের 1 যোগ করুন, এটিকে x এর নতুন লেবেল করুন এবং সংলগ্ন পাতাগুলি মুছে ফেলুন। যদি দুটি শীর্ষ অবশিষ্ট থাকে, তবে তাদের লেবেলগুলি অভিধানগত ক্রমে সংযুক্ত করুন। প্রয়োগ গ্রাফ ক্যানোনাইজেশন হল অনেক গ্রাফ আইসোমরফিজম অ্যালগরিদমের সারমর্ম। নেতৃস্থানীয় সরঞ্জামগুলির মধ্যে একটি হল নওটি। গ্রাফ ক্যানোনাইজেশনের একটি সাধারণ প্রয়োগ গ্রাফিকাল ডেটা মাইনিংয়ে, বিশেষত রাসায়নিক ডাটাবেস অ্যাপ্লিকেশনগুলিতে। রাসায়নিক পদার্থের জন্য বেশ কয়েকটি শনাক্তকারী, যেমন এস. এম. আই. এল. ই. এস এবং আই. এন. সি. আই তাদের গণনায় ক্যানোনিকালাইজেশন পদক্ষেপ ব্যবহার করে, যা মূলত গ্রাফের ক্যানোনিকালাইজেশন যা অণুর প্রতিনিধিত্ব করে। এই শনাক্তকারীগুলি আণবিক তথ্য এনকোড করার জন্য একটি আদর্শ (এবং কখনও কখনও মানব-পাঠযোগ্য) উপায় সরবরাহ করার জন্য এবং ডেটাবেস এবং ওয়েবে এই জাতীয় তথ্য অনুসন্ধানের সুবিধার্থে ডিজাইন করা হয়েছে। তথ্যসূত্র গ্রাফ তত্ত্ব