বেশ কিছুদিন ডিপি নিয়ে লেখার পর আবার গ্রাফ থিওরিতে ফিরে এলাম। আজকে আমরা একটা সহজ কিন্তু ইন্টারেস্টিং প্রবলেম দেখবো। স্টেবল ম্যারিজ(Stable Marriage) প্রবলেম এক ধরনের বাইপারটাইট ম্যাচিং প্রবলেম,তবে এটা শেখার জন্য অন্য কোনো অ্যালগোরিদম জানার প্রয়োজন নেই। মনে করি n টা ছেলে আর n টা মেয়ে আছে। এখন তাদের মধ্যে বিয়ে দিতে হবে এমন ভাবে যেনো বিয়ে "স্টেবল" হয়। প্রত্যেকের সাথেই প্রত্যেকের বিয়ে দেয়া সম্ভব তবে প্রতিটা ছেলে আর মেয়ের কিছু পছন্দ আছে,প্রত্যেকেই চাইবে তার পছন্দের মানুষকে বিয়ে করতে। যদি ছেলে ৩জনের নাম Tom,Bob,Peter , আর মেয়ে ৩জনের নাম Alice,Mary,Lucy হয় তাহলে ছেলেদের পছন্দের তালিকা হতে পারে...

আগের পর্বগুলো পড়ে থাকলে হয়তো ডেপথ ফার্স্ট সার্চ বা ডিএফএস এতদিনে নিজেই শিখে ফেলেছো। তারপরেও এই টিউটোরিয়ালটি পড়া দরকার কিছু কনসেপ্ট জানতে। বিএফএস এ আমরা গ্রাফটাকে লেভেল বাই লেভেল সার্চ করেছিলাম,নিচের ছবির মতো করে: এবার আমরা কোনো নোড পেলে সাথে সাথে সে নোড থেকে আরো গভীরে চলে যেতে থাকবো,যখন আর গভীরে যাওয়া যাবেনা তখন আবার আগের নোডে ফিরে এসে অন্য আরেক দিকে যেত চেষ্টা করবো,এক নোড কখনো ২বার ভিজিট করবোনা। আমরা নোডের ৩টি রং(কালার) দিবো: সাদা নোড= যে নোড এখনো খুজে পাইনি/ভিজিট করিনি। গ্রে বা ধুসর নোড= যে নোড ভিজিট করেছি কিন্তু নোডটি থেকে যেসব চাইল্ড নোডে যাওয়া যায় ...

(অন্যান্য পর্ব) মনে কর তোমার হাতে কিছু কাজের একটা তালিকা আছে,কাজগুলো অবশ্যই শেষ করতে হবে। কাজগুলো হলো অফিসে যাওয়া,সকালে নাস্তা করা,টিভিতে খেলা দেখা,কিছু ই-মেইলের উত্তর দেয়া ,বন্ধুদের সাথে ডিনার করা ইত্যাদি। কাজগুলো কিন্তু আপনি যেকোনো অর্ডারে করতে পারবেনা,কিছু শর্ত মানতে হবে। যেমন অফিসে যাবার আগে নাস্তা করতে হবে,খেলা দেখার আগে অফিসে যেতে হবে,ডিনারে বসার আগে ইমেইলের উত্তর দিতে হবে। তুমি শর্তগুলোর তালিকা করে ফেললে: ১. সকালের নাস্তা ---> অফিস (ক--->খ এর মানে হলো 'খ' কাজটি করার আগে 'ক' কাজটি করতে হবে) ২. সুট-টাই পড়া ----> অফিস ৩. অফিস ----> ইমেইল ৪. অফিস ----> ডিনার ...

(অন্যান্য পোস্ট) আগের পোস্টে আমরা প্রিমস অ্যালগোরিদম ব্যবহার করে mst নির্ণয় করা দেখেছি। mst কাকে বলে সেটাও আগের পোস্টে বলা হয়েছে। এ পোস্টে আমরা দেখবো mst বের করার আরেকটি অ্যালগোরিদম যা ক্রুসকালের অ্যালগোরিদম নামে পরিচিত। এটি mst বের করার সবথেকে সহজ অ্যালগোরিদম। তবে তোমাকে অবশ্যই ডিসজয়েন্ট সেট ডাটা স্ট্রাকচার সম্পর্কে জানতে হবে,না জানলে এই পোস্টটি অবশ্যই দেখে আসো। এই পোস্টে নিজের আকা ছবি ব্যবহার করবোনা। উইকিতে ক্রুসকাল নিয়ে খুব সুন্দর করে লেখা আছে,আমি ওখানকার ছবিগুলোই ব্যবহার করে সংক্ষেপে অ্যালগোরিদমটা বুঝানোর চেষ্টা করবো। নিচের গ্রাফটি দেখো: প্রথমে আমাদের ট্রিত...

(সিরিজের অন্যান্য পোস্ট) একটি গ্রাফ থেকে কয়েকটি নোড আর এজ নিয়ে নতুন একটি গ্রাফ তৈরি করা হলে সেটাকে বলা হয় সাবগ্রাফ। স্প্যানিং ট্রি হলো এমন একটি সাবগ্রাফ যেটায়: * মূল গ্রাফের সবগুলো নোড আছে। * সাবগ্রাফটি একটি ট্রি। ট্রিতে কখনো সাইকেল থাকেনা,এজ থাকে $n-1$ টি যেখানে $n$ হলো নোড সংখ্যা। একটি গ্রাফের অনেকগুলো স্প্যানিং ট্রি থাকতে পারে,যে ট্রি এর এজ গুলোর কস্ট/ওয়েট এর যোগফল সব থেকে কম সেটাই মিনিমাম স্প্যানিং ট্রি। আমরা এই লেখায় প্রিম অ্যালগোরিদমের সাহায্যে মিনিমাম স্প্যানিং ট্রি বের করা শিখবো। মনে করি নিচের গ্রাফের প্রতিটি নোড হলো একটি করে বাড়ি। আমাদের বাড়িগুলোর মধ্যে টেলিফে...

ট্রাভেলিং সেলসম্যান মূলত একটি NP-complete ক্লাসিকাল প্রবলেম। uva 10702 মূল প্রবলেমের পরিবর্তিত রূপ যা ডাইনামিক প্রোগ্রামিং এর মাধ্যমে সমাধান করা সম্ভব। একজন ফেরিওয়ালা এক শহর থেকে অন্য শহরে ঘুরে জিনিসপত্র বিক্রি করে। সে কোনো শহরে একাধিক বার যেতে পারে(ক্লাসিক tsp প্রবলেমে একটি নোড একবারের বেশি ভিজিট করা যায়না)। একটি শহর থেকে আরেকটি শহরে গেলে নির্দিষ্ট পরিমাণ লাভ হয়। ফেরিওয়ালা নির্দিষ্ট কিছু শহরে তার যাত্রা শেষ করে এবং যাত্রা শেষ করার আগে নির্দিষ্ট সংখ্যক বার বিভিন্ন শহরে ভ্রমণ করে(inter-city travel)। বলতে হবে সে সর্বোচ্চ কত লাভ করতে পারবে। এই প্রবলেমে গ্রাফটি complete,সব শহর থেকে সব শহরে যা...