Moser spindle
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, મોઝર સ્પિન્ડલ (જેને મોઝર્સ સ્પિન્ડલ અથવા મોઝર ગ્રાફ પણ કહેવાય છે) એ એક દિશાહીન આલેખ છે, જેનું નામ ગણિતશાસ્ત્રીઓ લીઓ મોઝર અને તેમના ભાઈ વિલિયમના નામ પરથી રાખવામાં આવ્યું છે, જેમાં સાત શિરોબિંદુઓ અને અગિયાર ધાર છે. તે એક એકમ અંતરનો આલેખ છે જે કોઈપણ આલેખ રંગમાં ચાર રંગોની જરૂર પડે છે, અને તેના અસ્તિત્વનો ઉપયોગ એ સાબિત કરવા માટે કરી શકાય છે કે સમતલની રંગીન સંખ્યા ઓછામાં ઓછી ચાર છે. મોઝર સ્પિન્ડલને ગ્યોરગી હાજોસ પછી હાજોસ ગ્રાફ પણ કહેવામાં આવે છે, કારણ કે તેને હાજોસ બાંધકામના ઉદાહરણ તરીકે જોઈ શકાય છે. જો કે, ષટ્કોણની અંદર અંકિત ત્રિકોણના સ્વરૂપમાં "હાજોસ ગ્રાફ" નામ પણ એક અલગ આલેખ પર લાગુ કરવામાં આવ્યું છે. એકમ અંતર આલેખ તરીકે, મોઝર સ્પિન્ડલ 60 અને 120 ડિગ્રી ખૂણાઓ સાથે બે લંબચોરસ દ્વારા રચાય છે, જેથી લંબચોરસની બાજુઓ અને ટૂંકા કર્ણ સમબાહુ ત્રિકોણ બનાવે છે. બે રોમ્બીને સમતલમાં મૂકવામાં આવે છે, જે તેમના એક તીવ્ર-કોણીય શિરોબિંદુને એવી રીતે વહેંચે છે કે બાકીના બે તીવ્ર-કોણીય શિરોબિંદુઓ એકબીજાથી એક એકમ અંતર દૂર હોય. આલેખની અગિયાર ધાર આઠ લંબચોરસ બાજુઓ, લંબચોરસના બે ટૂંકા કર્ણ અને તીવ્ર-કોણીય શિરોબિંદુઓની એકમ-અંતરની જોડી વચ્ચેની ધાર છે. મોઝર સ્પિન્ડલને ચાર શિરોબિંદુઓ પર બે સંપૂર્ણ આલેખથી શરૂ થતા હાજોસ બાંધકામનો ઉપયોગ કરીને, ભૌમિતિક એમ્બેડિંગના સંદર્ભ વિના, ગ્રાફ-સૈદ્ધાંતિક રીતે પણ બનાવી શકાય છે. આ બાંધકામ દરેક સંપૂર્ણ આલેખમાંથી એક ધારને દૂર કરે છે, દૂર કરેલી ધારના બે અંતિમ બિંદુઓને બંને જૂથો દ્વારા વહેંચાયેલા એક જ શિરોબિંદુમાં ભેળવે છે, અને દૂર કરેલી ધારના બાકીના બે અંતિમ બિંદુઓને જોડતી નવી ધાર ઉમેરે છે. મોઝર સ્પિન્ડલ બનાવવાની બીજી રીત યુટિલિટી ગ્રાફ K3,3 માંથી તેની એક ધારને પેટા વિભાજિત કરીને રચાયેલા ગ્રાફના પૂરક ગ્રાફ તરીકે છે. હેડવિગર-નેલ્સન સમસ્યાનો ઉપયોગ હેડવિગર-નેલ્સન સમસ્યા પૂછે છે કે યુક્લિડિયન સમતલના બિંદુઓને એવી રીતે રંગવા માટે કેટલા રંગોની જરૂર છે કે એકબીજાથી એકમ અંતર પરના બિંદુઓની દરેક જોડીને જુદા જુદા રંગો સોંપવામાં આવે. એટલે કે, તે અનંત આલેખની રંગીન સંખ્યા પૂછે છે, જેના શિરોબિંદુઓ સમતલના તમામ બિંદુઓ છે અને જેની ધાર એકમ અંતર પર બિંદુઓની જોડી છે. મોઝર સ્પિન્ડલને કોઈપણ ગ્રાફ રંગમાં ચાર રંગોની જરૂર પડે છેઃ બે લંબચોરસમાંથી એકના કોઈપણ ત્રણ રંગમાં, જેમાંથી તે રચાય છે, લંબચોરસના બે તીવ્ર-કોણીય શિરોબિંદુઓ એકબીજા જેવા જ રંગ ધરાવતા હોવા જરૂરી છે. પરંતુ જો બે લંબચોરસના વહેંચાયેલ શિરોબિંદુ બે વિરુદ્ધ તીવ્ર-કોણીય શિરોબિંદુઓ જેવો જ રંગ ધરાવે છે, તો આ બે શિરોબિંદુઓ એકબીજા જેવા જ રંગ ધરાવે છે, જે જરૂરિયાતનું ઉલ્લંઘન કરે છે કે તેમને જોડતી ધાર અલગ-અલગ રંગના અંતિમ બિંદુઓ ધરાવે છે. આ વિરોધાભાસ દર્શાવે છે કે ત્રણ રંગો અશક્ય છે, તેથી ઓછામાં ઓછા ચાર રંગો જરૂરી છે. મોઝર સ્પિન્ડલને રંગવા માટે ચાર રંગો પણ પૂરતા છે, જે હકીકત એ હકીકત પરથી અનુસરે છે કે તેની અધોગતિ ત્રણ છે. મોઝર સ્પિન્ડલને ચાર રંગોની જરૂર છે તેનો વૈકલ્પિક પુરાવો હાજોસ બાંધકામમાંથી મળે છે. બંને સંપૂર્ણ આલેખ કે જેમાંથી મોઝર સ્પિન્ડલ રચાય છે તેના માટે ચાર રંગોની જરૂર પડે છે, અને હાજોસ બાંધકામ આ ગુણધર્મને જાળવી રાખે છે. વધુ સીધી રીતે, મોઝર સ્પિન્ડલમાં દરેક સ્વતંત્ર સમૂહમાં વધુમાં વધુ બે શિરોબિંદુઓ હોય છે, તેથી તે તમામ સાત શિરોબિંદુઓને આવરી લેવા માટે ઓછામાં ઓછા ચાર સ્વતંત્ર સમૂહ લે છે. મોઝર સ્પિન્ડલ એ પ્લેનના અનંત એકમ અંતર ગ્રાફનો સબગ્રાફ હોવાથી, પ્લેનના ગ્રાફને પણ કોઈપણ રંગમાં ઓછામાં ઓછા ચાર રંગોની જરૂર પડે છે. ડી બ્રુઇજન-એર્ડોસ થીયરમ (પસંદગીનો સ્વયંસિદ્ધ સિદ્ધાંત સાચો છે એવી ધારણા સાથે), પ્લેનની રંગીન સંખ્યા તેના કોઈપણ મર્યાદિત સબગ્રાફની સૌથી મોટી રંગીન સંખ્યા જેટલી જ છે; 2018 માં 5-રંગીન એકમ અંતર ગ્રાફના પરિવારની શોધ ન થઈ ત્યાં સુધી, અનંત એકમ અંતર ગ્રાફનો કોઈ પેટા ગ્રાફ મળી આવ્યો ન હતો જેને મોઝર સ્પિન્ડલ કરતા મોટી સંખ્યામાં રંગોની જરૂર હોય. જો કે, સમતલની રંગીન સંખ્યા માટે શ્રેષ્ઠ ઉપલી સીમા સાત છે, જે મોઝર સ્પિન્ડલ માટે જરૂરી રંગોની સંખ્યા કરતાં નોંધપાત્ર રીતે વધારે છે. અન્ય ગુણધર્મો અને ઉપયોગો મોઝર સ્પિન્ડલ એ સમતલીય આલેખ છે, જેનો અર્થ છે કે તેને સમતલમાં પાર કર્યા વિના દોરી શકાય છે. જો કે, સીધી રેખાની ધાર સાથે આવા ચિત્રની રચના કરવી શક્ય નથી જે એકમ અંતરનું ચિત્ર પણ હોય; એટલે કે, તે માચિસની લાકડીનો આલેખ નથી. મોઝર સ્પિન્ડલ પણ લેમન ગ્રાફ છે, જેનો અર્થ છે કે જ્યારે તે પ્લેનમાં જડિત થાય છે ત્યારે તે ઓછામાં ઓછી કઠોર સિસ્ટમ બનાવે છે. સમતલીય લેમન આલેખ તરીકે, તે એક પોઇન્ટેડ સ્યુડોટ્રિઆંગ્યુલેશનનો આલેખ છે, જેનો અર્થ છે કે તેને સમતલમાં એવી રીતે જડિત કરી શકાય છે કે અમર્યાદિત ચહેરો એમ્બેડિંગનો બહિર્મુખ પડદો હોય અને દરેક બંધાયેલ ચહેરો માત્ર ત્રણ બહિર્મુખ શિરોબિંદુઓ સાથે સ્યુડોટ્રિઆંગલ હોય. મોઝર આલેખનો પૂરક આલેખ ત્રિકોણ-મુક્ત આલેખ છે. આમ, મોઝર ગ્રાફના એકમ અંતર એમ્બેડિંગનો ઉપયોગ સમતલમાં સાત બિંદુઓને એવી રીતે મૂકવાની સમસ્યાને ઉકેલવા માટે થઈ શકે છે કે દરેક ત્રણ બિંદુઓ એકબીજાથી એકમ અંતર પર ઓછામાં ઓછી એક જોડી ધરાવે. મોઝર સ્પિન્ડલમાં કોઈપણ ધાર ઉમેરવાથી ગ્રાફમાં પરિણમે છે જે એકમ અંતર ગ્રાફ તરીકે પ્લેનમાં એમ્બેડ કરી શકાતો નથી, અને મોઝર સ્પિન્ડલથી કોઈપણ નાના એકમ અંતર ગ્રાફમાં ગ્રાફ હોમોમોર્ફિઝમ અસ્તિત્વમાં નથી. મોઝર સ્પિન્ડલના આ બે ગુણધર્મોનો ઉપયોગ આપેલ ગ્રાફમાં દ્વિ-પરિમાણીય એકમ અંતરની રજૂઆત છે કે કેમ તે પરીક્ષણની એન. પી.-કઠિનતા બતાવવા માટે કરવામાં આવ્યો હતો; સાબિતી 3એસએટીમાંથી ઘટાડાનો ઉપયોગ કરે છે જેમાં મોઝર સ્પિન્ડલનો ઉપયોગ ઘટાડામાં કેન્દ્રીય સત્ય-સેટિંગ ગેજેટ તરીકે થાય છે. મોઝર સ્પિન્ડલનો ઉપયોગ યુક્લિડિયન રામસે સિદ્ધાંતમાં પરિણામ સાબિત કરવા માટે પણ થઈ શકે છેઃ જો T એ સમતલમાં કોઈ ત્રિકોણ હોય, અને સમતલના બિંદુઓ બે રંગના કાળા અને સફેદ હોય, તો પછી T નો કાળો અનુવાદ અથવા એકબીજાથી એકમ અંતર પર સફેદ બિંદુઓની જોડી હોય છે. કારણ કે, M એ મોઝર સ્પિન્ડલનું એકમ-અંતર એમ્બેડિંગ છે, અને M + T એ M અને T નો મિન્કોવ્સ્કી સરવાળો છે. જો M + T પાસે કોઈ સફેદ એકમ-અંતર જોડી નથી, તો પછી M + T માં મોઝર સ્પિન્ડલની ત્રણ નકલોમાંથી દરેકમાં વધુમાં વધુ બે સફેદ બિંદુઓ હોવા જોઈએ, કારણ કે દરેક નકલમાં સફેદ બિંદુઓ એક સ્વતંત્ર સમૂહ બનાવવો આવશ્યક છે અને મોઝર સ્પિન્ડલમાં સૌથી મોટા સ્વતંત્ર સમૂહનું કદ બે છે. તેથી, મોઝર સ્પિન્ડલના સાત શિરોબિંદુઓમાંથી, એમ + ટીમાં સફેદ નકલ ધરાવતા વધુમાં વધુ છ શિરોબિંદુઓ હોવા જોઈએ, તેથી સાત શિરોબિંદુઓમાંથી એક હોવો જોઈએ, જેની તમામ નકલો કાળી હોવી જોઈએ. પરંતુ પછી આ શિરોબિંદુની ત્રણ નકલો ટી. નું ભાષાંતર બનાવે છે. ગોલમ્બ આલેખ સંદર્ભો પણ જુઓ બાહ્ય કડીઓ વ્યક્તિગત આલેખ પ્લાનર આલેખ