Hajós construction
આલેખ સિદ્ધાંતમાં, ગણિતની એક શાખા, હાજોસ બાંધકામ એ તેના નામ પરથી નામ આપવામાં આવેલા આલેખ પરની એક કામગીરી છે જેનો ઉપયોગ કોઈપણ નિર્ણાયક આલેખ અથવા કોઈપણ આલેખ બનાવવા માટે થઈ શકે છે, જેની રંગીન સંખ્યા ઓછામાં ઓછી અમુક થ્રેશોલ્ડ હોય. રચના દો અને બે દિશાહીન આલેખ બનો, એક ધાર બનો, અને એક ધાર બનો. પછી હાજોસ બાંધકામ એક નવો આલેખ બનાવે છે જે શિરોબિંદુઓને ઓળખીને અને એક જ શિરોબિંદુમાં બે આલેખને જોડે છે, બે ધારને દૂર કરે છે અને નવી ધાર ઉમેરે છે. ઉદાહરણ તરીકે, ચાલો અને દરેક ચાર શિરોબિંદુઓ પર સંપૂર્ણ આલેખ હોય; આ આલેખની સમપ્રમાણતાને કારણે, તેમાંથી દરેકમાંથી કઈ ધાર પસંદ કરવી તે મહત્ત્વનું નથી. આ કિસ્સામાં, હાજોસ બાંધકામને લાગુ કરવાનું પરિણામ મોઝર સ્પિન્ડલ છે, જે સાત-વર્ટેક્સ એકમ અંતર ગ્રાફ છે જેને ચાર રંગોની જરૂર છે. અન્ય એક ઉદાહરણ તરીકે, જો અને અનુક્રમે લંબાઈના ચક્ર આલેખ હોય, તો પછી હાજોસ રચનાને લાગુ કરવાનું પરિણામ પોતે લંબાઈનો ચક્ર આલેખ છે. જ્યારે આલેખ નીચેની ત્રણ રીતોમાંથી એકમાં રચાય છે ત્યારે તેને-રચનાત્મક (અથવા હાજોસ-રચનાત્મક) કહેવામાં આવે છેઃ સંપૂર્ણ આલેખ-રચનાત્મક છે. કોઈપણ બે-રચનાત્મક આલેખ બનવા દો. પછી હાજોસ બાંધકામને લાગુ કરીને રચાયેલો આલેખ-રચનાત્મક છે. કોઈપણ-રચનાત્મક આલેખ હોવો જોઈએ, અને કોઈપણ બે બિન-અડીને આવેલા શિરોબિંદુઓને અંદર આવવા દો. પછી સંયોજન દ્વારા અને એક જ શિરોબિંદુમાં રચાયેલો આલેખ પણ-રચનાત્મક છે. તેવી જ રીતે, આ આલેખ આલેખમાં ધાર ઉમેરીને અને પછી તેને સંકોચાઈને બનાવી શકાય છે. રંગ સાથે જોડાણ દરેક-રચનાત્મક આલેખને કોઈપણ યોગ્ય આલેખ રંગમાં ઓછામાં ઓછા રંગોની જરૂર છે તેની ચકાસણી કરવી સરળ છે. ખરેખર, આ સંપૂર્ણ આલેખ માટે સ્પષ્ટ છે, અને બે બિન-અડીને આવેલા શિરોબિંદુઓને ઓળખવાની અસર તેમને કોઈપણ રંગમાં એકબીજા જેવો જ રંગ રાખવા માટે દબાણ કરે છે, જે રંગોની સંખ્યાને ઘટાડતી નથી. હાજોસ બાંધકામમાં જ, નવી ધાર બે શિરોબિંદુઓમાંથી ઓછામાં ઓછા એકને દબાણ કરે છે અને અને માટે સંયુક્ત શિરોબિંદુ કરતાં અલગ રંગ ધરાવે છે, તેથી સંયુક્ત આલેખનો કોઈપણ યોગ્ય રંગ બે નાના આલેખમાંથી એકના યોગ્ય રંગ તરફ દોરી જાય છે જેમાંથી તે રચાયો હતો, જેના કારણે તેને ફરીથી રંગોની જરૂર પડે છે. હેઝોસે વધુ મજબૂત રીતે સાબિત કર્યું કે ગ્રાફને ઓછામાં ઓછા રંગોની જરૂર હોય છે, કોઈપણ યોગ્ય રંગમાં, જો અને માત્ર ત્યારે જ જો તેમાં સબગ્રાફ તરીકે-રચનાત્મક ગ્રાફ હોય. સમાનરૂપે, દરેક નિર્ણાયક આલેખ (એક આલેખ કે જેના માટે રંગોની જરૂર હોય પરંતુ જેના માટે દરેક યોગ્ય પેટા આલેખ માટે ઓછા રંગોની જરૂર હોય)-રચનાત્મક છે. વૈકલ્પિક રીતે, રંગોની જરૂર હોય તેવા દરેક આલેખની રચના હાજોસની રચના, કોઈપણ બે બિન-અડીને આવેલા શિરોબિંદુઓને ઓળખવાની કામગીરી અને સંપૂર્ણ આલેખથી શરૂ કરીને આપેલ આલેખમાં શિરોબિંદુ અથવા ધાર ઉમેરવાની કામગીરીને જોડીને થઈ શકે છે. રંગની જગ્યાએ સૂચિ રંગ માટે સમાન રચનાનો ઉપયોગ કરી શકાય છે. નિર્ણાયક આલેખની રચનાત્મકતા કારણ કે, દરેક નિર્ણાયક આલેખ (એટલે કે, દરેક વિચિત્ર ચક્ર) ને-રચનાત્મક આલેખ તરીકે ઉત્પન્ન કરી શકાય છે જેથી તેની રચનામાં રચાયેલા તમામ આલેખ પણ-નિર્ણાયક હોય. કારણ કે, આ સાચું નથીઃ હાજોસના અનુમાનના પ્રતિકૂળ ઉદાહરણ તરીકે મળેલો આલેખ કે-રંગીન આલેખમાં એક પેટાવિભાગ હોય છે, તે પણ આ સમસ્યાના પ્રતિકૂળ ઉદાહરણ તરીકે કામ કરે છે. ત્યારબાદ, બધા માટે-નિર્ણાયક પરંતુ બિન-રચનાત્મક આલેખ માત્ર-નિર્ણાયક આલેખ દ્વારા મળી આવ્યા હતા. કારણ કે બે બિન-અડીને આવેલા શિરોબિંદુઓને ભેળવવાથી પરિણામી આલેખમાં શિરોબિંદુઓની સંખ્યા ઓછી થાય છે, તેથી હાજોસ દ્વારા વ્યાખ્યાયિત કામગીરીનો ઉપયોગ કરીને આપેલ આલેખને રજૂ કરવા માટે જરૂરી કામગીરીની સંખ્યા શિરોબિંદુઓની સંખ્યા કરતાં વધી શકે છે. વધુ સ્પષ્ટ રીતે,-રંગીન આલેખની હાજોસ સંખ્યાને રચવા માટે જરૂરી ઓછામાં ઓછા પગલાઓ તરીકે વ્યાખ્યાયિત કરો, જ્યાં દરેક પગલું અગાઉ રચાયેલા બે આલેખને જોડીને, અગાઉ રચાયેલા આલેખના બે બિન-અડીને આવેલા શિરોબિંદુઓને ભેળવીને અથવા અગાઉ રચાયેલા આલેખમાં શિરોબિંદુ અથવા ધાર ઉમેરીને નવો આલેખ બનાવે છે. તેઓએ બતાવ્યું કે, ધારવાળા-વર્ટેક્સ આલેખ માટે,. જો દરેક આલેખમાં બહુપદી હાજોસ સંખ્યા હોય, તો તેનો અર્થ એ થશે કે બિનનિર્ધારણીય બહુપદી સમયમાં બિન-રંગીનતા સાબિત કરવી શક્ય છે, અને તેથી તે સૂચવે છે કે એન. પી. = સહ-એન. પી., જે નિષ્કર્ષ જટિલતા સિદ્ધાંતવાદીઓ દ્વારા અસંભવિત માનવામાં આવે છે. જો કે, કેટલીક જટિલતા-સૈદ્ધાંતિક ધારણા કર્યા વિના હાજોસ સંખ્યા પર બિન-બહુપદી નીચલી સીમાઓ કેવી રીતે સાબિત કરવી તે જાણીતું નથી, અને જો આવી સીમા સાબિત થઈ શકે તો તે ગાણિતિક તર્કમાં ચોક્કસ પ્રકારની ફ્રીજ સિસ્ટમ પર બિન-બહુપદી સીમાઓનું અસ્તિત્વ પણ સૂચવે છે. આપેલ આલેખ માટે હાજોસની રચનાનું વર્ણન કરતા અભિવ્યક્તિ વૃક્ષનું લઘુતમ કદ હાજોસની સંખ્યા કરતાં નોંધપાત્ર રીતે મોટું હોઈ શકે છે, કારણ કે માટે ટૂંકી અભિવ્યક્તિ સમાન આલેખનો ઘણી વખત ફરીથી ઉપયોગ કરી શકે છે, એક અર્થતંત્ર જે અભિવ્યક્તિ વૃક્ષમાં મંજૂરી નથી. ત્યાં 3-રંગીન આલેખ અસ્તિત્વમાં છે જેના માટે આવા સૌથી નાના અભિવ્યક્તિ વૃક્ષનું ઘાતાંકીય કદ હોય છે. અન્ય એપ્લિકેશનોએ 4-નિર્ણાયક પોલિહેડ્રલ આલેખનો અનંત સમૂહ બનાવવા માટે હાજોસ બાંધકામનો ઉપયોગ કર્યો હતો, જેમાં દરેક શિરોબિંદુઓ કરતાં બમણાથી વધુ ધાર ધરાવે છે. તેવી જ રીતે, ઘણા 4-નિર્ણાયક ત્રિકોણ-મુક્ત આલેખ બનાવવા માટે ગ્રોટ્ઝસ્ક આલેખથી શરૂ કરીને બાંધકામનો ઉપયોગ કર્યો, જેને તેમણે પરંપરાગત બેકટ્રેકિંગ અલ્ગોરિધમ્સનો ઉપયોગ કરીને રંગવાનું મુશ્કેલ હોવાનું દર્શાવ્યું. પોલિહેડ્રલ સંયોજનશાસ્ત્રમાં, સ્થિર સમૂહ પોલિટોપનાં પાસાં પેદા કરવા માટે હાજોસ બાંધકામનો ઉપયોગ કરવામાં આવ્યો હતો. નોંધો સંદર્ભો. . . . . જેમ ટાંકવામાં આવ્યું છે. . . . . . . . . આલેખ કામગીરી આલેખ રંગકામ