Earth–Moon problem
પૃથ્વી-ચંદ્રની સમસ્યા એ ગણિતમાં આલેખ રંગ પરની એક વણઉકેલાયેલી સમસ્યા છે. તે સમતલીય નકશાના રંગની સમસ્યાનું વિસ્તરણ છે (ચાર રંગ પ્રમેય દ્વારા ઉકેલી શકાય છે), અને 1959માં ગેરહાર્ડ રિંગેલ દ્વારા રજૂ કરવામાં આવ્યું હતું. ગાણિતિક દ્રષ્ટિએ, તે દ્વિ-સમતલ આલેખની રંગીન સંખ્યાને શોધે છે. તે જાણીતું છે કે આ સંખ્યા ઓછામાં ઓછી 9 અને વધુમાં વધુ 12 છે. ફોર્મ્યુલેશન નકશાના રંગની સમસ્યામાં, યુક્લિડિયન સમતલમાં સરળ રીતે જોડાયેલા પ્રદેશોનો સંગ્રહ અથવા ટોપોલોજીકલ રીતે સમકક્ષ જગ્યા, જેમ કે પૃથ્વીની સપાટી પરના દેશો, રંગીન હોવા જોઈએ, જેથી જ્યારે બે પ્રદેશોની લંબાઈ બિન-શૂન્ય હોય, ત્યારે તેમના રંગો અલગ હોય. દરેક પ્રદેશ માટે શિરોબિંદુ અને દરેક બે પડોશી પ્રદેશો માટે ધાર બનાવીને તેને આલેખ રંગની સમસ્યામાં રૂપાંતરિત કરી શકાય છે, જે એક સમતલીય આલેખ બનાવે છે જેના શિરોબિંદુઓ રંગીન હોય છે. ચાર રંગ પ્રમેય અનુસાર, મહત્તમ ચાર જુદા જુદા રંગોનો ઉપયોગ કરીને આવું કરવું હંમેશા શક્ય છે, ભલે ગમે તેટલા પ્રદેશો આપવામાં આવે. તેના બદલે, પૃથ્વી-ચંદ્રની સમસ્યામાં, પૃથ્વી પરના દરેક દેશની ચંદ્રની સપાટી પર અનુરૂપ વસાહત છે, જેને સમાન રંગ આપવો આવશ્યક છે. આ વસાહતોની સરહદો હોઈ શકે છે જે પૃથ્વી પરની સરહદોની ગોઠવણીથી સંપૂર્ણપણે અલગ છે. દરેક દેશ અને તેની વસાહત માટે સમાન રંગનો ઉપયોગ કરીને દેશો રંગીન હોવા જોઈએ, જેથી જ્યારે બે દેશો પૃથ્વી પર અથવા ચંદ્ર પર સરહદ વહેંચે ત્યારે તેમને જુદા જુદા રંગો આપવામાં આવે. રિંગેલની સમસ્યા પૂછે છેઃ તમામ દેશો રંગીન હોઈ શકે તેની ખાતરી કરવા માટે કેટલા રંગોની જરૂર છે, ભલે તેમની સીમાઓ કેવી રીતે ગોઠવવામાં આવે? ફરીથી, દેશ અને તેની વસાહતની દરેક જોડી માટે એક જ શિરોબિંદુ અને દેશો અથવા વસાહતો વચ્ચેની દરેક નિકટતા માટે એક ધાર સાથે, ગ્રાફ થિયરીમાં એક સમાન પ્રશ્નને શબ્દસમૂહ કરી શકાય છે. સમસ્યાના આ સંસ્કરણમાં જે આલેખ પરિણમે છે તે બાયપ્લેનાર આલેખ છે, અથવા સમાન જાડાઈના બે આલેખ છેઃ તેમની કિનારીઓને બે ઉપગણ (પૃથ્વીની નજીક અને ચંદ્રની નજીક) માં વિભાજિત કરી શકાય છે જેથી અનુરૂપ બે પેટા આલેખ બંને સમતલીય હોય. ગાણિતિક દ્રષ્ટિએ, રિંગેલની સમસ્યા દ્વિ-સમતલ આલેખની મહત્તમ રંગીન સંખ્યા માટે પૂછે છે. સીમાઓ શિરોબિંદુઓ પર દ્વિ-સમતલીય આલેખની મોટાભાગની ધાર હોય છે (સમતલીય આલેખની સંખ્યાની બમણી), જેમાંથી તે અનુસરે છે કે તેમાં માત્ર 11 પડોશીઓ સાથે ઓછામાં ઓછું એક શિરોબિંદુ હોય છે. આ શિરોબિંદુને દૂર કરવાથી, બાકીના આલેખને પુનરાવર્તિત રીતે રંગવું, અને પછી દૂર કરેલા શિરોબિંદુ માટે સૌથી નાના ક્રમાંકિત બિનઉપયોગી રંગનો ઉપયોગ કરવાથી મહત્તમ 12 રંગો સાથે રંગ આવે છે; ગ્રાફના અધોગતિના ક્રમ માટે આ લોભી રંગ છે. તેથી, દ્વિ-સમતલ આલેખ માટે વધુમાં વધુ 12 રંગોની જરૂર પડે છે. 9 રંગોની જરૂર હોય તેવા બાયપ્લેનાર ગ્રાફનું ઉદાહરણ 6-વર્ટેક્સ સંપૂર્ણ ગ્રાફ અને 5-વર્ટેક્સ ચક્ર ગ્રાફના જોડાણ તરીકે બનાવી શકાય છે. આનો અર્થ એ છે કે આ બે સબગ્રાફ એક સબગ્રાફથી બીજા સુધી તમામ સંભવિત ધાર દ્વારા જોડાયેલા છે. પરિણામી આલેખમાં 11 શિરોબિંદુઓ છે, અને સંપૂર્ણ સબગ્રાફ માટે 6 રંગો અને ચક્ર સબગ્રાફ માટે 3 રંગોની જરૂર પડે છે, જે એકંદરે 9 રંગો આપે છે. 1974માં થોમ સુલાંકે દ્વારા કરવામાં આવેલી આ રચનાએ રિંગેલના એ અનુમાનને નકારી કાઢ્યું હતું કે 8 રંગો હંમેશા પૂરતા રહેશે. ત્યારબાદ, બાયપ્લેનાર 9-ક્રિટિકલ ગ્રાફ (ન્યૂનતમ ગ્રાફ કે જેમાં નવ રંગોની જરૂર હોય) ના અનંત ઉદાહરણો બનાવવામાં આવ્યા છે. સમસ્યા પર વધુ પ્રગતિનો અભાવ હોવા છતાં, 2018 માં એલેન ગેથનેરે અનુમાન લગાવ્યું હતું કે આ સમસ્યા માટે રંગોની યોગ્ય સંખ્યા 11 છે. તેણી 10-રંગીન બાયપ્લેનાર આલેખ માટે ઘણા ઉમેદવારોને સૂચવે છે, જેમાં એક જૂથ સાથે ચક્ર આલેખના મજબૂત ઉત્પાદન તરીકે મેળવેલ આલેખ અને તેમાંથી કોઈપણ શિરોબિંદુને દૂર કરીને મેળવેલ આલેખનો સમાવેશ થાય છે. આ આલેખને 10 રંગોની જરૂર હોવાનું દર્શાવી શકાય છે, કારણ કે તેમની પાસે એટલો મોટો સ્વતંત્ર સમૂહ નથી કે જે ઓછા રંગો સાથે રંગમાં સૌથી મોટો રંગ વર્ગ બની શકે. વધુમાં, તેઓ દ્વિ-સમતલ આલેખની ધારની સંખ્યા પરની મર્યાદાને પૂર્ણ કરે છે. જો કે, તેમને દ્વિ-સમતલ આલેખ (અથવા પૃથ્વી-ચંદ્ર નકશા) તરીકે રજૂ કરવા હજુ પણ અસ્પષ્ટ છે. દ્વિ-સમતલ આલેખના રંગોના એક ઉપયોગમાં ટૂંકી સર્કિટ માટે મુદ્રિત સર્કિટ બોર્ડનું પરીક્ષણ સામેલ છે. આ બોર્ડની અંદરના વિદ્યુત વાહકોમાં ક્રોસિંગનો સમાવેશ થાય છે, પરંતુ તેમની નિકટતાઓને બાયપ્લેનાર ગ્રાફ બનાવવાની ધારણા કરી શકાય છે. આ આલેખને રંગ્યા પછી, બધા વાહકોને એકબીજા સાથે સમાન રંગોથી જોડવા માટે વધારાની સર્કિટરી ઉમેરીને અને વિવિધ રંગોની જોડી વચ્ચેના જોડાણો માટે પરીક્ષણ કરીને નજીકના વાહકો વચ્ચેની ટૂંકી સર્કિટો શોધી શકાય છે. થોડી કાળજી સાથે, આ વિચારનો ઉપયોગ સર્કિટ દીઠ જરૂરી પરીક્ષણોની સંખ્યાને માત્ર ચાર સુધી ઘટાડવા માટે થઈ શકે છે. સામાન્યીકરણ સમસ્યાના વિવિધ સામાન્યીકરણ પર પણ વિચાર કરવામાં આવ્યો છે, જેમાં બેથી વધુ ગ્રહો અથવા એવા દેશો સાથે સમસ્યાના સંસ્કરણોનો સમાવેશ થાય છે કે જેમાં ગ્રહ દીઠ એકથી વધુ પ્રદેશ હોઈ શકે છે. ખાસ કરીને, જાડાઈના આલેખ (બેથી વધુ ગ્રહો સાથે નકશાનું પ્રતિનિધિત્વ કરે છે પરંતુ ગ્રહ દીઠ માત્ર એક પ્રદેશ), વધુ ચોક્કસ (જોકે હજુ પણ અપૂર્ણ) પરિણામો જાણીતા છે. આ આલેખ માટે, રંગીન સંખ્યા પૃથ્વી-ચંદ્રની સમસ્યામાં ઉપયોગમાં લેવાતી સમાન અધોગતિ દલીલ દ્વારા સૌથી વધુ છે. તેમજ, શિરોબિંદુઓ સાથેના સંપૂર્ણ આલેખની જાડાઈ હોય છે, જે દર્શાવે છે કે આમાંના કેટલાક આલેખ માટે રંગોની જરૂર પડે છે. આમ, આ કિસ્સામાં, ઉપલા અને નીચલા સીમાઓ એકબીજાના બે રંગોની અંદર હોય છે. સંદર્ભો બાહ્ય કડીઓ આલેખ રંગકામ