Gilbert–Pollack conjecture
ગણિતમાં, ગિલ્બર્ટ-પોલક અનુમાન એ યુક્લિડિયન સમતલમાં સમાન બિંદુ સમૂહો માટે સ્ટેઇનર વૃક્ષોની લંબાઈ અને યુક્લિડિયન લઘુત્તમ ફેલાયેલા વૃક્ષોના ગુણોત્તર પર એક અપ્રમાણિત અનુમાન છે. 1968માં એડગર ગિલ્બર્ટ અને હેનરી ઓ. પોલક દ્વારા તેની દરખાસ્ત કરવામાં આવી હતી. નિવેદન સમતલમાં બિંદુઓના સમૂહ માટે, બિંદુઓને જોડતા રેખા ખંડોનું સૌથી નાનું નેટવર્ક, જેમાં અંતિમ બિંદુઓ તરીકે માત્ર આપેલ બિંદુઓ હોય છે, તે સમૂહનું યુક્લિડિયન લઘુત્તમ ફેલાયેલું વૃક્ષ છે. વધારાના અંતિમ બિંદુઓનો ઉપયોગ કરીને ટૂંકા નેટવર્કનું નિર્માણ કરવું શક્ય બની શકે છે, જે આપેલ બિંદુ સમૂહમાં હાજર નથી. આ વધારાના બિંદુઓને સ્ટેઇનર પોઇન્ટ કહેવામાં આવે છે અને તેનો ઉપયોગ કરીને બનાવી શકાય તેવા સૌથી ટૂંકા નેટવર્કને સ્ટેઇનર મિનિમમ ટ્રી કહેવામાં આવે છે. સ્ટેઇનર ગુણોત્તર એ તમામ બિંદુ સમૂહો પર, યુક્લિડિયન લઘુત્તમ વૃક્ષની લંબાઈ અને સ્ટેઇનર લઘુત્તમ વૃક્ષના ગુણોત્તરનો સર્વોચ્ચ ગુણોત્તર છે. કારણ કે સ્ટેઇનર લઘુત્તમ વૃક્ષ ટૂંકા હોય છે, આ ગુણોત્તર હંમેશા એક કરતા વધારે હોય છે. સ્ટેઇનર ગુણોત્તર પરની નીચલી સીમા એકમ બાજુની લંબાઈના સમબાહુ ત્રિકોણના શિરોબિંદુઓ પર ત્રણ બિંદુઓ દ્વારા પૂરી પાડવામાં આવે છે. આ ત્રણ બિંદુઓ માટે, યુક્લિડિયન લઘુત્તમ ફેલાયેલું વૃક્ષ ત્રિકોણની બે ધારનો ઉપયોગ કરે છે, જેની કુલ લંબાઈ બે છે. સ્ટેઇનર લઘુત્તમ વૃક્ષ ત્રણેય બિંદુઓને ત્રિકોણના કેન્દ્રમાં સ્ટેઇનર બિંદુ સાથે જોડે છે, જેની કુલ લંબાઈ નાની હોય છે. આ ઉદાહરણને કારણે, સ્ટેઇનર ગુણોત્તર ઓછામાં ઓછો હોવો જોઈએ. ગિલ્બર્ટ-પોલક અનુમાન જણાવે છે કે આ ઉદાહરણ સ્ટેઇનર ગુણોત્તર માટે સૌથી ખરાબ સ્થિતિ છે, અને આ ગુણોત્તર સમાન છે. એટલે કે, યુક્લિડિયન સમતલમાં નિર્ધારિત દરેક મર્યાદિત બિંદુ માટે, યુક્લિડિયન લઘુત્તમ ફેલાયેલું વૃક્ષ સ્ટેઇનર લઘુત્તમ વૃક્ષની લંબાઈ કરતાં વધુ ન હોઈ શકે. આ અનુમાન ડિંગ-ઝુ ડુ અને ફ્રેન્ક ક્વાંગ-મિંગ હ્વાંગ દ્વારા તેના પુરાવા માટે પ્રખ્યાત છે, જે પાછળથી ગંભીર અંતર હોવાનું બહાર આવ્યું છે. અપૂર્ણ ડુ અને હ્વાંગ પરિણામના આધારે, જે. હાયમ રુબિનસ્ટીન અને જિયા એફ. વેંગે તારણ કાઢ્યું હતું કે સ્ટેઇનર ગુણોત્તર પણ સતત વળાંકના 2-પરિમાણીય ગોળા માટે છે, પરંતુ ડુ અને હ્વાંગના મૂળ પરિણામમાં અંતરને કારણે, રુબિનસ્ટીન અને વેંગનું પરિણામ પણ હવે હજુ સુધી સાબિત થયું નથી તેવું માનવામાં આવે છે. સંદર્ભો આલેખ સિદ્ધાંતમાં વણઉકેલાયેલી સમસ્યાઓના અનુમાન કોમ્પ્યુટર વિજ્ઞાનમાં વણઉકેલાયેલી સમસ્યાઓ ભૌમિતિક અલ્ગોરિધમ્સ સંયુક્ત ઓપ્ટિમાઇઝેશન મેટ્રિક ભૂમિતિ