Earth–Moon problem
ارتھ-مون کا مسئلہ ریاضی میں گراف کلرنگ کا ایک غیر حل شدہ مسئلہ ہے۔ یہ طیارہ نقشہ رنگنے کے مسئلے کی توسیع ہے (چار رنگ تھیوریم کے ذریعے حل کیا گیا)، اور اسے 1959 میں گیرہارڈ رنگیل نے پیش کیا تھا۔ ریاضیاتی لحاظ سے، یہ بائپلانر گراف کے کرومیٹک نمبر کی تلاش کرتا ہے۔ یہ معلوم ہے کہ یہ عدد کم از کم 9 اور زیادہ سے زیادہ 12 ہے۔ نقشے کے رنگ کے مسئلے میں، یوکلڈین سطح میں محض جڑے ہوئے علاقوں کا مجموعہ یا ٹپوولوجیکل طور پر مساوی جگہ، جیسے کہ زمین کی سطح پر موجود ممالک، کو رنگین ہونا ہے تاکہ جب دو خطوں کی حد غیر صفر ہو تو ان کے رنگ مختلف ہوں۔ اسے ہر خطے کے لیے ایک ورٹیکس اور ہر دو پڑوسی علاقوں کے لیے ایک کنارے بنا کر گراف رنگنے کے مسئلے میں تبدیل کیا جا سکتا ہے، جس سے ایک پلینر گراف تیار ہوتا ہے جس کے عمودی حصے رنگین ہوتے ہیں۔ چار رنگوں کے نظریہ کے مطابق، زیادہ سے زیادہ چار مختلف رنگوں کا استعمال کرتے ہوئے ایسا کرنا ہمیشہ ممکن ہے، چاہے کتنے ہی علاقے دیے جائیں۔ اس کے بجائے، ارتھ-مون کے مسئلے میں، زمین پر ہر ملک کی چاند کی سطح پر ایک متعلقہ کالونی ہے، جسے ایک ہی رنگ دیا جانا چاہیے۔ ان کالونیوں کی سرحدیں ہو سکتی ہیں جو زمین پر سرحدوں کے انتظام سے بالکل مختلف ہیں۔ ممالک کو ہر ملک اور اس کی کالونی کے لیے ایک ہی رنگ کا استعمال کرتے ہوئے رنگین ہونا چاہیے، تاکہ جب دو ممالک زمین پر یا چاند پر سرحد بانٹ لیں تو انہیں مختلف رنگ دیے جائیں۔ رنگل کا مسئلہ پوچھتا ہے: اس بات کی ضمانت کے لیے کتنے رنگوں کی ضرورت ہے کہ تمام ممالک رنگین ہو سکتے ہیں، اس سے کوئی فرق نہیں پڑتا کہ ان کی حدود کیسے ترتیب دی گئی ہیں؟ ایک بار پھر، کوئی بھی اسی سوال کو گراف تھیوری میں ایک کے مساوی طور پر بیان کر سکتا ہے، جس میں کسی ملک اور اس کی کالونی کے ہر جوڑے کے لیے ایک ہی سرے کے ساتھ، اور ممالک یا کالونیوں کے درمیان ہر قربت کے لیے ایک کنارے کے ساتھ۔ مسئلہ کے اس ورژن کے نتیجے میں آنے والے گراف بائیپلینر گراف ہیں، یا موٹائی دو کے گراف کے مساوی ہیں: ان کے کناروں کو دو ذیلی سیٹوں (زمین کے ملحقہ اور چاند کے ملحقہ) میں تقسیم کیا جا سکتا ہے تاکہ متعلقہ دو ذیلی گراف دونوں پلینر ہوں۔ ریاضیاتی لحاظ سے، رنگل کا مسئلہ بائپلانر گراف کی زیادہ سے زیادہ کرومیٹک تعداد کا مطالبہ کرتا ہے۔ چوٹیوں پر ایک بائپلانر گراف کے زیادہ تر کنارے ہوتے ہیں (اس تعداد سے دوگنا جو ایک پلینر گراف میں ہو سکتا ہے)، جس سے یہ پتہ چلتا ہے کہ اس کا کم از کم ایک ورٹیکس ہے جس کے صرف 11 پڑوسی ہیں۔ اس ورٹیکس کو ہٹانا، بقیہ گراف کو بار بار رنگنا، اور پھر ہٹائے گئے ورٹیکس کے لیے سب سے چھوٹے نمبر والے غیر استعمال شدہ رنگ کا استعمال زیادہ سے زیادہ 12 رنگوں کے ساتھ رنگنے کا باعث بنتا ہے۔ یہ گراف کے انحطاط کی ترتیب کے لیے لالچی رنگ ہے۔ لہذا، بائپلانر گراف کو زیادہ سے زیادہ 12 رنگوں کی ضرورت ہوتی ہے۔ 9 رنگوں کی ضرورت والے بائپلانر گراف کی ایک مثال کو 6-ورٹیکس مکمل گراف اور 5-ورٹیکس سائیکل گراف کے جوڑ کے طور پر بنایا جا سکتا ہے۔ اس کا مطلب یہ ہے کہ یہ دونوں ذیلی گراف ایک ذیلی گراف سے دوسرے تک تمام ممکنہ کناروں سے جڑے ہوئے ہیں۔ نتیجے میں آنے والے گراف میں 11 عمودی ہیں، اور مکمل ذیلی گراف کے لیے 6 رنگ اور سائیکل ذیلی گراف کے لیے 3 رنگ درکار ہوتے ہیں، جو مجموعی طور پر 9 رنگ دیتے ہیں۔ 1974 میں تھام سلانکے کی اس تعمیر نے رنگل کے اس قیاس کو مسترد کر دیا کہ 8 رنگ ہمیشہ کافی ہوں گے۔ اس کے بعد، بائپلانر 9 اہم گراف (کم سے کم گراف جن کے لیے نو رنگوں کی ضرورت ہوتی ہے) کی لامحدود بہت سی مثالیں بنائی گئی ہیں۔ اس مسئلے پر مزید پیش رفت نہ ہونے کے باوجود، 2018 میں ایلن گیتھنر نے اندازہ لگایا کہ اس مسئلے کے لیے رنگوں کی صحیح تعداد 11 ہے۔ وہ 10 کرومیٹک بائیپلانر گراف کے لیے کئی امیدواروں کا مشورہ دیتی ہیں، بشمول ایک کلیک کے ساتھ سائیکل گراف کے مضبوط پروڈکٹ کے طور پر حاصل کردہ گراف، اور کسی بھی ورٹیکس کو ہٹا کر حاصل کردہ گراف۔ ان گرافوں کو 10 رنگوں کی ضرورت کے لیے دکھایا جا سکتا ہے، کیونکہ ان کے پاس اتنا بڑا کوئی آزاد سیٹ نہیں ہے جو کم رنگوں والے رنگ میں سب سے بڑا رنگین کلاس ہو۔ مزید برآں، وہ ان کناروں کی تعداد کی حدود کو پورا کرتے ہیں جو ایک بائیپلانر گراف میں ہو سکتے ہیں۔ تاہم، ان کی نمائندگی بائیپلینر گراف (یا ارتھ-مون میپس) کے طور پر مبہم ہے۔ بائپلانر گراف کے رنگوں کی ایک درخواست میں شارٹ سرکٹس کے لیے پرنٹ شدہ سرکٹ بورڈ کی جانچ شامل ہے۔ ان بورڈوں کے اندر برقی موصل میں کراسنگ شامل ہیں، لیکن ان کے ملحقہ علاقوں کو بائیپلانر گراف بنانے کے لیے فرض کیا جا سکتا ہے۔ اس گراف کو رنگنے کے بعد، ملحقہ کنڈکٹرز کے درمیان شارٹ سرکٹس کا پتہ ایک ہی رنگ کے تمام کنڈکٹرز کو ایک دوسرے سے جوڑنے کے لیے اضافی سرکٹری شامل کر کے اور مختلف رنگوں کے جوڑوں کے درمیان رابطوں کی جانچ کر کے لگایا جا سکتا ہے۔ کچھ احتیاط کے ساتھ، اس خیال کو فی سرکٹ درکار ٹیسٹوں کی تعداد کو صرف چار تک کم کرنے کے لیے استعمال کیا جا سکتا ہے۔ عامیاں مسئلہ کی مختلف عامیوں پر بھی غور کیا گیا ہے، بشمول دو سے زیادہ سیاروں کے ساتھ یا ان ممالک کے ساتھ جو فی سیارے میں ایک سے زیادہ خطہ رکھ سکتے ہیں۔ خاص طور پر، موٹائی کے گراف (دو سے زیادہ سیاروں والے نقشوں کی نمائندگی کرتے ہیں لیکن فی سیارے صرف ایک خطہ)، زیادہ عین مطابق (اگرچہ ابھی تک نامکمل) نتائج معلوم ہیں۔ ان گرافوں کے لیے، کرومیٹک نمبر زیادہ سے زیادہ اسی انحطاط کی دلیل سے ہوتا ہے جو ارتھ-مون کے مسئلے میں استعمال ہوتا ہے۔ نیز، کیونکہ، عمودی کے ساتھ ایک مکمل گراف کی موٹائی ہوتی ہے، جس سے ظاہر ہوتا ہے کہ ان میں سے کچھ گرافوں کو رنگوں کی ضرورت ہوتی ہے۔ اس طرح، اس معاملے میں، اوپری اور نچلی حدود ایک دوسرے کے دو رنگوں کے اندر ہیں۔ حوالہ جات بیرونی روابط گراف کلرنگ