ہر نقشے کے لیے چار رنگ، خطی وقت میں دریافت

کسی چپٹے کاغذ پر بنا کوئی بھی نقشہ چار رنگوں سے اس طرح رنگا جا سکتا ہے کہ پڑوسی ممالک کبھی ایک ہی رنگ میں شریک نہ ہوں۔ فرانسس گتھری (Francis Guthrie) نے 1852 میں یہ قیاس پیش کیا؛ ایپل اور ہیکن (Appel and Haken) نے 1976 میں اسے ثابت کیا۔ مگر مسئلہ صرف یہ کہتا ہے کہ چار رنگ موجود ہیں۔ کسی دیے گئے نقشے کے لیے انہیں ڈھونڈا کیسے جائے؟ ٹوکیو یونیورسٹی کے یوتا اینوئے (Yuta Inoue) اور جاپان، کینیڈا، سلووینیا اور ڈنمارک کے ان کے پانچ ساتھی لکھتے ہیں: “اس کا کوئی آسان جواب نہیں”۔ یہ اتنا الجھا ہوا رہا ہے کہ اس کی وجہ سے بہت سی مجوزہ جوابی مثالیں سامنے آئیں۔

نقطے، لکیریں اور مثلث

ہر ملک ایک نقطہ، یعنی راس (vertex)، بن جاتا ہے، اور ہر مشترکہ سرحد ایک لکیر، یعنی کنارہ (edge): نقشہ ایک مستوی گراف (planar graph) بن جاتا ہے، جو لکیریں کاٹے بغیر بنایا جاتا ہے۔ اسے رنگنے کا مطلب ہے ہر راس کو چار میں سے ایک رنگ دینا، ہر کنارے کے دونوں سروں پر مختلف۔ راسوں کی تعداد کو n کہیے۔ مثلث بندیوں (triangulations) سے نمٹنا کافی ہے، جن میں ہر چہرہ ایک مثلث ہوتا ہے: مزید کنارے رنگنے کو صرف مشکل ہی بناتے ہیں۔

کیمپے کا تبادلہ

بنیادی چال اے۔ بی۔ کیمپے (A. B. Kempe) کے 1879 کے ایک مقالے سے آتی ہے۔ چار رنگوں کی جوڑیاں بنائیے، مثلاً سرخ کے ساتھ نیلا اور سبز کے ساتھ زرد۔ کیمپے زنجیر (Kempe chain) راسوں کا ایک جڑا ہوا گروہ ہے جو ایک جوڑی کے دو رنگ پہنے ہو۔ پوری زنجیر پر ان دو رنگوں کو آپس میں بدلنے سے رنگ کاری درست رہتی ہے۔

ایک راس v لیجیے جس کے چار پڑوسی ہوں، اس کے گرد ترتیب سے v0 سے v3 تک، اور باقی کو پہلے رنگ دیجیے۔ اگر پڑوسی تین یا اس سے کم رنگ استعمال کرتے ہیں تو v خالی رنگ لے لیتا ہے۔ اگر وہ چاروں استعمال کرتے ہیں تو اس زنجیر کے پیچھے چلیے جو v0 سے v0 اور v2 کے رنگوں میں شروع ہوتی ہے۔ اگر یہ v2 تک نہیں پہنچتی تو اسے بدل دیجیے: v0 v2 کا رنگ لے لیتا ہے، اور v کے لیے ایک رنگ خالی ہو جاتا ہے۔ اگر یہ v2 تک پہنچتی ہے تو اس کے بجائے v1 کی زنجیر کو v1 اور v3 کے رنگوں میں بدلیے، تاکہ v1 v3 کا رنگ لے لے۔

ٹکڑے جن کی ہمیشہ مرمت ہو سکتی ہے

اس مسئلے کے ثبوت قابلِ تخفیف ترتیبوں (reducible configurations) پر ٹکے ہیں: چھوٹے نمونے جنہیں کاٹ کر نکالا جا سکتا ہے، پھر باقی کے رنگے جانے کے بعد واپس لگایا جا سکتا ہے۔ اگر ان کے حلقے (ring) — یعنی ان کے بالکل گرد کے راس — کے رنگ میل نہ کھائیں، تو باہر کی گئی بہتری لانے والی کیمپے تبدیلیوں کی ایک محدود تعداد انہیں ہمیشہ درست کر دیتی ہے: یہاں استعمال ہونے والے نمونوں کے لیے زیادہ سے زیادہ 25، جن کے حلقوں میں زیادہ سے زیادہ 18 راس ہیں۔

ایک قابلِ تخفیف ترتیب (بائیں؛ ہر عدد بتاتا ہے کہ پورے نقشے میں اس راس کے کتنے پڑوسی ہونے چاہییں) اور وہی نمونہ اپنے حلقے R سے مکمل (دائیں)۔ — شکل 1، Inoue et al. (2026)، arXiv:2610.39753۔

رابرٹسن، سینڈرز، سیمور اور تھامس (Robertson, Sanders, Seymour and 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 کے متناسب وقت لیتی ہیں — خطی وقت (linear time) — ایک ایسی حد جسے مصنفین بہترین ممکن کہتے ہیں۔

ترکیب “چار روسیوں کا طریقہ” (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 کے احتمال سے بچتا؛ تمام زندہ حلقوں پر جمع کرنے سے یہ اعداد بچنے والوں کی متوقع تعداد دیتے ہیں۔ کسی زنجیر کا فیصلہ کرنا ہر اس حلقے کی رقم کو دگنا کر دیتا ہے جو وہی انتخاب چاہتا تھا اور باقیوں کی رقم کو صفر کر دیتا ہے۔ الگورتھم وہ راستہ چنتا ہے جو مجموعے کو گرنے نہیں دیتا، تاکہ آخر میں کم از کم اتنے حلقوں کی مدد ہو جتنوں کی اتفاق اوسطاً کرتا۔

ایک حد، اسٹاپ واچ نہیں

مقالہ کسی عملی نفاذ (implementation) اور کسی چلنے کے وقت کی اطلاع نہیں دیتا، اور “n کے متناسب” میں چھپے مستقلات نہیں بتائے گئے۔ وہ بڑے ہیں: 8,202 نمونوں میں سے ہر ایک کے لیے الگورتھم محفوظ رکھتا ہے کہ اس کے حلقے کی ہر رنگ کاری کو کتنی بہتری لانے والی تبدیلیوں کی ضرورت ہے — “معلومات کی ایک بہت بڑی مستقل مقدار”۔ ایک ضمیمے میں وہ ایک دوسرے کے اندر سمائے خطوں کی 2013 کی اس تعمیر میں “ایک معمولی غلطی” بھی درست کرتے ہیں جس پر وہ اپنا کام استوار کرتے ہیں۔ 1852 کا ایک قیاس اب ایک ایسے رنگ کاری کے طریقۂ کار کے ساتھ آتا ہے جس کی لاگت اس نقشے سے زیادہ تیزی سے نہیں بڑھتی جسے وہ رنگتا ہے۔