Comjagat.com-The first IT magazine in Bangladesh
  • ভাষা:
  • English
  • বাংলা
হোম > কনিগসবার্গ সেতু সমস্যা
লেখক পরিচিতি
লেখকের নাম: গণিতদাদু
মোট লেখা:১৩৭
লেখা সম্পর্কিত
পাবলিশ:
২০১৭ - জুলাই
তথ্যসূত্র:
কমপিউটার জগৎ
লেখার ধরণ:
গণিত
তথ্যসূত্র:
ম্যাথ
ভাষা:
বাংলা
স্বত্ত্ব:
কমপিউটার জগৎ
কনিগসবার্গ সেতু সমস্যা
কনিগসবার্গ সেতু সমস্যা
কনিগসবার্গ (Konigsberg) হচ্ছে প্রেজেল নদীতীরের একটি শহর। অষ্টাদশ শতাব্দীতে এটি ছিল একটি জার্মান শহর। এখন এটি রাশিয়ার একটি শহর। এই শহরের ভেতর দিয়ে নদী এঁকেবেঁকে প্রবাহিত হয়ে সৃষ্টি করেছে দু’টি রিভার আইল্যান্ড বা নদীদ্বীপ। আর নদীদ্বীপ দু’টিকে নদীতীরের সাথে যুক্ত করতে শহরের ভেতরে তৈরি করতে হয়েছে সাতটি সেতু, ঠিক নিচের চিত্রের মতো করে।
তখন একটি প্রশ্ন দেখা দেয়, কেউ কি পারবে পুরো এই শহরটি ঘুরে দেখতে, এই সেতু সাতটি মাত্র একবার অতিক্রম করে। অন্য কথায়, কেউ এই শহর ঘুরে দেখতে একটি সেতু একবার অতিক্রম করলে সে দ্বিতীয়বার আর এই সেতু অতিক্রম করতে পারবে না। এভাবে একবার করে এই সেতুগুলো অতিক্রম করে পুরো কনিগসবার্গ শহর ঘুরে দেখার চেষ্টা সেখানকার মানুষের মধ্যে একটি মজার ব্যাপার হয়ে উঠল। কিন্তু কেউই আর এই কাজটি করতে পারছিল না। এই চেষ্টা চালিয়ে যখন একের পর এক মানুষ ব্যর্থ হতে লাগল, তখন সবাই বলতে লাগল আসলেই এটি একটি কঠিন কাজ। কেউ কেউ বলতে লাগল এটি শুধু কঠিনই নয়, অসম্ভব এক কাজ। কিন্তু কেউ নিশ্চিত করে বলতে পারেনি, আসলেই এ কাজটি বাস্তবে সম্ভব কি না।
এক সময় এই কঠিন কাজটির কথা শুনলেন সুইজারল্যান্ডের বিখ্যাত গণিতবিদ লিওনার্দ ইউলার। তিনি কাজ করতেন রুশ সাম্রাজ্ঞী ক্যাথারিন দ্য গ্রেটের অধীনে। ১৭৩৬ সালে ইউলার প্রমাণ করে দেখান, একবার করে একটি সেতু অতিক্রম করে এই সাতটি সেতু পার হয়ে গোটা কনিগসবার্গ শহর বেড়ানো কিছুতেই সম্ভব নয়। তিনি তা প্রমাণ করে দেখান এক ধরনের একটি ডায়াগ্রাম বা চিত্র উদ্ভাবন করে। এই ডায়াগ্রামের নাম দেয়া হয় নেটওয়ার্ক। এই নেটওয়ার্ক তৈরি করা হয় নিচের চিত্রের মতো কয়েকটি শীর্ষবিন্দু (ভারটেক্স) বা ফুটাকে (ডট) বক্ররেখা দিয়ে সংযুক্ত করে।
তিনি চারটি ফুটা বা ভারটেক্সকে ব্যবহার করেন নদীর দু’টি তীর ও দু’টি দ্বীপকে বোঝানোর জন্য। এগুলোকে তিনি নাম দেন A, B এবং C, D। সাতটি বক্ররেখা দিয়ে বোঝানো হয় সাতটি সেতুকে। চিত্রে সহজেই দেখা যায়, তিনটি সেতু (বক্ররেখা) সংযুক্ত রয়েছে নদীতীর A-এর সাথে। আর অন্য তিনটি সেতু (বক্ররেখা) সংযুক্ত রয়েছে নদীতীর B-এর সাথে। অন্যদিকে পাঁচটি সেতু (বক্ররেখা) সংযুক্ত রয়েছে নদীদ্বীপ C-এর সাথে। আর তিনটি সেতু সংযুক্ত আছে নদীদ্বীপ D-এর সাথে। এর অর্থ হচ্ছে, প্রতিটি ফুটা বা শীর্ষবিন্দু সংযুক্ত রয়েছে বেজোড়সংখ্যক সেতু বা বক্ররেখার সাথে। এ কারণে এসব শীর্ষবিন্দুকে নাম দেয়া হয়েছে ওড ভারটেক্স বা বেজোড় শীর্ষবিন্দু। যদি কোনো শীর্ষবিন্দুর সাথে জোড়সংখ্যক সেতু বা বক্ররেখা সংযুক্ত থাকত, তবে এগুলোকে বলা হতো ইভেন ভারটেক্স বা জোড় শীর্ষবিন্দু।
মনে রাখতে হবে, আমাদের সমস্যাটি ছিল গোটা শহরটি ঘুরে আসা প্রতিটি সেতু একবারমাত্র পার হয়ে, কোনো সেতুই দুইবার পার হওয়া যাবে না। ইউলারের নেটওয়ার্কে এর অর্থ ছিল একটিমাত্র বক্ররেখা বরাবর একবারমাত্র চলে সবগুলো শীর্ষবিন্দু পার হওয়া। ইউলার প্রমাণ করেন এটি কখনই সম্ভব নয়। কারণ তিনি দেখলেন, জোড়সংখ্যক ভারটেক্স বা শীর্ষবিন্দু পাইতে হলে আমাদেরকে যাত্রা শুরু বা শেষ করতে হবে একই ভারটেক্স বা শীর্ষবিন্দু থেকে। কারও পক্ষে একটিমাত্র বিন্দু দিয়ে একবার পার হয়ে সবগুলো বিন্দু পার হওয়া তখনই সম্ভব, যখন সেখানে থাকবে কোনো জোড়সংখ্যক ভারটেক্স বা শীর্ষবিন্দু। যেহেতু এই কনিগসবার্গ সেতু সমস্যায় রয়েছে চারটি বেজোড় শীর্ষবিন্দু বা ওড ভারটেক্স, সেহেতু সবগুলো সেতু একবার পার হয়ে গোটা শহরটি বেড়ানো সম্ভব নয়। প্রশ্ন আসে, যদি ইউলারের নেটওয়ার্কে মোটেও কোনো ওড ভারটেক্স না থাকত, তবে কী হতো? তবে কি সব ভারটেক্স বা শীর্ষবিন্দু একবার করে পার হয়ে সব বিন্দু পর হওয়া সম্ভব হতো?
আসলে ইউলারের গুরুত্বপূর্ণ পর্যবেক্ষণ হচ্ছে- কোনো নেটওয়ার্কের একটি পথে একবারমাত্র চলে সবগুলো পথ একবার করে পার হতে হলে, তখন এই নেটওয়ার্কের বিন্দুগুলো জোড়সংখ্যক পথ দিয়ে সংযুক্ত থাকতে হবে। কারণ, এ ক্ষেত্রে আপনি একটি পথে একটি বিন্দুতে ঢোকেন, তবে আরেকটি পথ থাকা চাই এই বিন্দু থেকে বের হয়ে আসতে, অর্থাৎ এ ক্ষেত্রে থাকা চাই দু’টি লিঙ্ক। একটি বিন্দু দুইবার ভিজিট করতে প্রয়োজেন হবে চারটি লিঙ্কের, আর এভাবে ভিজিটসংখ্যা বাড়লে লিঙ্কের সংখ্যাও বাড়তে থাকবে। এই পর্যবেক্ষণ থেকেই ইউলার আমাদের বলে দিলেন, কনিগসবার্গ শহরের সেতুগুলো একবার করে পার হয়ে এই শহর বেড়ানো সম্ভব নয়। কারণ, এই সেতু নেটওয়ার্কের সংযোগবিন্দুগুলোর নেটওয়ার্কে বিন্দুগুলো বেজোড়সংখ্যক লিঙ্ক দিয়ে সংযুক্ত।
ইউলারের চিস্তাভাবনা থেকেই শুরু হলো গণিতের গ্রাফ থিওরির যুগ, যাকে বলা হয় নেটওয়ার্ক থিওরি। কনিগসবার্গ সেতু সমস্যাই আসলে উদ্ভাবনের পথ করে দিল নেটওয়ার্ক নামের গণিত শাখা। এই নেটওয়ার্কের উদ্ভাবন সূত্রেই আমরা পেলাম নতুন ধরনের গণিত, যার নাম দেয়া হয়েছে টপোলজি। এই টপোলজির ব্যবহার এখন চলছে নানাভাবে। রেলওয়ে পরিকল্পনা ও এর নেটওয়ার্ক ম্যাপ করতে আজকাল ব্যবহার হচ্ছে এই টপোলজি।
গণিতদাদু

পত্রিকায় লেখাটির পাতাগুলো
লেখাটি পিডিএফ ফর্মেটে ডাউনলোড করুন
লেখাটির সহায়ক ভিডিও
২০১৭ - জুলাই সংখ্যার হাইলাইটস
চলতি সংখ্যার হাইলাইটস