Barnette's conjecture
બાર્નેટનું અનુમાન ગ્રાફ થિયરીમાં એક વણઉકેલાયેલી સમસ્યા છે, જે ગણિતની એક શાખા છે, જે ગ્રાફમાં હેમિલ્ટોનિયન ચક્રને લગતી છે. તેનું નામ યુનિવર્સિટી ઓફ કેલિફોર્નિયા, ડેવિસ ખાતે પ્રોફેસર એમેરિટસ ડેવિડ ડબ્લ્યુ. બાર્નેટના નામ પરથી રાખવામાં આવ્યું છે; તે જણાવે છે કે દરેક દ્વિપક્ષી પોલિહેડ્રલ ગ્રાફમાં શિરોબિંદુ દીઠ ત્રણ ધાર સાથે હેમિલ્ટોનિયન ચક્ર હોય છે. વ્યાખ્યાઓ સમતલીય આલેખ એ એક દિશાહીન આલેખ છે જે કોઈપણ ક્રોસિંગ વિના યુક્લિડિયન સમતલમાં જડિત કરી શકાય છે. પ્લેનર ગ્રાફને પોલિહેડ્રલ કહેવામાં આવે છે જો અને માત્ર ત્યારે જ જો તે 3-વર્ટેક્સ-જોડાયેલ હોય, એટલે કે, જો ત્યાં બે શિરોબિંદુઓ અસ્તિત્વમાં ન હોય તો તેને દૂર કરવાથી બાકીનો ગ્રાફ ડિસ્કનેક્ટ થઈ જશે. ગ્રાફ દ્વિદલીય હોય છે જો તેના શિરોબિંદુઓને બે જુદા જુદા રંગોથી રંગીન કરી શકાય, જેમ કે દરેક ધાર દરેક રંગનું એક અંતિમ બિંદુ ધરાવે છે. આલેખ ઘન (અથવા 3-નિયમિત) હોય છે જો દરેક શિરોબિંદુ બરાબર ત્રણ ધારોનું અંતિમ બિંદુ હોય. છેવટે, ગ્રાફ હેમિલ્ટોનિયન છે જો ત્યાં એક ચક્ર અસ્તિત્વમાં હોય જે તેના દરેક શિરોબિંદુઓમાંથી બરાબર એક જ વાર પસાર થાય છે. બાર્નેટનો અંદાજ જણાવે છે કે દરેક ઘન દ્વિપક્ષી બહુપક્ષીય આલેખ હેમિલ્ટોનિયન છે. સ્ટેનિટ્ઝના પ્રમેય અનુસાર, સમતલીય આલેખ બહિર્મુખ પોલિહેડ્રોનની ધાર અને શિરોબિંદુઓને રજૂ કરે છે જો અને માત્ર ત્યારે જ જો તે પોલિહેડ્રલ હોય. ત્રિ-પરિમાણીય પોલિહેડ્રોનનો ઘન આલેખ હોય છે જો અને માત્ર ત્યારે જ જો તે એક સરળ પોલિહેડ્રોન હોય. અને, પ્લેનર ગ્રાફ દ્વિપક્ષી હોય છે જો અને માત્ર ત્યારે જ, ગ્રાફના પ્લેનર એમ્બેડિંગમાં, તમામ ચહેરાના ચક્રની લંબાઈ સરખી હોય. તેથી, બાર્નેટના અનુમાનને સમકક્ષ સ્વરૂપમાં કહી શકાયઃ ધારો કે ત્રિ-પરિમાણીય સરળ બહિર્મુખ પોલિહેડ્રોન તેના દરેક ચહેરા પર સમાન સંખ્યામાં ધાર ધરાવે છે. પછી, અનુમાન મુજબ, પોલિહેડ્રોનનો આલેખ હેમિલ્ટોનિયન ચક્ર ધરાવે છે. ઇતિહાસ એવું અનુમાન કરે છે કે દરેક ઘન પોલિહેડ્રલ ગ્રાફ હેમિલ્ટોનિયન છે; આ ટેટના અનુમાન તરીકે જાણીતું બન્યું. જેમણે 46 શિરોબિંદુઓ સાથે પ્રતિકૂળ ઉદાહરણ બનાવ્યું હતું; અન્ય સંશોધકોને પાછળથી તેનાથી પણ નાના પ્રતિકૂળ ઉદાહરણો મળ્યા હતા. જો કે, આમાંથી કોઈ પણ જાણીતા પ્રતિકૂળ ઉદાહરણો દ્વિપક્ષી નથી. ટુટે પોતે અનુમાન લગાવ્યું હતું કે દરેક ઘન 3-જોડાયેલ દ્વિપક્ષી આલેખ હેમિલ્ટોનિયન છે, પરંતુ હોર્ટન આલેખ નામના પ્રતિકૂળ ઉદાહરણની શોધ દ્વારા આ ખોટો હોવાનું દર્શાવવામાં આવ્યું હતું. ટેટ અને ટુટ્ટેના અનુમાનોના નબળા સંયોજનનો પ્રસ્તાવ મૂક્યો હતો, જેમાં જણાવવામાં આવ્યું હતું કે દરેક દ્વિપક્ષી ઘન પોલિહેડ્રોન હેમિલ્ટોનિયન છે, અથવા, સમકક્ષ રીતે, કે ટેટના અનુમાનનું દરેક પ્રતિકૂળ ઉદાહરણ બિન-દ્વિપક્ષી છે. સમકક્ષ સ્વરૂપો દર્શાવે છે કે બાર્નેટનો અંદાજ ઉપરછલ્લી રીતે મજબૂત નિવેદનની સમકક્ષ છે, કે દ્વિપક્ષી ઘન પોલિહેડ્રોનના એક જ ચહેરા પર દરેક બે ધાર e અને f માટે, હેમિલ્ટોનિયન ચક્ર અસ્તિત્વમાં છે જેમાં e હોય છે પરંતુ તેમાં f નથી. સ્પષ્ટપણે, જો આ નિવેદન સાચું હોય, તો દરેક દ્વિપક્ષી ઘન પોલિહેડ્રોન હેમિલ્ટોનિયન ચક્ર ધરાવે છેઃ ફક્ત મનસ્વી રીતે e અને f પસંદ કરો. અન્ય દિશાઓમાં, કેલમન્સે દર્શાવ્યું હતું કે પ્રતિકૂળ ઉદાહરણને મૂળ બાર્નેટ અનુમાનના પ્રતિકૂળ ઉદાહરણમાં રૂપાંતરિત કરી શકાય છે. બાર્નેટનો અંદાજ એ નિવેદનની સમકક્ષ પણ છે કે દરેક ઘન દ્વિદલીય બહુપક્ષીય આલેખના બેવડાના શિરોબિંદુઓને બે ઉપગણમાં વિભાજિત કરી શકાય છે જેમના પ્રેરિત ઉપગણ વૃક્ષો છે. બેવડા આલેખમાં આવા વિભાજન દ્વારા પ્રેરિત કટ પ્રાથમિક આલેખમાં હેમિલ્ટોનિયન ચક્રને અનુરૂપ છે. આંશિક પરિણામો બાર્નેટના અનુમાનનું સત્ય અજ્ઞાત હોવા છતાં, કોમ્પ્યુટેશનલ પ્રયોગોએ દર્શાવ્યું છે કે 86 થી ઓછા શિરોબિંદુઓ સાથે કોઈ પ્રતિકૂળ ઉદાહરણ નથી. જો બાર્નેટનો અંદાજ ખોટો સાબિત થાય છે, તો દ્વિદલીય ઘન પોલિહેડ્રોન હેમિલ્ટોનિયન છે કે કેમ તે ચકાસવા માટે તે એન. પી.-પૂર્ણ હોવાનું દર્શાવી શકાય છે. જો સમતલીય આલેખ દ્વિપક્ષી અને ઘન હોય પરંતુ માત્ર જોડાણ 2 નો હોય, તો તે બિન-હેમિલ્ટોનિયન હોઈ શકે છે, અને આ આલેખ માટે હેમિલ્ટોનસિટી ચકાસવા માટે તે NP-પૂર્ણ છે. બીજું પરિણામ આના દ્વારા મેળવવામાં આવ્યું હતુંઃ જો બેવડો આલેખ વાદળી, લાલ અને લીલા રંગો સાથે શિરોબિંદુ-રંગીન હોઈ શકે છે, જેમ કે દરેક લાલ-લીલા ચક્રમાં 4 ડિગ્રીનો શિરોબિંદુ હોય, તો પ્રાથમિક આલેખ હેમિલ્ટોનિયન છે. સંબંધિત સમસ્યાઓ બાર્નેટનો સંબંધિત અનુમાન જણાવે છે કે દરેક ક્યુબિક પોલિહેડ્રલ ગ્રાફ જેમાં તમામ ચહેરાઓ છ કે તેથી ઓછી ધાર ધરાવે છે તે હેમિલ્ટોનિયન છે. કોમ્પ્યુટેશનલ પ્રયોગોએ દર્શાવ્યું છે કે, જો પ્રતિકૂળ ઉદાહરણ અસ્તિત્વમાં હોય, તો તેમાં 177 થી વધુ શિરોબિંદુઓ હોવા જોઈએ. આ અનુમાન દ્વારા સાબિત થયું હતું. આ બે અનુમાનોનું આંતરછેદ એ હશે કે દરેક દ્વિપક્ષી ઘન પોલિહેડ્રલ ગ્રાફ જેમાં તમામ ચહેરાઓ ચાર કે છ ધાર ધરાવે છે તે હેમિલ્ટોનિયન છે. આ વાત સાચી સાબિત થઈ હતી. નોંધો સંદર્ભો; સાયન્ટિફિક પેપર્સમાં પુનઃમુદ્રિત, વોલ્યુમ. II, પીપી. 85-98 બાહ્ય કડીઓ ઓપન પ્રોબ્લેમ ગાર્ડનમાં બાર્નેટના અનુમાન, રોબર્ટ સામલ, 2007. આલેખ સિદ્ધાંતમાં વણઉકેલાયેલી સમસ્યાઓના અનુમાન પ્લાનર આલેખ હેમિલ્ટોનિયન માર્ગો અને ચક્ર