✖

কনিগসবার্গের সাত সেতু

অষ্টাদশ শতকে কনিগসবার্গ (Königsberg) শহরের মানুষ দীর্ঘদিন একটি ধাঁধা নিয়ে মাথা ঘামিয়েছিল। শহরের মধ্য দিয়ে বয়ে গেছে প্রেগেল নদী, যা দুইটি দ্বীপ তৈরি করেছে। নদীর ওপর দিয়ে দ্বীপগুলোতে যাওয়ার মোট সাতটি সেতু আছে। রবিবারের একটি হাঁটায় কি সব সেতু পার হওয়া যায়, কিন্তু প্রতিটি সেতু কেবল একবার করে? দেখা যাক, নদীর ওপর সেতুগুলো কীভাবে ছিল:

কোনো এক জায়গা থেকে হাঁটা শুরু করে প্রতিটি সেতু একবার করে পার হয়ে সব সেতু ঘুরে আসা কি সম্ভব? চেষ্টা করে দেখা যাক। বাঁ দিকের নিচ থেকে শুরু করে ওপরে উঠব, তারপর ক্রমে ডানে যাব, এভাবে:

দেখা যাচ্ছে, সাতটির মধ্যে ছয়টি সেতু পার হয়েছি, একটি সেতু বাদ পড়েছে। অন্য একটি পথ চেষ্টা করা যাক…

আবারও আমাদের কনিগসবার্গের সাতটি সেতুর মাত্র ছয়টি পার হয়েছি। মনে হচ্ছে, একবারের হাঁটায় প্রতিটি সেতু একবার করে পার হওয়া সম্ভব নয়। একদিন এই সমস্যার মুখোমুখি হলেন বিখ্যাত গণিতবিদ লিওনার্ড অয়লার (Leonhard Euler)। বিখ্যাত বললে কম বলা হয়, অয়লার ছিলেন গণিতের এক কিংবদন্তি, যাঁর নামে এমনকি অয়লারের সংখ্যার নাম রাখা হয়েছে। অয়লার ঠিক করলেন, এই ধাঁধার সমাধান তিনি করবেন। শুরুতে তিনি দ্বীপগুলো বা শহরের যেসব অংশে সেতু গিয়ে মিলেছে, সেগুলোকে চিহ্নিত করলেন:

এরপর অয়লার এভাবে চিন্তা করলেন: কোনো দ্বীপে যদি জোড় সংখ্যক সেতু থাকে, তাহলে যেখান থেকেই শুরু করি না কেন, একবারের হাঁটায় এই সেতুগুলো পার হওয়া যায়। কারণ একটি সেতু দিয়ে দ্বীপে আসি, আরেকটি দিয়ে বেরিয়ে যাই, তাতে বাকি সেতুর সংখ্যা দুই কমে যায়। একটি সেতু দিয়ে দ্বীপে এসে আরেকটি দিয়ে বেরোতে দুইটি সেতু লাগে। দ্বীপে ছয়টি সেতু থাকলে দ্বীপটিতে তিনবার যাওয়া হবে। যেমন, ধরি দ্বীপ B তে এভাবে চারটি সেতু আছে:

তাহলে যেখান থেকেই শুরু করি না কেন, রবিবারের একবারের হাঁটায় সব সেতু পার হওয়া যায়। নিজে চেষ্টা করে দেখ! ছবিতে আমি একটি পথ চিহ্নিত করেছি। এবার ধরি, দ্বীপ D থেকে দ্বীপ B তে আরও একটি সেতু আছে:

দেখা যাচ্ছে, আমাদের বেছে নেওয়া পথে প্রতিটি সেতু একবার করে পার হয়ে সব সেতু ঘোরা যায় না। কোনো একটি সেতু দিয়ে দ্বীপ B তে ফিরে এসে তারপর দ্বীপ D তে যেতে হতো। কিন্তু আমরা অন্য পথ বেছে নিতে পারি। হাঁটা শুরু করতে পারি দ্বীপ B থেকে, তখন প্রতিটি সেতু একবার করে পার হয়ে সব সেতু ঘোরা যায়:

আমরা হাঁটা শুরু করলাম দ্বীপ B থেকে, ওপরে গেলাম এলাকা A তে, তারপর সেতু দিয়ে আবার B তে, এরপর এলাকা C তে, তারপর আবার দ্বীপ B তে, আর শেষে দ্বীপ D তে। তাই বিজোড় সংখ্যক সেতুর কোনো দ্বীপ থেকে শুরু করলে তার সব সেতু একবার করে পার হওয়া যায়। কিংবা উল্টোভাবেও যাওয়া যায়: দ্বীপ D থেকে শুরু করে দ্বীপ B তে শেষ করা যায়।

তাই অয়লার লক্ষ করলেন, প্রতিটি সেতু একবার করে পার হয়ে সব সেতু ঘুরতে হলে হয় সব দ্বীপে জোড় সংখ্যক সেতু থাকতে হবে, নয়তো বিজোড় সংখ্যক সেতুর দ্বীপ থাকতে পারে দুইটি। বিজোড় সংখ্যক সেতুর একটি দ্বীপে শুরু করব, অন্যটিতে শেষ করব। বাকি সব দ্বীপে জোড় সংখ্যক সেতু থাকতে হবে। কনিগসবার্গের আসল সাতটি সেতুর দিকে তাকালে

দেখা যায়, প্রতিটি দ্বীপে বিজোড় সংখ্যক সেতু! দ্বীপ A তে 3 টি, B তে 5 টি, C তে 3 টি, আর D তেও 3 টি। তাই ধাঁধাটির কোনো সমাধান নেই: রবিবারের একবারের হাঁটায় সাতটি সেতুর প্রতিটি একবার করে পার হওয়া সম্ভব নয়। কিন্তু যেকোনো একটি সেতু ভেঙে ফেললে হঠাৎ ধাঁধাটির সমাধান মিলবে। যেমন, দ্বীপ B ও C এর মধ্যের একটি সেতু ভেঙে ফেলি:

দেখা যাচ্ছে, এখন দ্বীপ B তে 4 টি সেতু আর দ্বীপ C তে দুইটি সেতু। দ্বীপ A ও D এর সেতুর সংখ্যা বদলায়নি। এখন জোড় সংখ্যক সেতুর দ্বীপ দুইটি, আর বিজোড় সংখ্যক সেতুর দ্বীপ দুইটি। বিজোড় সংখ্যক সেতুর কোনো একটি দ্বীপ থেকে হাঁটা শুরু করলে প্রতিটি সেতু একবার করে পার হয়ে সব সেতু ঘোরা যায়। ছবিতে আমরা শুরু করেছি দ্বীপ A থেকে এবং শেষ করেছি দ্বীপ D তে।

এভাবে লিওনার্ড অয়লার আরও একটি বিখ্যাত গাণিতিক সমস্যার সমাধান করলেন এবং মোটামুটি সেই বিষয়ের ভিত্তি স্থাপন করলেন, যাকে আজ আমরা গ্রাফ তত্ত্ব বলি। তাঁর সম্মানে গ্রাফ তত্ত্বের ভাষায় যে গ্রাফের সব ধার (edge) একবার করে পার হওয়া যায়, তাকে বলা হয় অয়লার গ্রাফ।