Earth–Moon problem
পৃথিবীর-চাঁদের সমস্যা গণিতে গ্রাফের রঙ নিয়ে একটি অমীমাংসিত সমস্যা। এটি সমতলীয় মানচিত্রের রঙ সমস্যার একটি সম্প্রসারণ (চার রঙের উপপাদ্য দ্বারা সমাধান করা হয়েছে), এবং 1959 সালে গেরহার্ড রিঙ্গেল দ্বারা উপস্থাপিত হয়েছিল। গাণিতিক পরিভাষায়, এটি দ্বি-সমতলীয় গ্রাফের ক্রোমাটিক সংখ্যা চায়। জানা যায় যে এই সংখ্যাটি কমপক্ষে 9 এবং সর্বাধিক 12। মানচিত্রের রঙের সমস্যায়, ইউক্লিডীয় সমতলে সহজভাবে সংযুক্ত অঞ্চলগুলির একটি সংগ্রহ বা টপোলজিক্যালি সমতুল্য স্থান, যেমন পৃথিবীর পৃষ্ঠের দেশগুলি, এমনভাবে রঙিন হতে হবে যাতে, যখন দুটি অঞ্চলের সীমানা শূন্যেতর হয়, তখন তাদের বিভিন্ন রঙ থাকে। প্রতিটি অঞ্চলের জন্য একটি শীর্ষ এবং প্রতিটি দুটি পার্শ্ববর্তী অঞ্চলের জন্য একটি প্রান্ত তৈরি করে এটি একটি গ্রাফ রঙের সমস্যায় রূপান্তরিত করা যেতে পারে, একটি সমতলীয় গ্রাফ তৈরি করে যার শীর্ষগুলি রঙিন হতে হবে। চার রঙের উপপাদ্য অনুসারে, যত অঞ্চলই দেওয়া হোক না কেন, সর্বাধিক চারটি ভিন্ন রঙ ব্যবহার করে এটি করা সর্বদা সম্ভব। পরিবর্তে, পৃথিবী-চাঁদের সমস্যায়, পৃথিবীর প্রতিটি দেশের চাঁদের পৃষ্ঠে একটি অনুরূপ উপনিবেশ রয়েছে, যা অবশ্যই একই রঙ দেওয়া উচিত। এই উপনিবেশগুলির সীমানা থাকতে পারে যা পৃথিবীর সীমানার বিন্যাস থেকে সম্পূর্ণ আলাদা। প্রতিটি দেশ এবং তার উপনিবেশের জন্য একই রঙ ব্যবহার করে দেশগুলিকে অবশ্যই রঙিন হতে হবে, যাতে যখন দুটি দেশ পৃথিবীতে বা চাঁদে একটি সীমানা ভাগ করে নেয় তখন তাদের বিভিন্ন রঙ দেওয়া হয়। রিঙ্গেলের সমস্যাটি জিজ্ঞাসা করেঃ দেশগুলি রঙিন হতে পারে তা নিশ্চিত করার জন্য কতগুলি রঙের প্রয়োজন, তাদের সীমানা যেভাবে সাজানো হোক না কেন? আবার, একটি দেশ এবং তার উপনিবেশের প্রতিটি জোড়ার জন্য একটি একক শীর্ষ এবং দেশ বা উপনিবেশগুলির মধ্যে প্রতিটি সংলগ্নতার জন্য একটি প্রান্ত সহ গ্রাফ তত্ত্বের সমতুল্য একই প্রশ্নটি বাক্যাংশ করতে পারে। যে গ্রাফগুলি সমস্যার এই সংস্করণের ফলস্বরূপ হয় সেগুলি হল দ্বি-সমতলীয় গ্রাফ, বা সমানভাবে দুই পুরুত্বের গ্রাফঃ তাদের প্রান্তগুলিকে দুটি উপসেটে (পৃথিবীর সংলগ্নতা এবং চাঁদের সংলগ্নতা) বিভক্ত করা যেতে পারে যাতে সংশ্লিষ্ট দুটি উপগ্রাফ উভয়ই সমতলীয় হয়। গাণিতিক পরিভাষায়, রিঙ্গেলের সমস্যাটি দ্বি-সমতলীয় গ্রাফের সর্বাধিক ক্রোমাটিক সংখ্যা জিজ্ঞাসা করে। সীমানা শীর্ষে একটি দ্বি-সমতলীয় গ্রাফের সর্বাধিক প্রান্ত থাকে (একটি সমতলীয় গ্রাফের সংখ্যার দ্বিগুণ), যেখান থেকে দেখা যায় যে এটির কমপক্ষে একটি শীর্ষ রয়েছে যার মাত্র 11টি প্রতিবেশী রয়েছে। এই শীর্ষস্থানটি সরানো, অবশিষ্ট গ্রাফটিকে পুনরাবৃত্তিমূলকভাবে রঙ করা এবং তারপরে সরানো শীর্ষস্থানের জন্য ক্ষুদ্রতম-সংখ্যাযুক্ত অব্যবহৃত রঙটি ব্যবহার করা সর্বাধিক 12টি রঙের রঙের দিকে পরিচালিত করে; এটি গ্রাফের অবক্ষয় ক্রমের জন্য লোভী রঙ। অতএব, দ্বি-সমতলীয় গ্রাফের জন্য সর্বাধিক 12টি রঙের প্রয়োজন হয়। 9টি রঙের প্রয়োজন একটি দ্বি-সমতলীয় গ্রাফের একটি উদাহরণ 6-ভার্টেক্স সম্পূর্ণ গ্রাফ এবং 5-ভার্টেক্স চক্র গ্রাফের সংযোগ হিসাবে তৈরি করা যেতে পারে। এর অর্থ হল এই দুটি উপগ্রাফ একটি উপগ্রাফ থেকে অন্যটিতে সমস্ত সম্ভাব্য প্রান্ত দ্বারা সংযুক্ত। ফলস্বরূপ গ্রাফের 11টি শীর্ষ রয়েছে এবং সম্পূর্ণ উপ-গ্রাফের জন্য 6টি রঙ এবং চক্র উপ-গ্রাফের জন্য 3টি রঙের প্রয়োজন, যা সামগ্রিকভাবে 9টি রঙ দেয়। 1974 সালে থম সুলঙ্কের এই নির্মাণটি রিঙ্গেলের একটি অনুমানকে অস্বীকার করে যে 8টি রঙ সর্বদা যথেষ্ট হবে। পরবর্তীকালে, বাইপ্ল্যানার 9-ক্রিটিক্যাল গ্রাফের (ন্যূনতম গ্রাফ যার জন্য নয়টি রঙের প্রয়োজন) অসীম সংখ্যক উদাহরণ তৈরি করা হয়েছে। সমস্যাটির উপর আরও অগ্রগতির অভাব সত্ত্বেও, 2018 সালে এলেন গেথনার অনুমান করেছিলেন যে এই সমস্যার জন্য সঠিক রঙের সংখ্যা 11। তিনি 10-বর্ণের দ্বি-সমতলীয় গ্রাফের জন্য বেশ কয়েকটি প্রার্থীকে পরামর্শ দেন, যার মধ্যে একটি চক্রের সাথে চক্র গ্রাফের শক্তিশালী পণ্য হিসাবে প্রাপ্ত গ্রাফ এবং যে কোনও শীর্ষস্থান সরিয়ে প্রাপ্ত গ্রাফ রয়েছে। এই গ্রাফগুলির জন্য 10টি রঙের প্রয়োজন হতে পারে, কারণ এগুলির কোনও স্বাধীন সেট নেই যা কম রঙের রঙের বৃহত্তম রঙের শ্রেণী হতে পারে। উপরন্তু, তারা একটি দ্বি-সমতলীয় গ্রাফের প্রান্তের সংখ্যার সীমা পূরণ করে। যাইহোক, দ্বি-সমতলীয় গ্রাফ (বা পৃথিবী-চাঁদের মানচিত্র) হিসাবে তাদের একটি উপস্থাপনা অধরা রয়ে গেছে। প্রয়োগ দ্বি-সমতলীয় গ্রাফের রঙিনকরণের একটি প্রয়োগে শর্ট সার্কিটের জন্য মুদ্রিত সার্কিট বোর্ড পরীক্ষা করা হয়। এই বোর্ডগুলির মধ্যে বৈদ্যুতিক পরিবাহীগুলির মধ্যে ক্রসিং অন্তর্ভুক্ত রয়েছে, তবে তাদের সংলগ্নতা একটি দ্বি-সমতলীয় গ্রাফ গঠন করে বলে ধরে নেওয়া যেতে পারে। এই গ্রাফটি রঙ করার পরে, একই রঙের সমস্ত কন্ডাক্টরকে একে অপরের সাথে সংযুক্ত করার জন্য অতিরিক্ত সার্কিট যুক্ত করে এবং বিভিন্ন রঙের জোড়ার মধ্যে সংযোগের জন্য পরীক্ষা করে সংলগ্ন কন্ডাক্টরগুলির মধ্যে শর্ট সার্কিট সনাক্ত করা যেতে পারে। কিছু যত্নের সাথে, এই ধারণাটি প্রতি সার্কিটে প্রয়োজনীয় পরীক্ষার সংখ্যা মাত্র চারটিতে হ্রাস করতে ব্যবহার করা যেতে পারে। সাধারণীকরণ সমস্যার বিভিন্ন সাধারণীকরণও বিবেচনা করা হয়েছে, যার মধ্যে রয়েছে দুটির বেশি গ্রহ বা এমন দেশগুলির সাথে সমস্যার সংস্করণ যা প্রতি গ্রহে একাধিক অঞ্চল থাকতে পারে। বিশেষত, পুরুত্বের গ্রাফগুলি (দুটি গ্রহের বেশি কিন্তু প্রতি গ্রহে শুধুমাত্র একটি অঞ্চল সহ মানচিত্রের প্রতিনিধিত্ব করে), আরও সুনির্দিষ্ট (যদিও এখনও অসম্পূর্ণ) ফলাফল জানা যায়। এই গ্রাফগুলির জন্য, ক্রোমাটিক সংখ্যাটি সর্বাধিক পৃথিবী-চাঁদ সমস্যায় ব্যবহৃত একই অবক্ষয় যুক্তি দ্বারা হয়। এছাড়াও, কারণ, শীর্ষ সহ একটি সম্পূর্ণ গ্রাফের পুরুত্ব রয়েছে, যা দেখায় যে এই গ্রাফগুলির মধ্যে কিছু রঙের প্রয়োজন। সুতরাং, এই ক্ষেত্রে, উপরের এবং নীচের সীমানা একে অপরের দুটি রঙের মধ্যে থাকে। তথ্যসূত্র বাহ্যিক লিঙ্ক গ্রাফ রঙ