গ্রাফ থিওরি

গ্রাফ থিওরি: স্টেবল ম্যারেজ প্রবলেম

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

গ্রাফ থিওরিতে হাতেখড়ি ৮: ডেপথ ফার্স্ট সার্চ এবং আবারো টপোলোজিকাল সর্ট

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

গ্রাফ থিওরিতে হাতেখড়ি ৭:টপোলোজিকাল সর্ট

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

গ্রাফ থিওরিতে হাতেখড়ি ৬: মিনিমাম স্প্যানিং ট্রি(ক্রুসকাল অ্যালগোরিদম)

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

গ্রাফ থিওরিতে হাতেখড়ি ৫: মিনিমাম স্প্যানিং ট্রি(প্রিম অ্যালগোরিদম)

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

ইউভিএ ১০৭০২(ট্রাভেলিং সেলসম্যান)

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

গ্রাফ থিওরিতে হাতেখড়ি – ৩ (ভ্যারিয়েবলে গ্রাফ স্টোর-২)

আগের পর্ব সবগুলো পর্ব এই পর্বে গ্রাফ স্টোর করার ২য় পদ্ধতি অ্যাডজেসেন্সি লিস্ট নিয়ে লিখব। এ পদ্ধতিতে গ্রাফ স্টোর করে কম মেমরি ব্যবহার করে আরো efficient কোড লেখা যায়। এ ক্ষেত্রে আমরা ডায়নামিক্যালি মেমরি অ্যালোকেট করব,ভয়ের কিছু নেই সি++ এর standard template library(STL) ব্যবহার করে খুব সহজে কাজটা করা যায়। আগের লেখার শেষের দিকে STL এর উপর কয়েকটি টিউটোরিয়ালের লিংক দিয়েছি, আশা করছি ভেক্টর কিভাবে কাজ করে এখন তুমি জানো। অ্যাডজেসেন্সি লিস্ট শুনতে যতটা ভয়ংকর শুনায়,ব্যাপারটি আসলে তেমনই সহজ। আমরা আবার আগের পোস্টের ছবিটিতে ফিরে যাই: এবার বাজার করার লিস্টের মত একটি লিস্ট বানাই: ...
Read More

গ্রাফ থিওরিতে হাতেখড়ি – ২ (ভ্যারিয়েবলে গ্রাফ স্টোর-১)

আগের পোস্টে আমরা দেখেছি গ্রাফ থিওরি কি কাজে লাগে,আর এলিমেন্টারি কিছু টার্ম শিখেছি। এখন আমরা আরেকটু ভিতরে প্রবেশ করবো। প্রথমেই আমাদের জানা দরকার একটা গ্রাফ কিভাবে ইনপুট নিয়ে স্টোর করে রাখা যায়। অনেকগুলো পদ্ধতির মধ্যে দুটি  খুব কমন: ১. অ্যাডজেসেন্সি ম্যাট্রিক্স(adjacency matrix) ২. অ্যাডজেসেন্সি লিস্ট(adjacency list) অ্যাডজেসেন্ট(adjacent) শব্দটার অর্থ "কোন কিছুর পাশে"। যেমন তোমার পাশের বাড়ির প্রতিবেশিরা  তোমার অ্যাডজেসেন্ট। গ্রাফের ভাষায় এক নোডের সাথে আরেকটা নোডে যাওয়া গেলে ২য় নোডটি প্রথমটির অ্যাডজেসেন্ট। এই পোস্টে আমরা ম্যাট্রিক্সের সাহায্যে কোন নোড কার অ্যাডজেসেন্ট অ...
Read More

গ্রাফ থিওরিতে হাতেখড়ি – ১

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