গ্রাফ থিওরি (পর্ব ৯)
প্রোগ্রামিং — ১
উপগ্রাফের কথা
একটি গ্রাফ থেকে এক বা একাধিক নোড সরিয়ে দিয়ে নতুন যে গ্রাফ বানানো যায় তাকে আমরা মূল গ্রাফের একটা উপগ্রাফ বলতে পারি। নিচের ছবিটি খেয়াল করলে আরও পরিষ্কার হবে।
এখানে আমরা G নামের একটি গ্রাফ নিয়েছি, এর v₁ নোডটি সরিয়ে নিলে ডানপাশের গ্রাফটি তৈরি হয়। একে আমরা মূল গ্রাফের (G) উপগ্রাফ (subgraph) বলবো। তুমি যে নোডটি সরিয়ে নিবা সেই নোড থেকে যে এজগুলো বের হবে তারাও মুছে যাবে। উপগ্রাফটিকে G — v₁ দ্বারা প্রকাশ করা যায়। এভাবে নোড সরিয়ে দেয়ার মাধ্যমে যে উপগ্রাফ তৈরি হয় তাদেরকে induced subgraph বলে।
আরেকটি উদাহরণ দেয়া যাক,
ছবি ৬৭ এর মূল গ্রাফ (G) থেকে v₁ ও v₅ নোড সরিয়ে নেয়া হয়েছে। সরিয়ে নেয়া নোডগুলো নিয়ে একটি সেট তৈরি করা হলো, নাম দিলাম X। তাহলে, X = {v₁, v₅}। একারণে উপগ্রাফটির নাম দেয়া হয়েছে G — X।
আবার কোন গ্রাফ থেকে এক বা একাধিক এজ সরিয়ে নিয়েও উপগ্রাফ তৈরি করা যায়। এদেরকে বলা হয় spanning। নিচের ছবিটি খেয়াল করি,
ছবি ৬৮ এর মূল গ্রাফ (G) থেকে e₁ এজটি সরিয়ে নিলে আমরা (২) নং গ্রাফটি পাই। একে G\e₁ দ্বারা প্রকাশ করা হয় এবং একে আমরা মূল গ্রাফের একটি spanning বলবো। এবার আমরা যদি আরও একটি এজ (e₂) সরিয়ে নিই তাহলে (৩) নং গ্রাফটি পাই। তাহলে Y = {e₁, e₂} সরিয়ে নিলে আমরা G\Y গ্রাফটি পাচ্ছি। খেয়াল করে দেখো (৩) নং গ্রাফটি হচ্ছে একটি ট্রি। আশা করছি, ট্রি বলতে কি বুঝায় সেটা তোমাদের মনে আছে। না থাকলে পর্ব ৪ পড়ে আসতে পারো।
তাহলে আমরা (৩) নং গ্রাফটিকে বলতে পারি spanning tree। এখানে একটা বিষয় মনে রাখতে হবে যে, induced graph এ যে নোডগুলোকে সরিয়ে ফেলছিলাম তাদের সাথে সংশ্লিষ্ট এজগুলোও মুছে যাচ্ছিল কিন্তু spanning এর ক্ষেত্রে মূল গ্রাফে যতগুলো নোড থাকবে spanning এও ততগুলোই নোড থাকবে।
Introduction to Algorithms (3rd Edition) বইয়ের ২৩নং অধ্যায়ে Minimum Spanning Tree (MST) নিয়ে আলোচনা আছে। Spanning Tree কি জিনিস সেটা নিয়ে আমরা ইতিমধ্যেই কথা বলেছি। এবার MST নিয়ে কথা হবে। নিচের ছবিটি খেয়াল করি,
আমরা ছবি ৬৯ এ একটি undirected weighted গ্রাফ দেখতে পাচ্ছি। তোমাকে যদি ছবি ৬৯ এর গ্রাফের Spanning Tree বের করতে বলা হয়, পারবানা? ছবি ৬৮ এর নিয়ম অবলম্বন করলেই হবে। কিন্তু দেখা যাবে যে, একেক জন একেকটা Spanning Tree বের করছে। আসলে একটি গ্রাফের অনেকগুলো Spanning Tree হতে পারে। কোন গ্রাফের এজসংখ্যা = n, নোডসংখ্যা = m এবং চক্রসংখ্যা (number of cycle) = k হলে, ঐ গ্রাফের Spanning Tree সংখ্যা = ⁿCₘ₋₁ — k
তাহলে ছবি ৬৯ এর গ্রাফের ক্ষেত্রে, এজসংখ্যা, n = 5, নোডসংখ্যা, m = 4 এবং চক্রসংখ্যা k = 2 (নোড ১, ২, ৪ মিলে একটি চক্র এবং নোড ৪, ২, ৩ মিলে আরেকটি চক্র), তাহলে এই গ্রাফের Spanning Tree সংখ্যা = ⁵C₃ — 2 = 8 । আমরা এখন উপরের গ্রাফের ৮টি Spanning Tree এঁকে ফেলবো,
এজগুলোর সাথে যে মান দেয়া (weight) আছে তাদের যোগ করলে ওই spanning tree ঘুরতে কত খরচ (cost) হয় সেটা পাওয়া যায়। যে spanning tree এর ক্ষেত্রে খরচ সবথেকে কম সেটাই হচ্ছে MST। এক্ষেত্রে (৪) নং spanning tree টি হচ্ছে ছবি ৬৯ এর গ্রাফের MST। কিন্তু এভাবে গরু-গাধার মতো সবগুলো spanning tree এঁকে MST বের করা সম্ভব না, তাই আমরা অন্যপথে হাঁটবো।
MST বের করার দুটি বিখ্যাত অ্যালগরিদম আছে। যথাঃ Kruskal’s algorithm ও Prim’s algorithm। এই অ্যালগরিদমগুলো নিয়ে কথা বলার আগে আমরা একটু ইতিহাস চর্চা করবো।
গণিতের রাজপুত্র লিওনার্দ অয়লারের সাথে শুধুমাত্র একটি মানুষের তুলনা হওয়া সম্ভব, তিনি হচ্ছেন পল আরডস (Paul Erdos)। হাঙ্গেরির রাজধানী বুদাপেস্টে অয়লারের মৃত্যুর ১৩০ বছর পর জন্ম নেয়া শারীরিকভাবে ছোটখাটো এই যাযাবর মানুষটি ছিলেন অবিবাহিত। সারাজীবন এক বিশ্ববিদ্যালয় থেকে আরেক বিশ্ববিদ্যালয়ে ঘুরে ঘুরে ক্লাস নিয়েছেন। কখনোই কোন স্থানে বেশিদিন একটানা অবস্থান করেননি। বিশ্ববিদ্যালয়গুলোতে ক্লাস নিয়ে আর গণিতের বিভিন্ন সেমিনারে বক্তৃতা দিয়ে উনার যে আয় হতো তা দিয়েই দিনানিপাত করতেন।
সবসময়ের সঙ্গী হিসেবে সাথে থাকতো একটা স্যুটকেস, তাতে জামা-কাপড়ের মতো প্রয়োজনীয় কিছু জিনিসপত্র থাকতো। সেই স্যুটকেস নিয়েই একেকদিন একেক গণিতবিদের দরজায় গিয়ে কড়া নাড়তেন, বলতেন “আমার মাথা খালি আছে, সমাধানের জন্য সমস্যা দাও।”
সারাজীবনে গণিতের ওপর দেড় হাজার গবেষণাপত্র লিখেছেন, যা আজ পর্যন্ত কেউই ছুঁতে পারেনি। ছিলেন মা-বাবার একমাত্র জীবিত সন্তান। শৈশবেই তার বড় দুই বোন মারা যায়। মা-বাবা দুজনেই ছিলেন গণিতের শিক্ষক। সেখান থেকেই গণিতে হাতেখড়ি হয়ে যায়। ৮৩ বছর বয়সে মৃত্যুর ঘন্টাখানেক আগেও গণিতের ওপর বক্তৃতা দিয়েছেন।
ভদ্রলোকের প্রিয় একটি বাক্য ছিল যে, “Another roof, another proof”। সারাক্ষণ বিভিন্ন বিখ্যাত গাণিতিক সমস্যা নিয়ে মাথা ঘামাতেন, যেগুলো বছরের পর বছর কেউ সমাধান করতে পারেনি। কমপক্ষে ১৫টি বিশ্ববিদ্যালয় উনাকে সম্মানসূচক ডিগ্রিতে ভূষিত করে।
পল আরডস এর হাত ধরে চারজন ব্যক্তি পিএইচডি করেছেন। এদের মধ্যে একজন হচ্ছেন বিখ্যাত Bell Labs এর গবেষক Joseph Bernard Kruskal। এই Kruskal সাহেব MST বের করার জন্য একটি অ্যালগরিদম তৈরি করেন আজ থেকে ৬৪ বছর আগে, যা পরবর্তীতে বেশ খ্যাতি লাভ করে। আমরা এখন সেই অ্যালগরিদমটি কিভাবে কাজ করে সেটা দেখবো।
উদাহরণ হিসেবে যেকোন একটি গ্রাফ নেয়া যাক,
প্রথমে আমরাকে সেই এজটি নিতে হবে যার weight সবচেয়ে কম।
আমাদের উদ্দেশ্য হচ্ছে সবচেয়ে কম খরচে পুরো গ্রাফটি ঘুরে বেড়ানো অর্থাৎ যতগুলো নোড আছে সবগুলোতে ঘুরে আসা।
অবশেষে,
তাহলে kruskal এর অ্যালগরিদমটিকে সংক্ষেপে লিখলে,
সবচেয়ে কম weight বিশিষ্ট এজ নিতে হবে, এরপর যেই এজ কম weight বিশিষ্ট হবে সেটা নিতে হবে। এভাবে নিতে থাকতে হবে, শুধু খেয়াল রাখতে হবে যেন কোন চক্র তৈরি না হয়। কেননা আমরা ট্রি বানাচ্ছি এবং ট্রি তে কোন চক্র থাকেনা। তাহলে ছবি ৭১ এর গ্রাফের MST হচ্ছে,
যে সময়ে Bell Labs এ Kruskal গবেষণা করতেন; ওই সময়ে Robert Clay Prim যিনি আইনস্টাইনের স্মৃতি বিজড়িত Princeton University থেকে গণিতে পিএইচডি করেছেন, তিনিও Kruskal এর সাথে একই জায়গায় গবেষণায় নিয়োজিত ছিলেন। দেখা যাচ্ছে যে উনারা একই সময় একই জায়গায় কাজ করতেন এবং MST বের করার জন্য দুটি আলাদা বিখ্যাত অ্যালগরিদম প্রায় একই সময় আবিষ্কার করেন। তবে এখানে আরেকটি মজার ব্যাপার বলা যায়, আমরা যেটিকে Prim’s algorithm বলছি সেই অ্যালগরিদমটি Prim এর ২৭ বছর আগে Vojtech Jarnik এবং Prim এর ২ বছর পর Edsger Dijkstra আলাদা আলাদাভাবে আবিষ্কার করেন। অর্থাৎ একই অ্যালগরিদম তিনজন মানুষ আলাদা আলাদাভাবে কাউকে না জানিয়ে আবিষ্কার করেছেন। সে কারণে এই অ্যালগরিদমকে অনেক সময় Dijkstra-Jarnik-Prim Algorithm বা DJP algorithm নামেও ডাকা হয়।
যে অ্যালগরিদম নিয়ে এত কথা সেটা কিভাবে কাজ করে, তা নিয়ে এবার আলোচনা করা হবে। আমরা উদাহরণ হিসেবে ছবি ৭১ এর গ্রাফটিই ব্যবহার করবো।
প্রথমে আমরাকে সেই এজটি বেছে নিতে হবে যার weight সবথেকে কম ( Kruskal’s algorithm এর মত)।
এখন পর্যন্ত আমরা দুটি এজ নিয়েছি (১ থেকে ৬ এবং ৬ থেকে ৫)। এই নোডগুলোর (১, ৬, ৫) সাথে যুক্ত সবচেয়ে কম weight বিশিষ্ট এজটি এবার নিতে হবে এবং এভাবেই পুরো পদ্ধতিটি কাজ করবে। এই এজগুলোর সাথে যুক্ত এজগুলোর weight হচ্ছে ২৮ (১ থেকে ২), ২৪ (৫ থেকে ৭) এবং ২২ (৫ থেকে ৪)। তাহলে আমরা নিবো ২২ weight বিশিষ্ট এজটি।
Prim’s algorithm এবং Kruskal’s algorithm এর মধ্যে মূল পার্থক্য আমরা দেখতে পাচ্ছি যে, Kruskal’s algorithm এর ক্ষেত্রে আমরা সবচেয়ে কম weight বিশিষ্ট এজগুলো (যেখানেই থাকুক না কেন) একটার পর একটা নিয়েছি। কিন্তু Prim’s algorithm এর ক্ষেত্রে আমরা শুরু করবো সবচেয়ে কম weight বিশিষ্ট এজ দিয়ে, তবে এরপরের যে এজগুলো (অবশ্যই সবচেয়ে কম weight বিশিষ্ট) নিবো সেগুলো যেন অবশ্যই আগেরগুলোর সাথে কোন না কোনভাবে যুক্ত থাকে।
অবশেষে আমরা যে ফলাফল পেয়েছি তা ছবি ৭৫ এ প্রাপ্ত ফলাফলের অনুরূপ। এখন আলোচ্য অ্যালগরিদম দুটোর প্রোগ্রাম দেখার পালা। কিন্তু Prim’s algorithm এর জন্য Min heap এবং Kruskal’s algorithm এর implementation এর জন্য Union set data structure জানা প্রয়োজন।
আমরা অ্যালগরিদম দুটির প্রোগ্রাম দেখার আগে এই পূর্বশর্তগুলো নিয়ে আলোচনা করবো। এই পর্বে এগুলো নিয়ে আলোচনা করলে অনেক লম্বা হয়ে যাবে, তাই পরের পর্বে আলোচনা করাই ভালো হবে।
মাত্র ২৬ বছর বয়সে লিওনার্দ অয়লার সেন্ট পিটার্সবার্গ অ্যাকাডেমির গণিত বিভাগের প্রধান হিসেবে নিয়োগ পান।
