২৪একসাথে দুটি পরীক্ষা নয়: গ্রাফ রঙ করে রুটিন বানানো
এমন একটি পরীক্ষা বা ক্লাবের রুটিন বানানো যেখানে কোনো শিক্ষার্থীর একই সময়ে দুটি কাজ নেই, একটি বিখ্যাত গাণিতিক ধাঁধা। দলগুলো সমস্যাটিকে একটি গ্রাফে পরিণত করে, প্রতিটি বিষয়ের জন্য একটি বিন্দু আর যেকোনো দুটি বিষয়ে একই শিক্ষার্থী থাকলে তাদের মধ্যে একটি রেখা, আর তারপর বিন্দুগুলো এমনভাবে রঙ করে যাতে যুক্ত বিন্দুগুলোর রঙ আলাদা হয়। প্রতিটি রঙ একটি সময়ের স্লট। তারা সবচেয়ে কম কয়টি স্লট লাগে বের করে আর একটি আসল স্কুল অনুষ্ঠানের জন্য ন্যায্য রুটিন বানায়।
- ক্লাস ও বয়স
- ক্লাস ১১ · ১৬–১৭
- কাজের ধরন
- দলগত
- সময় লাগবে
- ৬০ মিনিটের ২টি সেশন
- কাঠিন্য
- চ্যালেঞ্জিং
- আনুমানিক খরচ
- ৳০–৳২০
গাণিতিক ধারণা
- সংঘাতের গ্রাফ
- গ্রাফ রঙ করা আর ক্রোম্যাটিক সংখ্যা
- লোভী (greedy) রঙ করার অ্যালগরিদম
- ত্রিভুজ আর ক্লিক থেকে নিম্নসীমা
- রুটিনে শর্ত আর ন্যায্যতা
শেখার উদ্দেশ্য
- একটি রুটিনের সমস্যাকে গ্রাফ হিসেবে মডেল করা।
- একটি পরিষ্কার অ্যালগরিদম দিয়ে গ্রাফ রঙ করা।
- স্লটের সংখ্যার একটি নিম্নসীমা প্রমাণ করা।
- একটি আসল অনুষ্ঠানের রুটিন বানানো আর যুক্তি দেওয়া।
বাস্তব জীবনের সাথে সম্পর্ক
বিশ্ববিদ্যালয় পরীক্ষার রুটিন বানায়, এয়ারলাইন গেট ঠিক করে, রেডিও স্টেশন এমন ফ্রিকোয়েন্সি বাছে যাতে একে অপরকে বাধা না দেয়, আর ফোন নেটওয়ার্ক চ্যানেল ভাগ করে, সবাই গ্রাফ রঙ করার ধারণা ব্যবহার করে।
প্রয়োজনীয় উপকরণ
- চার্ট পেপার আর রঙিন কলম বা স্টিকার
- কোন শিক্ষার্থী কোন বিষয় বা ক্লাবে আছে তার একটি তালিকা (নামবিহীন, শিক্ষক বা ক্লাস জরিপ থেকে)
- ঐচ্ছিক: একটি স্প্রেডশিট
ধাপে ধাপে নির্দেশনা
- শুরুতে: বিষয় P, Q, R, S, T। যে জোড়াগুলোতে একই শিক্ষার্থী আছে: P-Q, P-R, Q-R, R-S, S-T। সংঘাতের গ্রাফ আঁকো।
- যত কম রঙে পারো রঙ করো যাতে যুক্ত বিন্দুগুলো আলাদা হয়। কয়টি রঙ লাগল?
- একটি ত্রিভুজ খোঁজো (তিনটি বিন্দু, সবাই পরস্পর যুক্ত)। ব্যাখ্যা করো কেন একটি ত্রিভুজ অন্তত ৩টি রঙ বাধ্য করে।
- লোভী অ্যালগরিদম শেখো: বিন্দুগুলোর তালিকা করো (সবচেয়ে বেশি রেখা যার সে আগে), প্রত্যেককে প্রথম সেই রঙ দাও যা তার রঙ করা প্রতিবেশীরা ব্যবহার করেনি।
- আসল, নামবিহীন তথ্য সংগ্রহ করো: প্রত্যেক শিক্ষার্থী কোন বিষয়, ক্লাব বা প্রতিযোগিতার ইভেন্টে আছে।
- আসল সংঘাতের গ্রাফ বানিয়ে লোভী অ্যালগরিদম দিয়ে রঙ করো। অন্য ক্রমে চেষ্টা করো। রঙের সংখ্যা কি বদলায়?
- আসল শর্ত যোগ করো, যেমন কোনো শিক্ষার্থীর এক দিনে দুটির বেশি পরীক্ষা থাকবে না, বা একটি হল শুধু সকালে খালি।
- একটি চূড়ান্ত রুটিন, গ্রাফ আর কেন কম স্লটে করা সম্ভব নয় তার একটি ছোট প্রমাণ (খুঁজে পেলে) উপস্থাপন করো।
গাণিতিক ব্যাখ্যা
শুরুর উদাহরণে P, Q আর R একটি ত্রিভুজ বানায়, তাই তাদের তিনটি আলাদা স্লট লাগে, আর ৩ একটি নিম্নসীমা। তিনটি রঙই যথেষ্ট: P = স্লট ১, Q = স্লট ২, R = স্লট ৩, S = স্লট ১ (S শুধু R আর T-এর সাথে যুক্ত), T = স্লট ২। তাই সর্বনিম্ন সংখ্যা, যাকে ক্রোম্যাটিক সংখ্যা বলে, ঠিক ৩। লোভী অ্যালগরিদম দ্রুত আর সবসময় একটি বৈধ রুটিন দেয়, কিন্তু সবসময় সর্বনিম্ন দেয় না; অন্য ক্রমে একটি স্লট বাঁচতে পারে। বড় গ্রাফে আসল সর্বনিম্ন খোঁজা কম্পিউটার বিজ্ঞানের সবচেয়ে কঠিন পরিচিত সমস্যাগুলোর একটি, তাই আসল রুটিন নির্মাতারা চতুর অ্যালগরিদমের সাথে ভালো নিম্নসীমা মেলান, যেমন পরস্পর সংঘাতপূর্ণ বিষয়ের সবচেয়ে বড় দল।
প্রত্যাশিত ফলাফল
রঙ করা শুরুর গ্রাফ, আসল সংঘাতের গ্রাফ, শর্তসহ একটি চূড়ান্ত রুটিন আর সর্বনিম্ন স্লট সংখ্যা নিয়ে একটি ছোট লিখিত যুক্তি।
যে দক্ষতা গড়ে ওঠে
- গ্রাফ মডেলিং
- অ্যালগরিদমিক চিন্তা
- নিম্নসীমা দিয়ে প্রমাণ
- শর্তসহ বাস্তব পরিকল্পনা
মূল্যায়নের মানদণ্ড
- শুরুর উদাহরণ ৩টি রঙে রঙ করা আর ত্রিভুজের যুক্তি ব্যাখ্যা করা।
- তথ্য থেকে আসল গ্রাফ সঠিকভাবে বানানো।
- লোভী অ্যালগরিদম সঠিকভাবে প্রয়োগ করা।
- রুটিন বলা সব শর্ত পূরণ করে।
এক্সটেনশন চ্যালেঞ্জ
মানচিত্রের জন্য চার রঙের উপপাদ্য (Four Colour Theorem) খোঁজো। বাংলাদেশের বিভাগগুলোর একটি মানচিত্র এমনভাবে রঙ করো যাতে পাশাপাশি বিভাগের রঙ আলাদা হয়। সবচেয়ে কম কয়টি রঙ লাগে?
নিরাপত্তা ও অন্তর্ভুক্তি
বিষয় বা ক্লাবের তালিকা সংগ্রহের সময় নামের বদলে শিক্ষার্থী নম্বর বা কোড ব্যবহার করবে, আর তালিকা ক্লাসের মধ্যেই রাখবে।