মডিউল ১১_৩ঃ Minimum Spanning Tree কি ?

Minimum Spanning Tree কি

Minimum Spanning Tree হলো এমন একটি spanning tree যেখানে edge গুলোর যোগফল যতটুকু সম্ভব সর্বনিম্ন হয়।

এখন Minimum Spanning Tree আমরা একটি উদাহরণের মাধ্যমে বুঝে ফেলি।

ধরুন আপনি একটি wifi business করবেন, এখন আপনার একটি অফিস আছে, সেইখানে থেকে আপনি গ্রাহকদের wifi সংযোগ দিবেন। আপনার কাছে ৫ জন গ্রাহক আছে। নিচের চিত্রে দেখুন , office থেকে A গ্রাহকের কাছে লাইন যেতে 5K( 5 হাজার টাকা ) cost লাগবে। একই ভাবে, office->B তে 8K , office->C তে 8K, B->C তে 7K, office->C তে 3K, office->D তে 15K, office->E তে 7K, E->D তে 10K cost লাগবে। এখন আপনার থেকে এমন way choose করতে হবে, যেইটি দিয়ে লাইন সংযোগ করলে আপনার cost সব থেকে কম হবে।

আপনি দেখুন, লাইনটি office->A->B তে যেতে cost লাগবে 5K + 7K = 12K, আবার office->B->A তে যেতে cost লাগবে 8K + 7K = 15K, তাহলে আপনি অবশ্যই office->A->B way টি choose করবেন কারণ এতে cost কম হচ্ছে।

এরপর দেখুন, office->D তে যেতে cost 15K, আবার দেখুন office->E->D তে যেতে cost 7K + 10K = 17K এইখানে office->E->D তে cost বেশি কিন্তু আপনি যেহেতু office->E->D দিয়ে D গ্রাহককে সংযোগ দিতে পারতেছেন সেইখানে cost 17K আসলেও আপনার জন্য ভালো কারণ, আপনি যদি শুধু office->D cost 15K এবং office->E cost 7K দেন , এইভাবে আলাদা আলাদা সংযোগ দেয়াতে আপনার cost 15K+7K = 22K হচ্ছে, এখন যদি আপনি office->E->D এই way তে E এবং D তে সংযোগ দেন তাহলে আপনার cost আসতেছে 7K + 10K = 17K। তাই আপনি অবশ্যই office->E->D এই way টি choose করবেন।

শেষে office->C তে যেতে cost 3K, আর অন্য কোন way দিয়ে office থেকে C গ্রাহকে লাইন দেয়া সম্ভব নয়। তাই office->C way টি choose করতেই হবে।

এইভাবে দেখুন, আপনি cost কমিয়ে wifi business শুরু করতে পারলেন। এই যে cost কমালেন সেইটি minimum spanning tree এর কারণে কমাতে পারলেন। আর এইটিকে tree বলা হচ্ছে কারণে minimum spannig tree বানানোর পর সেইখানে কোন multiple edge থাকবে নাহ, কোন cycle থাকবে, সেইটি tree এর মত বৈশিষ্ট্যপূর্ণ হবে।