Heawood conjecture
આલેખ સિદ્ધાંતમાં, હેવુડ અનુમાન અથવા રિંગેલ-યંગ્સ પ્રમેય આપેલ જીનસની સપાટી પર આલેખ રંગ માટે જરૂરી રંગોની સંખ્યા માટે નીચી સીમા આપે છે. જાતિ 0,1,2,3,4,5,6,7,. ની સપાટીઓ માટે, રંગોની જરૂરી સંખ્યા 4,7,8,9,10,11,12,12,, રંગીન સંખ્યા અથવા હેવુડ સંખ્યા છે. આ અનુમાન 1890માં પર્સી જ્હોન હેવુડ દ્વારા ઘડવામાં આવ્યું હતું અને 1968માં ગેરહાર્ડ રિંગેલ અને ટેડ યંગ્સ દ્વારા સાબિત કરવામાં આવ્યું હતું. એક કેસ, નોન-ઓરિએન્ટેબલ ક્લેઇન બોટલ, સામાન્ય સૂત્ર માટે અપવાદ સાબિત થયો. સમતલ અથવા ગોળા માટે જરૂરી રંગોની સંખ્યા શોધવાની ઘણી જૂની સમસ્યા માટે સંપૂર્ણપણે અલગ અભિગમની જરૂર હતી, જેને 1976માં હેકેન અને એપેલ દ્વારા ચાર રંગ પ્રમેય તરીકે ઉકેલવામાં આવ્યો હતો. ગોળા પર નીચલી સીમા સરળ છે, જ્યારે ઉચ્ચ જાતિ માટે ઉપલી સીમા સરળ છે અને હેવુડના મૂળ ટૂંકા પેપરમાં સાબિત થયું હતું જેમાં અનુમાન હતું. બીજા શબ્દોમાં કહીએ તો, રિંગેલ, યંગ્સ અને અન્યોએ દરેક જીનસ g = 1,2,3, માટે આત્યંતિક ઉદાહરણો બનાવવાની જરૂર હતી. જો g = 12s + k હોય, તો જાતિ k = 0,1,2,3,4,5,6,7,8,9,10,11 મુજબ 12 કિસ્સાઓમાં આવે છે. સરળ બનાવવા માટે, ધારો કે કેસ k સ્થાપિત કરવામાં આવ્યો છે જો 12s + k સ્વરૂપના g ની મર્યાદિત સંખ્યા જ શંકામાં હોય. પછી જે વર્ષોમાં બાર કેસોનું સમાધાન કરવામાં આવ્યું હતું અને જેમના દ્વારા નીચે મુજબ છેઃ 1954, રિંગેલઃ કેસ 5,1961, રિંગેલઃ કેસ 3,7,10 1963, ટેરી, વેલ્ચ, યંગ્સઃ કેસ 0,4 1964, ગસ્ટિન, યંગ્સઃ કેસ 1 1965, ગસ્ટિનઃ કેસ 9 1966, યંગ્સઃ કેસ 6 1967, રિંગેલ, યંગ્સઃ કેસ 2,8,11 છેલ્લા સાત છૂટાછવાયા અપવાદોનું સમાધાન નીચે મુજબ કરવામાં આવ્યું હતુંઃ 1967, મેયરઃ કેસ 18,20,23 1968, રિંગેલ, યંગ્સઃ કેસ 30,35,47,59, અને અનુમાન સાબિત થયું હતું. ઔપચારિક નિવેદન પર્સી જ્હોન હેવુડે 1890 માં અનુમાન લગાવ્યું હતું કે આપેલ જીનસ જી> 0 માટે, તે જીનસની દિશા નિર્ધારિત સપાટી પર દોરેલા તમામ આલેખને રંગવા માટે જરૂરી ઓછામાં ઓછા રંગોની સંખ્યા (અથવા સપાટીના કોઈપણ વિભાજનના પ્રદેશોને ફક્ત જોડાયેલા પ્રદેશોમાં રંગવા માટે સમકક્ષ) ફ્લોર ફંક્શન ક્યાં છે તેના દ્વારા આપવામાં આવે છે. યુલર લાક્ષણિકતા દ્વારા જીનસને બદલીને, આપણે એક સૂત્ર મેળવીએ છીએ જે ઓરિએન્ટેબલ અને નોન-ઓરિએન્ટેબલ બંને કેસોને આવરી લે છે, આ સંબંધ ધરાવે છે, જેમ કે રિંગેલ અને યંગ્સે દર્શાવ્યું હતું, ક્લેઈન બોટલ સિવાયની તમામ સપાટીઓ માટે. ફિલિપ ફ્રેન્કલીન (1930) એ સાબિત કર્યું કે સૂત્ર દ્વારા આગાહી કરવામાં આવી છે તેમ ક્લેઈન બોટલને 7ને બદલે વધુમાં વધુ 6 રંગોની જરૂર પડે છે. ફ્રેન્કલીન ગ્રાફને ક્લેઈન બોટલ પર એવી રીતે દોરી શકાય છે કે જે છ પરસ્પર-અડીને આવેલા પ્રદેશો બનાવે છે, જે દર્શાવે છે કે આ બંધન ચુસ્ત છે. ઉપલા બાઉન્ડ, જે હેવુડના મૂળ ટૂંકા પેપરમાં સાબિત થયું છે, તે લોભી રંગના અલ્ગોરિધમ પર આધારિત છે. યુલર લાક્ષણિકતામાં હેરફેર કરીને, કોઈ બતાવી શકે છે કે આપેલ સપાટીમાં જડિત દરેક ગ્રાફમાં આપેલ બાઉન્ડ કરતાં ઓછામાં ઓછું એક ડિગ્રીનું શિરોબિંદુ હોવું જોઈએ. જો કોઈ આ શિરોબિંદુને દૂર કરે છે, અને બાકીના આલેખને રંગ આપે છે, તો દૂર કરેલા શિરોબિંદુ સાથે સંકળાયેલી કિનારીઓની નાની સંખ્યા એ સુનિશ્ચિત કરે છે કે તેને બંધની બહાર રંગોની જરૂરી સંખ્યા વધાર્યા વિના આલેખમાં ફરીથી ઉમેરી શકાય છે અને રંગીન કરી શકાય છે. બીજી દિશામાં, સાબિતી વધુ મુશ્કેલ છે, અને તેમાં દર્શાવવાનો સમાવેશ થાય છે કે દરેક કિસ્સામાં (ક્લેઇન બોટલ સિવાય) આપેલ સંખ્યાબંધ રંગોની સમકક્ષ સંખ્યાબંધ શિરોબિંદુઓ સાથેનો સંપૂર્ણ આલેખ સપાટી પર જડિત કરી શકાય છે. ઉદાહરણ ટોરસમાં g = 1 છે, તેથી χ = 0 છે. તેથી, સૂત્ર જણાવે છે તેમ, પ્રદેશોમાં ટોરસના કોઈપણ પેટાવિભાગને મહત્તમ સાત રંગોનો ઉપયોગ કરીને રંગીન કરી શકાય છે. આ ચિત્ર ટોરસનું એક પેટાવિભાગ દર્શાવે છે જેમાં સાત પ્રદેશોમાંથી દરેક એકબીજાના પ્રદેશને અડીને આવેલા છે; આ પેટાવિભાગ દર્શાવે છે કે આ કેસ માટે રંગોની સંખ્યા પર સાતની સીમા ચુસ્ત છે. આ પેટાવિભાગની સીમા ટોરસ પર હેવુડ ગ્રાફનું એમ્બેડિંગ બનાવે છે. સંદર્ભો બાહ્ય કડીઓ આલેખ રંગના ટોપોલોજીકલ આલેખ સિદ્ધાંત સિદ્ધ થયેલા અનુમાનો આલેખ સિદ્ધાંતમાં પ્રમેયો