গ্রাফ থিওরি (পর্ব ১)
প্রোগ্রামিং — ১
কালিনিনগ্রাদের প্রেগেল নদী
কালিনিনগ্রাদ নামটা আমার প্রথম নজরে আসে এবছর রাশিয়ায় ফুটবল বিশ্বকাপ অনুষ্ঠিত হওয়ার সময়। বিশ্বকাপ শুরু হওয়ার আগ দিয়ে ফিক্সচার জোগাড় করা নিয়ে সবার বেশ ব্যস্ততা থাকে, আমারও ছিল। এক ওষুধ কোম্পানির বেশ সুন্দর একখানা ফিক্সচার পেয়েও গেলাম, সেটা বাড়িতে টিভিরুমের দেয়ালে টানিয়ে দিয়ে কবে, কোথায়, কোন্ ম্যাচ হবে দেখতে লাগলাম। সেই সময় এই কালিনিনগ্রাদ নামটা প্রথমবার চোখে পড়লো। “রাশিয়া ২০১৮ ফিফা ফুটবল বিশ্বকাপ” উপলক্ষ্যে এখানে একটা সুন্দর স্টেডিয়াম বানানো হয়। “ক্রোয়েশিয়া বনাম নাইজেরিয়া” খেলা দিয়ে এই নতুন স্টেডিয়ামের বিশ্বকাপ যাত্রা শুরু হয়েছিল।
এবার আসি কেন এই নাম নিয়ে এত কথা বলছি সেটার আলোচনায়। এই কালিনিনগ্রাদ শহরের আগে নাম ছিল কনিগসবার্গ। ১২৫৫ সালে কনিগসবার্গ শহর প্রতিষ্ঠিত হয়। ১৯৪৫ সালে দ্বিতীয় বিশ্বযুদ্ধের সময় এই শহরে বেশ তান্ডব চলে। ১৯৪৬ সালে এই শহরটা জার্মানির দখল থেকে রাশিয়ার অন্তর্ভূক্ত হয়ে যায়। এই সময়ই এর নাম পাল্টে কালিনিনগ্রাদ করা হয়।
যাই হোক এইসব ইতিহাসের কথাবার্তা আজকের আলোচনার বিষয় নয়। আমরা বরং আমাদের নির্ধারিত আলোচনার দিকেই আগাই। অন্য কোনদিন সময়-সুযোগ পেলে হয়তো ইতিহাস নিয়ে গল্প করা যাবে। এই শহরে একটা নদী আছে যার নাম প্রেগেল। নদীটা এই শহরকে বেশ কয়েকটা ভাগ করে প্রবাহিত হয়েছে। নিচের ছবিটা খেয়াল করলে একটা ধারণা পাওয়া যাবে।
নদীটা এমনভাবে কনিগসবার্গ শহরের মধ্য দিয়ে গেছে যে শহরের মধ্যেই দ্বীপ তৈরি হয়ে গেছে। ছবিতে দেখা যাচ্ছে শহরের বিভিন্ন অংশে যাওয়ার জন্য নদীর ওপর সাতটা ব্রীজ (লাল রং এর দাগগুলো) আছে। তোমাকে যদি প্রশ্ন করা হয় যে, “তুমি কি প্রতিটা ব্রীজ শুধুমাত্র একবার ব্যবহার করে পুরো শহরটা (দ্বীপগুলোসহ) ঘুরে আসতে পারবে?” প্রশ্নটা এমনিতে খুব সাধারণ মনে হলেও এটা মোটেও কোন সাধারণ প্রশ্ন না। ১৭৩৬ সালে এই প্রশ্নের উত্তর দিতে গিয়ে গণিতের একটা পুরোদস্তুর শাখাই তৈরি করে ফেলেন লিওনার্দ অয়লার (Leonhard Euler)। এই ভদ্রলোককে তুমি চোখ বন্ধ করে সর্বকালের সর্বসেরা গণিতবিদ বলে দিতে পারো। ইনার কথা বলতে শুরু করলে শেষ হবার না, তাই আপাতত ঝুঁকি নিলাম না। আচ্ছা তো যা বলছিলাম, অয়লার সাহেব যে শাখা তৈরি করে ফেলেন উপরের প্রশ্নের উত্তর দিতে গিয়ে, সেই শাখার নাম হচ্ছে ‘গ্রাফ থিওরি’।
আমাদের এই সিরিজের উদ্দেশ্য হচ্ছে গ্রাফ থিওরি সম্পর্কে মোটামুটি ধারণা তৈরি করা। প্রথম কয়েক পর্বে আমরা শুধু গ্রাফ থিওরি বোঝার চেষ্টা করবো, মোটেও কোড টোডের দিকে যাবোনা। তারমানে প্রথমদিকে প্রোগ্রামিং থাকবেনা বললেই চলে। যখন আমাদের গ্রাফ থিওরি সম্পর্কে কিছুটা অনুভূতি কাজ করা শুরু করবে তারপর গেলাম কোডিং ফোডিং এর দিকে, কেমন?
আর একটা তথ্য দিয়ে ভূমিকা শেষ করে পড়ালেখায় মন দিবো আমরা। সেটা হচ্ছে যে, অয়লারের সময় যে সাতটা ব্রীজ ছিল তার মধ্যে দুইটি ব্রীজ দ্বিতীয় বিশ্বযুদ্ধের সময় বোমা বিস্ফোরণের কারণে ধ্বংসপ্রাপ্ত হয় (উপরের ছবির ২ ও ৪ নং ব্রীজ), আরও দুইটি ব্রীজ পরবর্তীতে ভেঙ্গে ফেলে আধুনিক হাইওয়ে (উপরের ছবির ১ ও ৩ নং) বানানো হয়েছে, আর একটা ব্রীজ ১৯৩৫ সালে নতুন করে বানানো হয়। তারমানে দাঁড়ায় যে, অয়লারের সময়কার দুটি ব্রীজ এখন আছে।
এখন আমরা উপরের প্রশ্নটার উত্তর খোঁজার কাজ করতে পারি। এখানে বলে রাখা ভালো যে, যেখান থেকে আমরা যাত্রা শুরু করবো সেখানেই যে যাত্রা শেষ করতে হবে এমন কোন কথা নেই। পুরো শহর ঘুরতে হবে প্রতিটা ব্রীজ শুধুমাত্র একবার ব্যবহার করে, এটাই কাজ।
ধরি, আমরা শহরের A অংশে এখন আছি। তারমানে আমাদের A অংশ ঘুরাঘুরি করা হয়ে গেছে। এবার আমরা ২ নং ব্রীজ দিয়ে নিপফ দ্বীপে চলে আসলাম। এখন পর্যন্ত আমরা A অংশ আর নিপফ দ্বীপ ঘুরে ফেলেছি আর ২ নং ব্রীজ ব্যবহার করে ফেলেছি। এরপর ধরো আমরা ৫ নং ব্রীজ দিয়ে লোমসে দ্বীপে এসে একটু চা-পানি খেয়ে নিলাম। তাহলে আপডেট হচ্ছে A অংশ, নিপফ দ্বীপ ও লোমসে দ্বীপ দেখা শেষ আর ২ ও ৫ নং ব্রীজ ব্যবহার করা হয়ে গেছে। এবার হয়তো আমরা ৭ নং ব্রীজ ধরে B অংশে এসে ৪ নং ব্রীজ দিয়ে নিপফ দ্বীপ হয়ে ১ নং ব্রীজ দিয়ে আবার A অংশে চলে আসলাম। তাহলে সর্বশেষ আপডেট হচ্ছে, শহরের সবগুলো অংশ ঘুরাঘুরি শেষ এবং ২, ৫, ৭, ৪, ১ নং ব্রীজগুলো ব্যবহার করা শেষ। সবশেষে আমরা ৬ নং ব্রীজ ব্যবহার করে আবার লোমসে দ্বীপে এসে আমাদের যাত্রা শেষ করতে পারি। তাহলে ৬ নং ব্রীজটাও ব্যবহার করা হয়ে গেলো। কিন্তু এখানে এসে আমি আর কোনদিকে যেতে পারছিনা কারণ ৫ ও ৭ নং ব্রীজ আমার ব্যবহার করা হয়ে গেছে আগেই। এভাবে আমরা পুরো ভ্রমণটা ৩ নং ব্রীজ ব্যবহার না করেই শেষ করে ফেললাম। তুমি অন্যভাবেও ভ্রমণ করে দেখতে পারো, কিন্তু তুমি কখনোই সবগুলো ব্রীজ ব্যবহার করতে পারবেনা। লিওনার্দ অয়লারও তাই বলেছেন যে, সবগুলো ব্রীজ মাত্র একবার ব্যবহার করে পুরো শহর ভ্রমণ করা যাবেনা।
এখন তোমার মনে হতে পারে যে, ব্যাপারটা তো বেশ সহজই। তাহলে পুরো একটা গণিতের শাখার কি দরকার? আচ্ছা আমি যদি তোমাকে এখন এর চাইতেও বড় সমস্যা দেই, যেমন ধরো একটা দেশের মানচিত্র দিয়ে জিজ্ঞেস করলাম সবগুলো রাস্তা একবার ব্যবহার করে পুরো দেশ ঘুরতে পারবে? তখন কিন্তু তোমার হিসাব করতে জীবন শেষ হয়ে যাবে।
ঠিক এই জায়গাটাতেই অয়লার সাহেবের কীর্তি। তিনি এমন কিছু সূত্র বা কথাবার্তা বলে গেছেন যা আমরা ব্যবহার করে কম পরিশ্রমে বড় বড় সমস্যা সমাধান করে ফেলতে পারি। তোমরা সবাই কমবেশি গুগল ম্যাপ বা অন্য কোন কোম্পানির ম্যাপ সার্ভিস ব্যবহার করেছো। এই ধরনের ‘অ্যাপ’ গুলো তৈরি করতে গ্রাফ থিওরি ব্যাপকভাবে ব্যবহৃত হয়েছে।
এখন আমরা দেখবো যে, অয়লার কিভাবে এই সমস্যাটার সমাধান করেছিলেন। প্রথম কথা হচ্ছে যে, এই সমস্যাটা জ্যামিতি দিয়ে সমাধান করা যাবেনা। কারণ শহরের কোন্ অংশ অন্য অংশের সাথে কত ডিগ্রি কোণে অবস্থান করছে এরকম কোন ব্যাপার এই সমস্যা সমাধানের ক্ষেত্রে গুরুত্বপূর্ণ নয়। তাই আমরা বলতে পারি যে, এটা কোন জ্যামিতিক সমস্যা নয়। যেহেতু তৎকালীন কোন গণিতের শাখার সাথে এই সমস্যার সমাধানকে সম্পর্কযুক্ত করা যাচ্ছিল না, তাই অয়লার সাহেব নতুন শাখার গোড়াপত্তন করলেন।
তিনি বুঝতে পারলেন যে, শহরগুলোর বিভিন্ন অংশের সাথে অন্য অংশের সম্পর্কটাই হচ্ছে এই সমস্যার মূল ব্যাপার। এক্ষেত্রে সম্পর্কগুলো স্থাপন করেছে ব্রীজগুলো। তিনি ছবি ১ কে নিচের ছবির মতো করে রূপান্তরিত করে ফেললেন।
আচ্ছা এই ছবিতে আমরা কি করেছি সেটা আগে বলে ফেলি। ছবি ১ এ A ও B বলতে যা বুঝানো হয়েছে এখানেও তাই। ছবি ১ এর নিপফ দ্বীপ ও লোমসে দ্বীপকে ছবি ২ এ যথাক্রমে C ও D দ্বারা আমরা চিহ্নিত করেছি। আর লাল দাগগুলো ব্রীজকে নির্দেশ করছে এটা বুঝতে আশা করি কারও সমস্যা নাই। এবার তোমরা ছবি ১ ও ছবি ২ কে তুলনা করলে দেখবে যে, আসলে দুটো ছবি একই। তোমাদেরকে অনেক অভিনন্দন কারণ তোমরা ইতিমধ্যেই ছবি ২ এ একটি গ্রাফ দেখতে পাচ্ছো। আমাদের প্রথম গ্রাফ।
আমরা যে গোল গোলগুলো দিয়ে ছবি ২ এ শহরের বিভিন্ন অংশ বুঝিয়েছি তাদেরকে গ্রাফ থিওরির ভাষায় বলা হয় নোড (Node) বা ভার্টেক্স (Vertex)। আর যে লাল দাগুলোগ দিয়ে ব্রীজ বুঝিয়েছি তাদেরকে গ্রাফ থিওরির ভাষায় বলা হয় এজ (Edge)। তাহলে মোদ্দা কথা দাঁড়ালো যে, নোড হচ্ছে সেইসব জিনিসপত্র যাদের মধ্যে অন্য কারও আদৌ সম্পর্ক আছে কিনা সেটা আমরা এজ দিয়ে প্রকাশ করি। যেমন ছবি ২ থেকে বলা যায় যে, শহরের B অংশের সাথে A অংশের সরাসরি কোন এজ নাই মানে এদের মধ্যে সরাসরি কোন সম্পর্ক নাই।
এখন আমরা দেখবো যে, অয়লার সাহেব কিভাবে একদম আমাদের মুখের ওপর বলে দিলেন যে সবগুলো ব্রীজ একবার ব্যবহার করে পুরো শহর ঘুরে আসা যাবেনা। আমরা ছবি ২ হতে ৫ নং এজটা (edge) সরিয়ে ফেলে নতুন করে চেষ্টা করবো যেন সবগুলো ব্রীজ একবার ব্যবহার করে পুরো শহর ঘুরে আসা যায়। তোমরা এখন আমাকে জিজ্ঞেস করতে পারো, কেন আমরা এরকম করবো? আমি বলবো, আরে করেই দেখিনা কি হয়!! উত্তরটা নাহয় পরেই দেয়া গেলো।
আচ্ছা তাহলে নিচের ছবি ৩ কে একটু খেয়াল করো, আমরা যাত্রা শুরু করলাম B থেকে। B থেকে ৩ নং ব্রীজ ব্যবহার করে C তে আসলাম। এবার C থেকে ১ নং ব্রীজ ব্যবহার করে A তে আসলাম। আপডেট হচ্ছে B, C, A ঘুরাঘুরি শেষ এবং ১ ও ৩ নং ব্রীজ ব্যবহার করা হয়েছে। এবার আমরা আবার A থেকে C তে ২ নং ব্রীজ এবং C থেকে B তে ৪ নং ব্রীজ ব্যবহার করে চলে আসলাম। অবশেষে B থেকে ৭ নং ব্রীজ ব্যবহার করে D তে এবং D থেকে ৬ নং ব্রীজ ব্যবহার করে A তে এসে যাত্রা শেষ করলাম।
খেয়াল করে দেখো আমরা পুরো শহর ভ্রমণ করেছি কোন ব্রীজ একবারের বেশি ব্যবহার না করে আর ব্যবহার করিনি এরকম কোন ব্রীজও বাকি নাই।
যখন আমরা কোন গ্রাফের প্রতিটি নোড ঘুরে আসতে পারি প্রতিটি এজ শুধুমাত্র একবার ব্যবহার করে (যেমনটা উপরের ছবি ৩ এ করতে পেরেছি), তখন এই যাত্রাকে বা ঘুরাঘুরিকে Eulerian walk বলে। এখানে যাত্রা বা walk বা হাঁটা বলার কারণ নিশ্চয়ই বুঝতে সমস্যা হচ্ছেনা, আমরা তো পুরো গ্রাফটা ঘুরেই বেড়িয়েছি, তাই না?
তাহলে দেখা যাচ্ছে যে, ছবি ২ এ এই Eulerian walk পাওয়া যাচ্ছেনা। এখন আমরা দেখবো কখন Eulerian walk পাওয়া সম্ভব এবং কখন নয়। আলোচনার জন্য নিচের ছবিটি খেয়াল করি। এখানে দুটি গ্রাফ দেখা যাচ্ছে, প্রথম গ্রাফটিতে একটি নোড ও চারটি এজ আছে এবং দ্বিতীয়টিতে একটি নোড ও পাঁচটি এজ আছে। কোন নোডের যতগুলো এজ থাকে তাকে ঐ নোডের ডিগ্রি (Degree) বলে। তাহলে প্রথম গ্রাফটির নোডের ক্ষেত্রে আমরা বলতে পারি যে, এই নোডের ডিগ্রি হচ্ছে ৪।
ছবি ৪ এর প্রথম গ্রাফটির ক্ষেত্রে, ধরলাম আমরা ১ নং এজ দিয়ে নোডে প্রবেশ করলাম, দিয়ে ৪ নং এজ দিয়ে বের হয়ে গেলাম। তারপর বাইরে একটু ঘুরাঘুরি করে আবার ৩ নং এজ দিয়ে প্রবেশ করে ২ নং এজ দিয়ে বের হয়ে গেলাম। এর অর্থ হচ্ছে যে আমরা সবগুলো এজ দিয়েই গেছি কিন্তু নোডে আটকা পড়িনি। কিন্তু দ্বিতীয় গ্রাফে যদি আমরা খেয়াল করি তাহলে দেখা যাবে যে, ১ নং এজ দিয়ে প্রবেশ করলাম, ৫ নং দিয়ে বের হলাম, আবার ৪ নং দিয়ে প্রবেশ করে ৩ নং দিয়ে বের হলাম, ২ নং দিয়ে প্রবেশ করে আর বের হতে পারছিনা কারণ সবগুলো এজ আমার ব্যবহার করা হয়ে গেছে। অর্থাৎ আমি নোডে আটকা পড়ে গেছি।
উপরের উদাহরণ থেকে আমরা একটা সিদ্ধান্ত নিতে পারি যে, গ্রাফের কোন একটি নোড যদি শুরুর নোড বা শেষের নোড না হয় (যেমন ছবি ৩ এর যাত্রা শুরুর নোড ছিল B এবং শেষের নোড ছিল A) তাহলে তার ডিগ্রি হবে জোড়। ছবি ৪ এ আমরা ১ নং এজ দিয়ে নোডে প্রবেশ করেছিলাম অর্থাৎ এই নোডটা আমাদের শুরুর নোড নয়, কারণ আমরা তো এখান থেকে শুরু করিনি। অন্য কোথাও থেকে শুরু করে এই নোডে এসে প্রবেশ করেছি। আবার শেষে ২ নং এজ দিয়ে বের হয়ে গেছি অর্থাৎ এই নোডটা শেষের নোডও নয়। কারণ আমরা এই নোডে শেষ করছিনা, অন্য কোথাও চলে যাচ্ছি ২ নং এজ দিয়ে।
সিদ্ধান্তঃ যে নোডটা শুরুর (যাত্রা) বা শেষের নয় তার ডিগ্রি হবে জোড়।
আবার ছবি ৪ এর দ্বিতীয় গ্রাফটায় আমরা দেখতে পাচ্ছি, নোডের ডিগ্রি বিজোড় (৫টি)। আমরা বাইরে থেকে শুরু করলে অর্থাৎ ১ নং এজ দিয়ে প্রবেশ করলে, শেষে ২ নং এজ দিয়ে প্রবেশ করে আটকা পড়ে যাচ্ছি। তাহলে আমরাকে এই নোডে থেমে যেতে হচ্ছে, অর্থাৎ এটা শেষের নোড। আবার যদি আমরা এই নোড থেকে শুরু করি তাহলে ১ নং দিয়ে বের হয়ে ৫ নং দিয়ে প্রবেশ করে আবার ৪ নং দিয়ে বের হয়ে ৩ নং দিয়ে প্রবেশ করে ২ নং দিয়ে বের হয়ে যেতে পারবো। তাহলে এটা হবে শুরুর নোড।
সিদ্ধান্তঃ যে নোডটা শুরুর বা শেষের তার ডিগ্রি হবে বিজোড়। [এখানে শুরুর নোড বলতে আমরা যে নোড দিয়ে গ্রাফে চলা শুরু করছি এবং শেষের নোড বলতে যে নোড দিয়ে আমরা গ্রাফে চলা শেষ করছি।]
ছবি ২ এ, আমাদের শুরুর নোড এবং শেষের নোড আলাদা (যথাক্রমে B ও A)। এরা যেহেতু শুরুর বা শেষের নোড তাই এদের ডিগ্রি হবে বিজোড়। তাহলে দুুটি (দুই কিন্তু জোড় সংখ্যা!!) নোডের ডিগ্রি সংখ্যা হচ্ছে বিজোড়।
সিদ্ধান্তঃ যদি কোন গ্রাফের শুরু এবং শেষের নোড আলাদা হয় তাহলে বিজোড় ডিগ্রির নোডের সংখ্যা হবে দুই।
কিন্তু যদি গ্রাফের শুরু এবং শেষ একই নোডে হয় তাহলে কি হবে? ছবি ৪ এর প্রথম গ্রাফটিতে যদি আমরা ওই নোড থেকেই শুরু করি এবং ১ নং এজ দিয়ে বের হয়ে ৪ নং দিয়ে প্রবেশ করে আবার ৩ নং দিয়ে বের হয়ে ২ নং দিয়ে প্রবেশ করি তাহলে যেখানে শুরু হয়েছিল সেখানেই শেষ হচ্ছে। এক্ষেত্রে বিজোড় ডিগ্রির নোড থাকছেনা অর্থাৎ শূন্যসংখ্যক থাকছে।
সিদ্ধান্তঃ যদি কোন গ্রাফের শুরু এবং শেষের নোড একই হয় তাহলে বিজোড় ডিগ্রির নোডের সংখ্যা হবে শূন্য।
এবার আমরা ফেরত যাবো ছবি ২ এ। এখানে, A নোডের ডিগ্রি ৩, B নোডের ডিগ্রি ৩, C নোডের ডিগ্রি ৫ এবং D নোডের ডিগ্রি ৩। অর্থাৎ এখানে বিজোড় ডিগ্রির নোডের সংখ্যা ৪। যেহেতু এই গ্রাফে শুরুর এবং শেষের নোড আলাদা তাই বিজোড় ডিগ্রির সংখ্যা দুই হলে এই গ্রাফে আমরা Eulerian walk পেতে পারতাম। কিন্তু বিজোড় ডিগ্রির নোডের সংখ্যা ৪ হওয়ায় আমরা এই গ্রাফে Eulerian walk পাইনি। এভাবেই অয়লার সাহেব সিদ্ধান্ত দিয়েছিলেন যে কনিগসবার্গ শহর ঘুরতে গিয়ে প্রতিটি ব্রীজ অন্তত একবার ব্যবহার করা সম্ভব না।
অয়লার সম্পর্কে একটা তথ্য জানিয়ে শেষ করি। অয়লারের ১৩টি বাচ্চাকাচ্চা ছিল, কিন্তু তাদের মধ্যে মাত্র ৫ জন বড় হয়েছিল এবং বাকিরা বাচ্চাকালেই মারা যায়।
