Thrackle
થ્રેકલ એ પ્લેનમાં ગ્રાફનું એમ્બેડિંગ છે જેમાં દરેક ધાર જોર્ડન ચાપ છે અને દરેક જોડી ધાર બરાબર એક જ વાર મળે છે. ધાર કાં તો એક સામાન્ય અંતિમ બિંદુ પર મળી શકે છે, અથવા, જો તેમની પાસે કોઈ સામાન્ય અંતિમ બિંદુઓ ન હોય, તો તેમના આંતરિક ભાગમાં એક બિંદુ પર. પછીના કિસ્સામાં, તેઓએ તેમના આંતરછેદ બિંદુ પર પાર કરવું આવશ્યક છેઃ આંતરછેદ ત્રાંસા હોવો આવશ્યક છે. રેખીય થ્રેકલ એ એવી રીતે દોરવામાં આવેલી થ્રેકલ છે કે તેની ધાર સીધી રેખાના ભાગો હોય છે. પોલ એર્ડસે અવલોકન કર્યું તેમ, દરેક રેખીય થ્રેકલમાં શિરોબિંદુઓ જેટલી ધાર હોય છે. જો શિરોબિંદુ v ત્રણ અથવા વધુ ધાર vw, vx અને vy સાથે જોડાયેલ હોય, તો તેમાંથી ઓછામાં ઓછી એક ધાર (જેમ કે vw) એક રેખા પર આવેલી હોય છે જે અન્ય બે ધારને અલગ કરે છે. પછી, ડબલ્યુ પાસે એક ડિગ્રી હોવી આવશ્યક છે, કારણ કે ડબલ્યુ પર સમાપ્ત થતો કોઈ પણ રેખા ખંડ, વીડબલ્યુ સિવાય, વીએક્સ અને વીવાય બંનેને સ્પર્શ કરી શકતો નથી. ધાર અને શિરોબિંદુઓની સંખ્યા વચ્ચેના તફાવતને બદલ્યા વિના, ડબલ્યુ અને વીડબ્લ્યુને દૂર કરવાથી નાની થ્રેકલ ઉત્પન્ન થાય છે. આ રીતે દૂર કર્યા પછી એક થ્રેકલ તરફ દોરી જાય છે જેમાં દરેક શિરોબિંદુને વધુમાં વધુ બે પડોશીઓ હોય છે, હાથ મિલાવતા લેમ્મા દ્વારા ધારની સંખ્યા મહત્તમ શિરોબિંદુઓની સંખ્યા હોય છે. એર્ડોસના પુરાવાના આધારે, કોઈ અનુમાન કરી શકે છે કે દરેક રેખીય થ્રેકલ એક સ્યુડોફોરેસ્ટ છે. વિષમ લંબાઈના દરેક ચક્રને રેખીય થ્રેકલ બનાવવા માટે ગોઠવી શકાય છે, પરંતુ સમ-લંબાઈના ચક્ર માટે આ શક્ય નથી, કારણ કે જો ચક્રની એક ધાર મનસ્વી રીતે પસંદ કરવામાં આવે તો અન્ય ચક્ર શિરોબિંદુઓ આ ધાર દ્વારા રેખાની વિરુદ્ધ બાજુઓ પર વારાફરતી આવેલા હોવા જોઈએ. માઇક પર્લેસે બીજો સરળ પુરાવો આપ્યો હતો કે રેખીય થ્રેકલમાં મહત્તમ n ધાર હોય છે, જે એ હકીકત પર આધારિત છે કે રેખીય થ્રેકલમાં દરેક ધારનો અંતિમ બિંદુ હોય છે, જેના પર ધાર મહત્તમ 180°ના ખૂણા સુધી વિસ્તરે છે, અને જેના માટે તે આ ગાળામાં ઘડિયાળની દિશામાં સૌથી વધુ ધાર હોય છે. કારણ કે, જો નહીં, તો ત્યાં બે ધાર હશે, જે ધારની વિરુદ્ધ અંતિમ બિંદુઓ સાથે જોડાયેલી હશે અને ધાર દ્વારા રેખાની વિરુદ્ધ બાજુએ પડેલી હશે, જે એકબીજાને પાર કરી શકતી ન હતી. પરંતુ દરેક શિરોબિંદુમાં માત્ર એક જ ધારના સંદર્ભમાં આ ગુણધર્મ હોઈ શકે છે, તેથી ધારની સંખ્યા શિરોબિંદુઓની સંખ્યા જેટલી જ હોય છે. એર્ડોસે પણ અવલોકન કર્યું છે તેમ, બિંદુ સમૂહના વ્યાસને સમજતા બિંદુઓની જોડીનો સમૂહ એક રેખીય થ્રેકલ બનાવવો જોઈએઃ કોઈ પણ બે વ્યાસ એકબીજાથી અલગ ન હોઈ શકે, કારણ કે જો તેઓ હોત તો તેમના ચાર અંતિમ બિંદુઓ બે અલગ ધાર કરતાં દૂરના અંતરે એક જોડી ધરાવતા હોત. આ કારણોસર, સમતલમાં n બિંદુઓના દરેક સમૂહમાં મહત્તમ n વ્યાસ જોડી હોઈ શકે છે, જે 1934માં હેઇન્ઝ હોપ્ફ અને એરિકા પેન્વિટ્ઝ દ્વારા પૂછવામાં આવેલા પ્રશ્નનો જવાબ આપે છે. એન્ડ્રુ વેઝસોનીએ ઉચ્ચ પરિમાણોમાં વ્યાસ જોડીઓની સંખ્યા પર અનુમાન લગાવ્યું છે, જે આ સમસ્યાને સામાન્ય બનાવે છે. કોમ્પ્યુટેશનલ ભૂમિતિમાં, ફરતી કેલિપર્સની પદ્ધતિનો ઉપયોગ બહિર્મુખ સ્થિતિમાં બિંદુઓના કોઈપણ સમૂહમાંથી રેખીય થ્રેકલ બનાવવા માટે થઈ શકે છે, જે બિંદુઓની જોડી જોડે છે જે બિંદુઓના બહિર્મુખ પત્થરો સાથે સમાંતર રેખાઓને ટેકો આપે છે. આ આલેખમાં સબગ્રાફ તરીકે વ્યાસ જોડીનો થ્રેકલ છે. રેઇનહાર્ટ બહુકોણનો વ્યાસ રેખીય થ્રેકલ બનાવે છે. રેખીય થ્રેકલની ગણતરીનો ઉપયોગ સૌથી મોટી નાની બહુકોણ સમસ્યાને ઉકેલવા માટે થઈ શકે છે, તેના વ્યાસને સંબંધિત મહત્તમ વિસ્તાર સાથે એન-ગોન શોધવા માટે. થ્રેકલ અનુમાન જ્હોન એચ. કોનવેએ અનુમાન લગાવ્યું હતું કે, કોઈપણ થ્રેકલમાં, ધારની સંખ્યા શિરોબિંદુઓની સંખ્યા જેટલી જ હોય છે. કોનવેએ પોતે પરિભાષા પાથ અને સ્પોટ્સ (અનુક્રમે ધાર અને શિરોબિંદુઓ માટે) નો ઉપયોગ કર્યો હતો, તેથી કોનવેના થ્રેકલ અનુમાનને મૂળ રૂપે દરેક થ્રેકલમાં પાથ જેટલા ઓછામાં ઓછા ઘણા ફોલ્લીઓ હોય છે તે સ્વરૂપમાં જણાવવામાં આવ્યું હતું. કોનવેએ આ અનુમાનને સાબિત કરવા અથવા નકારી કાઢવા માટે $1000 ઇનામની ઓફર કરી હતી, જેમાં કોનવેની 99-ગ્રાફ સમસ્યા, ડેન્ઝર સેટના લઘુતમ અંતર અને ચાલ 16 પછી સિલ્વર સિક્કાઓના વિજેતા સહિત ઇનામની સમસ્યાઓના સમૂહના ભાગ રૂપે. તેવી જ રીતે, થ્રેકલ અનુમાન કહી શકાય કારણ કે દરેક થ્રેકલ એક સ્યુડોફોરેસ્ટ છે. વધુ સ્પષ્ટ રીતે, જો થ્રેકલ અનુમાન સાચું હોય, તો થ્રેકલને વુડલના પરિણામ દ્વારા બરાબર વર્ગીકૃત કરી શકાય છેઃ તે સ્યુડોફોરેસ્ટ છે જેમાં લંબાઈ ચારનું કોઈ ચક્ર નથી અને વધુમાં વધુ એક વિચિત્ર ચક્ર છે. તે સાબિત થયું છે કે C4 સિવાયના દરેક ચક્ર આલેખમાં થ્રેકલ એમ્બેડિંગ હોય છે, જે દર્શાવે છે કે અનુમાન તીક્ષ્ણ છે. એટલે કે, ત્યાં માર્ગો જેટલા જ સ્થળો ધરાવતા થ્રેકલ છે. બીજી ચરમસીમાએ, સૌથી ખરાબ સ્થિતિ એ છે કે સ્થળોની સંખ્યા રસ્તાઓની સંખ્યા કરતા બમણી છે; આ પણ પ્રાપ્ય છે. થ્રેકલ અનુમાન એવી રીતે દોરેલા થ્રેકલ માટે સાચું હોવાનું જાણીતું છે કે દરેક ધાર એક એક્સ-મોનોટોન વળાંક છે, જે દરેક ઊભી રેખા દ્વારા વધુમાં વધુ એક વાર પાર થાય છે. જાણીતી સીમાઓએ સાબિત કર્યું કે દરેક દ્વિપક્ષી થ્રેકલ એક સમતલીય આલેખ છે, જો કે સમતલીય રીતે દોરવામાં આવ્યું નથી. પરિણામે, તેઓ દર્શાવે છે કે n શિરોબિંદુઓ સાથેના દરેક થ્રેકલેબલ ગ્રાફમાં મહત્તમ 2n−3 ધાર હોય છે. ત્યારથી, આ સીમા ઘણી વખત સુધારવામાં આવી છે. પ્રથમ, તે સુધારીને 3 (n−1)/2 કરવામાં આવ્યું હતું, અને અન્ય સુધારો આશરે 1.428n ની સીમા તરફ દોરી ગયો હતો. વધુમાં, પછીના પરિણામને સાબિત કરવા માટે ઉપયોગમાં લેવાતી પદ્ધતિ કોઈપણ ε> 0 માટે એક મર્યાદિત અલ્ગોરિધમ આપે છે જે કાં તો (1 + ε) n ની મર્યાદામાં સુધારો કરે છે અથવા અનુમાનને નકારી કાઢે છે. વર્તમાન રેકોર્ડ આના કારણે છે, જેણે 1.3984n નો બાઉન્ડ સાબિત કર્યો હતો. જો અનુમાન ખોટું હોય, તો ન્યૂનતમ પ્રતિ-ઉદાહરણમાં શિરોબિંદુ વહેંચતા બે સમ ચક્રોનું સ્વરૂપ હશે. તેથી, અનુમાનને સાબિત કરવા માટે, તે સાબિત કરવા માટે પૂરતું હશે કે આ પ્રકારના આલેખ થ્રેકલ તરીકે દોરી શકાતા નથી. સંદર્ભો બાહ્ય કડીઓ thrackle.org-સમસ્યા વિશેની વેબસાઇટ અનુમાન ટોપોલોજિકલ ગ્રાફ સિદ્ધાંત ભૌમિતિક આંતરછેદ