যে-কোনো মানচিত্রের চারটি রং, রৈখিক সময়ে

সমতল কাগজে আঁকা যে-কোনো মানচিত্রকে চারটি রং দিয়ে এমনভাবে রাঙানো যায় যে প্রতিবেশী দুটি দেশের রং কখনো এক হয় না। Francis Guthrie 1852 সালে এই অনুমান করেন; Appel ও Haken 1976 সালে তা প্রমাণ করেন। কিন্তু উপপাদ্যটি কেবল বলে যে চারটি রং বিদ্যমান। একটি নির্দিষ্ট মানচিত্রের জন্য সেগুলো খুঁজবেন কীভাবে? “এর কোনো সহজ উত্তর নেই,” লিখেছেন টোকিও বিশ্ববিদ্যালয়ের Yuta Inoue এবং জাপান, কানাডা, স্লোভেনিয়া ও ডেনমার্কের তাঁর পাঁচ সহকর্মী। প্রশ্নটি এতটাই জট পাকানো ছিল যে তা থেকে অনেক প্রস্তাবিত প্রতি-উদাহরণ জন্ম নিয়েছে।

বিন্দু, রেখা আর ত্রিভুজ

প্রতিটি দেশ হয়ে যায় একটি বিন্দু, বা শীর্ষবিন্দু (vertex), আর প্রতিটি অভিন্ন সীমান্ত একটি রেখা, বা বাহু (edge): মানচিত্রটি হয়ে যায় একটি সমতলীয় গ্রাফ (planar graph), যা রেখার কোনো কাটাকাটি ছাড়াই আঁকা যায়। একে রং করা মানে প্রতিটি শীর্ষবিন্দুকে চারটির একটি রং দেওয়া, যাতে প্রতিটি বাহুর দুই প্রান্তে রং আলাদা হয়। শীর্ষবিন্দুর সংখ্যাকে n বলা যাক। ত্রিভুজায়ন (triangulation) সামলানোই যথেষ্ট, যেখানে প্রতিটি তল একটি ত্রিভুজ: বেশি বাহু রং করাকে কেবল কঠিনই করে।

কেম্পের অদলবদল

মূল চালটির উৎস A. B. Kempe-র 1879 সালের একটি গবেষণাপত্র। চারটি রংকে জোড়ায় ভাগ করুন, ধরা যাক লালের সঙ্গে নীল আর সবুজের সঙ্গে হলুদ। কেম্পে শিকল (Kempe chain) হলো শীর্ষবিন্দুর একটি সংযুক্ত দল, যাদের গায়ে একটি জোড়ের দুটি রং। পুরো একটি শিকল জুড়ে সেই দুটি রং অদলবদল করলে রং-করা বৈধই থাকে।

চারটি প্রতিবেশী আছে এমন একটি শীর্ষবিন্দু v নিন, তার চারপাশে ক্রমানুসারে v0 থেকে v3, আর আগে বাকি অংশটি রং করুন। প্রতিবেশীরা তিনটি বা তার কম রং ব্যবহার করলে v খালি রংটি নেয়। চারটিই ব্যবহার করলে v0 থেকে শুরু হওয়া v0 ও v2-এর রঙের শিকলটি ধরে চলুন। সেটি v2-তে না পৌঁছালে তাকে অদলবদল করুন: v0 পায় v2-এর রং, ফলে v-এর জন্য একটি রং খালি হয়। সেটি v2-তে পৌঁছালে তার বদলে v1 ও v3-এর রঙে v1-এর শিকলটি অদলবদল করুন, যাতে v1 পায় v3-এর রং।

যে টুকরো সবসময় মেরামত করা যায়

উপপাদ্যের প্রমাণগুলো দাঁড়িয়ে আছে হ্রাসযোগ্য বিন্যাসের (reducible configurations) ওপর: ছোট ছোট নকশা যা কেটে বাদ দেওয়া যায়, তারপর বাকিটা রং হয়ে গেলে আবার বসানো যায়। যদি তাদের বলয়ের (ring) — ঠিক তাদের চারপাশের শীর্ষবিন্দুগুলোর — রং খাপ না খায়, তবে বাইরে করা সীমিত সংখ্যক উন্নয়নকারী কেম্পে পরিবর্তন সবসময় তা ঠিক করে দেয়: এখানে ব্যবহৃত নকশাগুলোর জন্য বড়জোর 25টি, যাদের বলয়ে বড়জোর 18টি শীর্ষবিন্দু থাকে।

