ক্লিক সমস্যা

কম্পিউটার বিজ্ঞানে, ক্লিক সমস্যাটি গ্রাফের মধ্যে ক্লিকগুলি (শীর্ষ বিন্দুগুলোর উপসেট, একে অপরের সাথে পরিচিত, সম্পূর্ণ সাবগ্রাফ নামেও পরিচিত) খুঁজে বের করার গণনা সংক্রান্ত সমস্যা। কোন ক্লিকগুলিতে এটি নির্ভর করে এবং বিভিন্ন ক্লিক সম্পর্কে কোন তথ্য পাওয়া উচিত তা নির্ভর করে বিভিন্ন সূত্র রয়েছে। ক্লিক সমস্যাগুলির সাধারণ সূত্রগুলির মধ্যে সর্বাধিক ক্লিক (সম্ভাব্য সর্বাধিক সংখ্যক শীর্ষগুলির সাথে একটি ক্লিক) খুঁজে বের করা, ওজনযুক্ত গ্রাফে সর্বাধিক ওজন ক্লিক খুঁজে পাওয়া, সর্বোচ্চ ক্লিকগুলি (যেগুলি বড় করা যাবে না) তালিকাভুক্ত করা এবং সিদ্ধান্তের সমস্যা সমাধান করা একটি গ্রাফে প্রদত্ত আকারের চেয়ে বৃহৎ ক্লিক রয়েছে কিনা তা পরীক্ষা করা।

বাস্তব বিশ্বের সেটিং-এর মধ্যে নিম্নলিখিত ক্লিক সমস্যা উদ্ভূত হয়। একটি সামাজিক নেটওয়ার্ক বিবেচনা করুন, যেখানে গ্রাফের শীর্ষ বিন্দুগুলো লোকেদের প্রতিনিধিত্ব করে এবং গ্রাফের প্রান্তগুলি পারস্পরিক পরিচিতি উপস্থাপন করে। তারপরে একটি ক্লিক এমন লোকেদের একটি উপসেটকে প্রতিনিধিত্ব করে যারা সবাই একে অপরকে জানে, এবং ক্লিকগুলো খোঁজার এলগরিদমগুলো পারস্পরিক বন্ধুদের এই গ্রুপ আবিষ্কার করতে ব্যবহার করা যেতে পারে। সামাজিক নেটওয়ার্কে তার অ্যাপ্লিকেশনগুলির পাশাপাশি, বায়োইনফরম্যাটিক্স, কম্পিউটেশনাল রসায়ন এবং গতি বিভাগে ক্লিক সমস্যাটির অনেকগুলি ব্যবহার রয়েছে।

ক্লিক সমস্যার অধিকাংশ সংস্করণগুলো কঠিন। ক্লিক সিদ্ধান্ত সমস্যা এনপি সম্পূর্ণ (কার্প এর ২১ এনপি সম্পূর্ণ সমস্যা)। সর্বাধিক চক্র খুঁজে পেতে স্থির-পরামিতি intractable এবং আনুমানিক কঠিন উভয় সমস্যা। এবং সর্বোচ্চ ক্লিকগুলো তালিকাভুক্ত করার জন্য সূচকীয় সময়গুলির প্রয়োজন হতে পারে সেখানে সূচকগুলি সর্বোচ্চ অনেক ক্লিকে উপস্থিত রয়েছে। অতএব, ক্লিক সমস্যা সম্পর্কে বেশিরভাগ তত্ত্ব বিশেষ ধরনের গ্রাফ চিহ্নিত করার জন্য নিবেদিত, যা আরো দক্ষ অ্যালগরিদমগুলয়কে সত্য বলে স্বীকার করে, বা গণনার বিভিন্ন মডেলগুলিতে সাধারণ সমস্যাগুলির গণনা সংক্রান্ত অসুবিধাটি প্রতিষ্ঠার জন্য।; .

তথ্যসূত্র

বিষয়শ্রেণী:গ্রাফ তত্ত্বে গণনাগত সমস্যা