Degree-constrained spanning tree
গ্রাফ তত্ত্বে, একটি ডিগ্রি-সীমাবদ্ধ স্প্যানিং ট্রি হল একটি স্প্যানিং ট্রি যেখানে সর্বাধিক শীর্ষ ডিগ্রি একটি নির্দিষ্ট ধ্রুবক k-এর মধ্যে সীমাবদ্ধ থাকে। ডিগ্রি-সীমাবদ্ধ স্প্যানিং ট্রি সমস্যাটি নির্ধারণ করা হয় যে কোনও নির্দিষ্ট গ্রাফের একটি নির্দিষ্ট k-এর জন্য এমন একটি স্প্যানিং ট্রি আছে কিনা। আনুষ্ঠানিক সংজ্ঞা ইনপুটঃ এন-নোড অনির্দিষ্ট গ্রাফ জি (ভি, ই); ধনাত্মক পূর্ণসংখ্যা কে <এন। প্রশ্নঃ জি-এর কি একটি স্প্যানিং ট্রি রয়েছে যেখানে কোনও নোডের ডিগ্রি কে-এর চেয়ে বেশি নয়? এনপি-সম্পূর্ণতা এই সমস্যাটি এনপি-সম্পূর্ণ। হ্যামিল্টনিয়ান পথ সমস্যা থেকে হ্রাসের মাধ্যমে এটি দেখানো যেতে পারে। এটি এন. পি-সম্পূর্ণ থাকে, এমনকি যদি কে-এর মান 2-এ স্থির করা থাকে। যদি সমস্যাটিকে সংজ্ঞায়িত করা হয় যে ডিগ্রি অবশ্যই ≤ k হতে হবে, তবে ডিগ্রি-সীমাবদ্ধ স্প্যানিং ট্রি-র k = 2 কেস হ্যামিল্টনিয়ান পাথ সমস্যা। ডিগ্রি-সীমাবদ্ধ ন্যূনতম স্প্যানিং ট্রি একটি ওজনযুক্ত গ্রাফের উপর, একটি ডিগ্রি-সীমাবদ্ধ ন্যূনতম স্প্যানিং ট্রি (ডিসিএমএসটি) একটি ডিগ্রি-সীমাবদ্ধ স্প্যানিং ট্রি যেখানে তার প্রান্তের যোগফলের সর্বনিম্ন সম্ভাব্য যোগফল থাকে। ডিসিএমএসটি খুঁজে পাওয়া একটি এনপি-হার্ড সমস্যা। জেনেটিক এবং অ্যান্ট-ভিত্তিক অ্যালগরিদম সহ বহুপদী সময়ে সমস্যা সমাধান করতে পারে এমন অনুসন্ধানমূলক অ্যালগরিদম প্রস্তাব করা হয়েছে। আনুমানিক অ্যালগরিদম একটি পুনরাবৃত্তিমূলক বহুপদী সময় অ্যালগরিদম দেয় যা একটি গ্রাফ দেওয়া হলে, সর্বাধিক ডিগ্রি সহ একটি স্প্যানিং ট্রি প্রদান করে, যেখানে সমস্ত স্প্যানিং ট্রিগুলির উপর সর্বনিম্ন সম্ভাব্য সর্বাধিক ডিগ্রি। সুতরাং, যদি, এই ধরনের একটি অ্যালগরিদম হয় সর্বোচ্চ মাত্রার একটি স্প্যানিং ট্রি ফিরিয়ে দেবে। রেফারেন্স বিস্তৃত গাছ এন. পি-সম্পূর্ণ সমস্যা