একটি হ্রাসযোগ্য বিন্যাস (বাঁয়ে; প্রতিটি সংখ্যা বোঝায় পূর্ণ মানচিত্রে ওই শীর্ষবিন্দুর কতগুলো প্রতিবেশী থাকতে হবে) এবং তার বলয় R দিয়ে সম্পূর্ণ করা একই নকশা (ডানে)। — চিত্র 1, Inoue et al. (2026), arXiv:2610.39753.

Robertson, Sanders, Seymour ও Thomas 1997 সালে দেখান কীভাবে এভাবে, একবারে একটি নকশা ধরে, রং করা যায়। প্রতিটি দফা গ্রাফকে কয়েকটি শীর্ষবিন্দু ছোট করে এবং তার খরচ পুরো গ্রাফের ওপর দিয়ে একবার যাওয়া, তাই সময় হয় দ্বিঘাত (quadratic): দ্বিগুণ বড় মানচিত্রের জন্য চার গুণ বেশি।

আগের একটি গবেষণাপত্রে (FOCS’26) এই একই ছয় লেখক প্রমাণ করেন যে প্রতিটি ত্রিভুজায়নে n-এর সমানুপাতিক সংখ্যক পরস্পর-অস্পৃষ্ট হ্রাসযোগ্য বিন্যাস থাকে, যা 8,202টি নকশার একটি তালিকা থেকে নেওয়া — অথবা ততগুলো ছোট লুপ যাদের দুই পাশেই শীর্ষবিন্দু আছে, যেগুলোও কাজে আসে। তাঁরা সব নকশা একসঙ্গে সরিয়ে দেন, বাকিটা রং করেন, তারপর সব বলয় একসঙ্গে মেরামত করেন। একটি এলোমেলো কেম্পে পরিবর্তন একটি নির্দিষ্ট বলয়কে সাহায্য করে যদি তা রঙের সঠিক জোড় বাছে (তিনে এক সম্ভাবনা) এবং বলয় ছোঁয়া প্রতিটি শিকলে মুদ্রার টস সঠিক পড়ে (প্রতিটিতে দুইয়ে এক সম্ভাবনা)। এমন বড়জোর 18টি শিকল থাকলে সম্ভাবনা অন্তত 3 × 2¹⁸-এ এক, অর্থাৎ 786,432-এ এক: ছোট, কিন্তু স্থির। তাই দফার সংখ্যা বাড়ে কেবল log n হারে, মোটামুটি n-কে যতবার অর্ধেক করা যায়। কিন্তু একটিমাত্র পরিবর্তন গ্রাফের একটি স্থির ভগ্নাংশকে জড়াতে পারে: প্রতিটির খরচ পুরো গ্রাফের ওপর দিয়ে একবার যাওয়া, মোট n log n।

পুরো গ্রাফ ঘোরার বদলে একটি সারণি

নতুন গবেষণাপত্রটি log n-টি পরিবর্তন রেখে দেয়, কিন্তু প্রতিটিকে সস্তা করে। n-এর সমানুপাতিক সময়ের একটি প্রস্তুতির পর, প্রতিটি পরিবর্তন গড়ে প্রায় n / log n ধাপে খুঁজে বের করে কার্যকর করা হয়। তখন log n-টি পরিবর্তন মিলে n-এর সমানুপাতিক সময় নেয় — রৈখিক সময় — এমন একটি সীমা যাকে লেখকেরা সর্বোত্তম বলেন।

কৌশলটি হলো “চার রুশির পদ্ধতি” (Method of Four Russians)। যে উপ-সমস্যা ½ log n বিটের একটি কোডে এঁটে যায় — অর্থাৎ n লিখতে যত দ্বিমিক অঙ্ক লাগে তার অর্ধেক — তার বড়জোর √n-টি সম্ভাব্য রূপ থাকে, তাই তাদের সব উত্তর আগেই হিসাব করে একটি সারণিতে রাখা যায়। ধরে নেওয়া কম্পিউটারটি, যার মেমরি-শব্দ প্রায় log n বিটের, যে-কোনো সংরক্ষিত উত্তর এক ধাপে পড়ে ফেলে।

গ্রাফটিকে বারবার ছোট সীমানাওয়ালা নেস্টেড (একটির ভেতরে আরেকটি) অঞ্চলে কাটা হয়। সবচেয়ে ছোটগুলোতে থাকে প্রায় log n-টি শীর্ষবিন্দু, আর রংসহ সেগুলো একটি কোডে এঁটে যায়। প্রতিটি অঞ্চলের জন্য একটি ছোট সারাংশ-গ্রাফ লিখে রাখে কোন কোন সীমানা-শীর্ষবিন্দু একই কেম্পে শিকল ভাগ করে। তখন একটি পরিবর্তন “অদলবদল” বা “রেখে দাও” বিটের সারি হিসেবে নিচে নামে, আর প্রতিটি ছোট অঞ্চলে একবার সারণি দেখলেই সব রং হালনাগাদ হয়ে যায়।

চারটি রঙে রাঙানো একটি গ্রাফের অংশ। ধূসর জায়গাটি একটি অঞ্চল R; মোটা কালো বাহুগুলো লাল-নীল ও সবুজ-হলুদ জোড়ের কেম্পে শিকলের অংশ। — চিত্র 2, Inoue et al. (2026), arXiv:2610.39753.

একই অঞ্চলের সারাংশ: প্রতিটি নীল ছোপ একটি কেম্পে শিকলের একটি টুকরোকে বোঝায়, আর তার রেখাগুলো দেখায় সেটি কোন কোন সীমানা-শীর্ষবিন্দুকে যুক্ত করে। — চিত্র 3, Inoue et al. (2026), arXiv:2610.39753.

পাশা ছাড়াই বাছাই

এলোমেলো বাছাই দিয়ে এটি আগেই গড়ে রৈখিক সময়ে একটি মানচিত্র রং করে। গতি না হারিয়ে পাশা সরিয়ে দেওয়াই ছিল “নিঃসন্দেহে সবচেয়ে কঠিন অংশ”। একটি বলয়কে জীবিত বলা যাক, যতক্ষণ এখন পর্যন্ত প্রতিটি সিদ্ধান্ত তার পক্ষে গেছে। তাকে ছোঁয়া u-টি অনিষ্পন্ন শিকল যদি মুদ্রা টসের ওপর ছেড়ে দেওয়া হতো, তবে সে টিকে থাকত 1/2^u সম্ভাবনায়; সব জীবিত বলয়ের ওপর যোগ করলে এই সংখ্যাগুলো টিকে থাকা বলয়ের প্রত্যাশিত সংখ্যা দেয়। একটি শিকলের সিদ্ধান্ত নিলে যে বলয়গুলো সেই বাছাই চেয়েছিল তাদের প্রত্যেকের পদ দ্বিগুণ হয়, বাকিদের শূন্য হয়। অ্যালগরিদম সেই বিকল্পটি নেয় যা যোগফলকে কমতে দেয় না, যাতে শেষে অন্তত ততগুলো বলয় সাহায্য পায় যতগুলোকে দৈবক্রম গড়ে সাহায্য করত।

একটি সীমা, স্টপওয়াচ নয়

গবেষণাপত্রটি কোনো বাস্তবায়ন বা চলার সময় জানায় না, আর “n-এর সমানুপাতিক”-এর আড়ালে থাকা ধ্রুবকগুলোও দেওয়া হয়নি। সেগুলো বড়: 8,202টি নকশার প্রতিটির জন্য অ্যালগরিদম সংরক্ষণ করে তার বলয়ের প্রতিটি রং-বিন্যাসের কতগুলো উন্নয়নকারী পরিবর্তন লাগে — “বিপুল এক ধ্রুবক পরিমাণ তথ্য”। একটি পরিশিষ্টে তাঁরা নেস্টেড অঞ্চলের যে 2013 সালের নির্মাণের ওপর ভিত্তি করে কাজ করেছেন, তাতে “একটি ছোট ভুল”ও সংশোধন করেছেন। 1852 সালের একটি অনুমান এখন এমন একটি রং-করার পদ্ধতির সঙ্গে আসে, যার খরচ সে যে মানচিত্র রং করে তার চেয়ে দ্রুত বাড়ে না।