Trémaux tree
આલેખ સિદ્ધાંતમાં, દિશાહીન આલેખનું ટ્રેમોક્સ વૃક્ષ એ ફેલાયેલા વૃક્ષનો એક પ્રકાર છે, જે ઊંડાઈ-પ્રથમ શોધ વૃક્ષોને સામાન્ય બનાવે છે. તેઓ એ ગુણધર્મ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે કે વૃક્ષની દરેક ધાર વૃક્ષમાં પૂર્વજ-વંશજોની જોડીને જોડે છે. ટ્રેમોક્સ વૃક્ષોનું નામ 19મી સદીના ફ્રેન્ચ લેખક ચાર્લ્સ પિયરે ટ્રેમોક્સના નામ પરથી રાખવામાં આવ્યું છે, જેમણે મેઝને ઉકેલવા માટેની વ્યૂહરચના તરીકે ઊંડાઈ-પ્રથમ શોધના સ્વરૂપનો ઉપયોગ કર્યો હતો. તેમને સામાન્ય ફેલાયેલા વૃક્ષો પણ કહેવામાં આવે છે, ખાસ કરીને અનંત આલેખના સંદર્ભમાં. બધા ઊંડાઈ-પ્રથમ શોધ વૃક્ષો અને બધા હેમિલ્ટોનિયન માર્ગો ટ્રેમોક્સ વૃક્ષો છે. મર્યાદિત આલેખમાં, દરેક ટ્રેમોક્સ વૃક્ષ એ ઊંડાઈ-પ્રથમ શોધ વૃક્ષ છે, પરંતુ ઊંડાઈ-પ્રથમ શોધ પોતે સ્વાભાવિક રીતે ક્રમિક હોવા છતાં, ટ્રેમોક્સ વૃક્ષો જટિલતા વર્ગ આરએનસીમાં રેન્ડમાઇઝ્ડ સમાંતર અલ્ગોરિધમ દ્વારા બનાવી શકાય છે. તેનો ઉપયોગ આલેખની વૃક્ષ-ઊંડાઈને વ્યાખ્યાયિત કરવા માટે અને આલેખ સમતલીય આલેખ છે કે કેમ તે ચકાસવા માટે ડાબી-જમણી સમતોલતા પરીક્ષણના ભાગ રૂપે થઈ શકે છે. આલેખના મોનડિક બીજા ક્રમના તર્કમાં ટ્રેમોક્સ વૃક્ષોનું લાક્ષણિકતા નિરૂપણ કોર્સેલના પ્રમેયનો ઉપયોગ કરીને બંધાયેલા ત્રિ-પહોળાઈના આલેખ માટે દિશાઓ સાથે સંકળાયેલા આલેખ ગુણધર્મોને અસરકારક રીતે ઓળખવાની મંજૂરી આપે છે. દરેક અનંત જોડાયેલા આલેખમાં ટ્રેમોક્સ વૃક્ષ હોતું નથી, અને દરેક અનંત ટ્રેમોક્સ વૃક્ષ ઊંડાઈ-પ્રથમ શોધ વૃક્ષ હોતું નથી. ટ્રેમોક્સ વૃક્ષો ધરાવતા આલેખને પ્રતિબંધિત સગીર દ્વારા વર્ગીકૃત કરી શકાય છે. અનંત ટ્રેમોક્સ વૃક્ષમાં આલેખના દરેક છેડા માટે બરાબર એક અનંત માર્ગ હોવો આવશ્યક છે, અને ટ્રેમોક્સ વૃક્ષનું અસ્તિત્વ આલેખની લાક્ષણિકતા ધરાવે છે, જેની ટોપોલોજીકલ પૂર્ણતા, દરેક છેડા માટે અનંત બિંદુ ઉમેરીને રચાય છે, તે મેટ્રિક જગ્યાઓ છે. વ્યાખ્યા અને ઉદાહરણો આલેખ માટે ટ્રેમોક્સ વૃક્ષ એ એક ફેલાયેલું વૃક્ષ છે, જેમાં દરેક ધાર માટે, બે અંતિમ બિંદુઓમાંથી એક છે અને તે બીજાનો પૂર્વજ છે. ફેલાયેલું વૃક્ષ બનવા માટે, તેણે માત્ર તેની ધારનો ઉપયોગ કરવો જોઈએ, અને દરેક શિરોબિંદુ વચ્ચે એક અનન્ય મર્યાદિત માર્ગ સાથે દરેક શિરોબિંદુ શામેલ કરવું જોઈએ. વધુમાં, આ વૃક્ષમાં પૂર્વજ-વંશના સંબંધને વ્યાખ્યાયિત કરવા માટે, તેના એક શિરોબિંદુને તેના મૂળ તરીકે નિયુક્ત કરવું આવશ્યક છે. જો મર્યાદિત આલેખમાં હેમિલ્ટોનિયન માર્ગ હોય, તો તે માર્ગને તેના બે અંતિમ બિંદુઓમાંથી એક પર રુટ કરવાથી ટ્રેમોક્સ વૃક્ષ ઉત્પન્ન થાય છે. આવા માર્ગ માટે, શિરોબિંદુઓની દરેક જોડી પૂર્વજો-વંશજોની જોડી છે. નીચે દર્શાવેલ આલેખમાં, ધાર 1-3,2-3 અને 3-4 ધરાવતું વૃક્ષ જ્યારે શિરોબિંદુ 1 અથવા શિરોબિંદુ 2 પર મૂળ ધરાવે છે ત્યારે તે ટ્રીમોક્સ વૃક્ષ છેઃ આલેખની દરેક ધાર વૃક્ષની છે સિવાય કે ધાર 1-2, જે (મૂળની આ પસંદગીઓ માટે) પૂર્વજો-વંશજોની જોડીને જોડે છે. જો કે, શિરોબિંદુ 3 અથવા શિરોબિંદુ 4 પર એક જ વૃક્ષને મૂળમાં મૂકતા મૂળ ધરાવતું વૃક્ષ ઉત્પન્ન થાય છે જે ટ્રેમોક્સ વૃક્ષ નથી, કારણ કે આ મૂળ સાથે 1 અને 2 હવે એકબીજાના પૂર્વજ અને વંશજ નથી. મર્યાદિત આલેખમાં અસ્તિત્વ દરેક મર્યાદિત જોડાયેલા દિશાહીન આલેખમાં ઓછામાં ઓછું એક ટ્રેમોક્સ વૃક્ષ હોય છે. ઊંડાણ-પ્રથમ શોધ કરીને અને દરેક શિરોબિંદુને (શોધના પ્રારંભિક શિરોબિંદુ સિવાય) અગાઉના શિરોબિંદુ સાથે જોડીને આવા વૃક્ષનું નિર્માણ કરી શકાય છે, જ્યાંથી તેની શોધ થઈ હતી. આ રીતે બાંધવામાં આવેલા વૃક્ષને ઊંડાઈ-પ્રથમ શોધ વૃક્ષ તરીકે ઓળખવામાં આવે છે. જો આલેખમાં મનસ્વી ધાર હોય, અને શોધ દ્વારા પહોંચવાના બે શિરોબિંદુઓમાંથી પહેલું હોય, તો તે ઊંડાણ-પ્રથમ શોધ વૃક્ષમાંથી ઉતરતા ઉપવૃક્ષા સાથે સંબંધિત હોવું જોઈએ, કારણ કે જ્યારે તે આ ઉપવૃક્ષા અન્વેષણ કરી રહ્યું હોય ત્યારે શોધ આવશ્યકપણે શોધી કાઢશે, કાં તો ઉપવૃક્ષા અન્ય શિરોબિંદુઓમાંથી એકમાંથી અથવા, તે નિષ્ફળ જાય તો, સીધાથી. દરેક મર્યાદિત ટ્રેમોક્સ વૃક્ષને ઊંડાઈ-પ્રથમ શોધ વૃક્ષ તરીકે ઉત્પન્ન કરી શકાય છેઃ જો તે મર્યાદિત આલેખનું ટ્રેમોક્સ વૃક્ષ હોય, અને ઊંડાઈ-પ્રથમ શોધ કોઈપણ અન્ય શિરોબિંદુઓનું અન્વેષણ કરતા પહેલા દરેક શિરોબિંદુના બાળકોની શોધ કરે, તો તે આવશ્યકપણે તેના ઊંડાઈ-પ્રથમ શોધ વૃક્ષ તરીકે ઉત્પન્ન થશે. સમાંતર રચના તે ટ્રેમોક્સ વૃક્ષને શોધવા માટે પી-પૂર્ણ છે જે ક્રમિક ઊંડાઈ-પ્રથમ શોધ અલ્ગોરિધમ દ્વારા મળી આવશે, જેમાં દરેક શિરોબિંદુના પડોશીઓને તેમની ઓળખ દ્વારા ક્રમમાં શોધવામાં આવે છે. તેમ છતાં, રેન્ડમાઇઝ્ડ સમાંતર અલ્ગોરિધમ દ્વારા એક અલગ ટ્રેમોક્સ વૃક્ષ શોધવું શક્ય છે, જે દર્શાવે છે કે ટ્રેમોક્સ વૃક્ષોનું નિર્માણ જટિલતા વર્ગ આરએનસી સાથે સંબંધિત છે. અલ્ગોરિધમ અન્ય રેન્ડમાઇઝ્ડ સમાંતર અલ્ગોરિધમ પર આધારિત છે, જે 0-1-ભારિત આલેખમાં લઘુતમ-વજનના સંપૂર્ણ મેળ શોધવા માટે છે. 1997 સુધીમાં, તે અજ્ઞાત રહ્યું કે શું ટ્રેમોક્સ વૃક્ષનું બાંધકામ જટિલતા વર્ગ એન. સી. માં નિર્ધારક સમાંતર અલ્ગોરિધમ દ્વારા કરી શકાય છે કે કેમ. જો મેળ એન. સી. માં મળી શકે છે, તો પછી ટ્રેમોક્સ વૃક્ષો પણ મળી શકે છે. તાર્કિક અભિવ્યક્તિ એ ગુણધર્મને વ્યક્ત કરવો શક્ય છે કે મૂળ શિરોબિંદુની પસંદગી સાથે ધારોનો સમૂહ ટ્રેમોક્સ વૃક્ષ બનાવે છે, ગ્રાફના મોનડિક બીજા ક્રમના તર્કમાં, અને વધુ ખાસ કરીને આ તર્કના સ્વરૂપમાં જેને MSO2 કહેવાય છે, જે શિરોબિંદુ અને ધાર સમૂહ બંને પર માત્રાત્મકતાને મંજૂરી આપે છે. આ ગુણધર્મને નીચેના ગુણધર્મોના સંયોજન તરીકે વ્યક્ત કરી શકાય છેઃ આલેખ અંદરની ધાર દ્વારા જોડાયેલ છે. આને તાર્કિક રીતે નિવેદન તરીકે વ્યક્ત કરી શકાય છે કે, આલેખના શિરોબિંદુઓના દરેક ખાલી ન હોય તેવા યોગ્ય સબસેટ માટે, આપેલ સબસેટમાં બરાબર એક અંતિમ બિંદુ સાથે એક ધાર અસ્તિત્વમાં છે. તે એસાયક્લિક છે. આને તાર્કિક રીતે નિવેદન તરીકે વ્યક્ત કરી શકાય છે કે ત્યાં કોઈ બિન-ખાલી સબસેટ અસ્તિત્વમાં નથી કે જેના માટે દરેક શિરોબિંદુ શૂન્ય અથવા તેની બે ધાર સાથે સંકળાયેલું હોય. દરેક ધાર પૂર્વજો-વંશજોની શિરોબિંદુઓની જોડીને અંદરથી જોડે છે. આ ત્યારે સાચું પડે છે જ્યારે બંને અંતિમ બિંદુઓ એક માર્ગ સાથે સંબંધિત હોય. તેને તાર્કિક રીતે આ નિવેદન તરીકે વ્યક્ત કરી શકાય છે કે, તમામ ધાર માટે, એક એવો ઉપસમૂહ અસ્તિત્વમાં છે કે જેમાં બરાબર બે શિરોબિંદુઓ, તેમાંથી એક, તેની એક ધાર સાથે સંલગ્ન હોય અને તેના બંને અંતિમ બિંદુઓ તેની ઓછામાં ઓછી એક ધાર સાથે સંલગ્ન હોય. એકવાર ટ્રેમોક્સ વૃક્ષને આ રીતે ઓળખવામાં આવે તે પછી, કોઈ પણ વ્યક્તિ આપેલા આલેખની દિશાને વર્ણવી શકે છે, મોનાડિક સેકન્ડ-ઓર્ડર લોજિકમાં પણ, કિનારીઓના સમૂહને સ્પષ્ટ કરીને જેની દિશા પૂર્વજોના અંતિમ બિંદુથી વંશજોના અંતિમ બિંદુ સુધી હોય છે. આ સમૂહની બહારની બાકીની ધાર બીજી દિશામાં હોવી જોઈએ. આ તકનીક દિશા નિર્દેશો સાથે સંકળાયેલા આલેખ ગુણધર્મોને મોનાડિક સેકન્ડ ઓર્ડર લોજિકમાં સ્પષ્ટ કરવાની મંજૂરી આપે છે, જે આ ગુણધર્મોને કોર્સેલના પ્રમેયનો ઉપયોગ કરીને બાઉન્ડેડ ટ્રીવિડ્થના આલેખ પર અસરકારક રીતે પરીક્ષણ કરવાની મંજૂરી આપે છે. સંબંધિત ગુણધર્મો જો આલેખમાં હેમિલ્ટોનિયન માર્ગ હોય, તો તે માર્ગ (તેના અંતિમ બિંદુઓમાંથી એક પર મૂળ ધરાવતો) પણ ટ્રેમોક્સ વૃક્ષ છે. દરેક ટ્રેમોક્સ વૃક્ષનું આ સ્વરૂપ હોય તેવા દિશાહીન આલેખમાં ચક્ર આલેખ, સંપૂર્ણ આલેખ અને સંતુલિત સંપૂર્ણ દ્વિપક્ષી આલેખ છે. ટ્રીમોક્સ વૃક્ષો વૃક્ષની ઊંડાઈના ખ્યાલ સાથે ગાઢ રીતે સંબંધિત છે. આલેખની વૃક્ષ-ઊંડાઈને સૌથી નાની સંખ્યા તરીકે વ્યાખ્યાયિત કરી શકાય છે, જેના માટે આલેખ અસ્તિત્વમાં છે, જેમાં ટ્રેમોક્સ વૃક્ષની ઊંડાઈ હોય છે, જેમ કે તેની પેટા આલેખ હોય છે. આલેખના કુટુંબમાં વૃક્ષની ઊંડાઈની સીમા, એવા માર્ગના અસ્તિત્વની સમકક્ષ હોય છે જે કુટુંબમાં આલેખના નાના આલેખ તરીકે ન આવી શકે. આલેખ પરની ઘણી હાર્ડ કોમ્પ્યુટેશનલ સમસ્યાઓમાં એલ્ગોરિધમ્સ હોય છે જે તેમના ઇનપુટ્સની વૃક્ષ-ઊંડાઈ દ્વારા પરિમાણિત કરવામાં આવે ત્યારે નિશ્ચિત-પરિમાણ ટ્રેક્ટેબલ હોય છે. આપેલ આલેખ સમતલીય છે કે કેમ તે ચકાસવા માટે ફ્રેસીક્સ-રોસેનસ્ટીહલ સમતલીયતાના માપદંડમાં ટ્રેમોક્સ વૃક્ષો પણ મુખ્ય ભૂમિકા ભજવે છે. આ માપદંડ અનુસાર, આલેખ સમતલ હોય છે, જો આપેલ ટ્રીમોક્સ વૃક્ષ માટે, બાકીની ધારને વૃક્ષની ડાબી અથવા જમણી બાજુએ સુસંગત રીતે મૂકી શકાય છે, જે અવરોધોને આધિન હોય છે જે સમાન પ્લેસમેન્ટવાળી ધારને એકબીજાને પાર કરતા અટકાવે છે. અનંત આલેખમાં અસ્તિત્વ દરેક અનંત આલેખમાં સામાન્ય ફેલાયેલું વૃક્ષ હોતું નથી. દાખલા તરીકે, શિરોબિંદુઓના અગણિત સમૂહ પર સંપૂર્ણ આલેખમાં એક નથીઃ સંપૂર્ણ આલેખમાં સામાન્ય ફેલાયેલું વૃક્ષ માત્ર એક માર્ગ હોઈ શકે છે, પરંતુ માર્ગમાં માત્ર ગણતરીપાત્ર સંખ્યામાં શિરોબિંદુઓ હોય છે. જો કે, શિરોબિંદુઓના ગણતરીપાત્ર સમૂહ પરના દરેક આલેખમાં સામાન્ય સ્પૅનિંગ ટ્રી હોય છે. ગણતરીપાત્ર આલેખમાં પણ, ઊંડાઈ-પ્રથમ શોધ આખરે સમગ્ર આલેખની શોધ કરવામાં સફળ ન થઈ શકે, અને દરેક સામાન્ય ફેલાયેલું વૃક્ષ ઊંડાઈ-પ્રથમ શોધ દ્વારા પેદા કરી શકાતું નથીઃ ઊંડાઈ-પ્રથમ શોધ વૃક્ષ બનવા માટે, ગણતરીપાત્ર સામાન્ય ફેલાયેલું વૃક્ષ માત્ર એક અનંત માર્ગ અથવા અનંત સંખ્યાબંધ બાળકો (અને બંને નહીં) સાથે એક નોડ ધરાવતું હોવું જોઈએ. જો અનંત આલેખમાં સામાન્ય ફેલાયેલું વૃક્ષ હોય, તો દરેક જોડાયેલ આલેખ પણ નાના હોય છે. તે આમાંથી અનુસરે છે કે જે આલેખમાં સામાન્ય રીતે ફેલાયેલા વૃક્ષો હોય છે તે પ્રતિબંધિત સગીર દ્વારા લાક્ષણિકતા ધરાવે છે. પ્રતિબંધિત સગીરના બે વર્ગોમાંથી એકમાં દ્વિપક્ષી આલેખ હોય છે જેમાં દ્વિપક્ષીકરણની એક બાજુ ગણવા યોગ્ય હોય છે, બીજી બાજુ અગણિત હોય છે અને દરેક શિરોબિંદુ અનંત ડિગ્રી ધરાવે છે. પ્રતિબંધિત સગીરના અન્ય વર્ગમાં એરોન્ઝાજન વૃક્ષોમાંથી મેળવેલા ચોક્કસ આલેખનો સમાવેશ થાય છે. આ લાક્ષણિકતાની વિગતો ગણિતને ઔપચારિક બનાવવા માટે ઉપયોગમાં લેવાતા સમૂહ-સૈદ્ધાંતિક સ્વયંસિદ્ધીકરણની પસંદગી પર આધારિત છે. ખાસ કરીને, સમૂહ સિદ્ધાંતના નમૂનાઓમાં કે જેના માટે માર્ટિનનો સિદ્ધાંત સાચો છે અને સાતત્ય પૂર્વધારણા ખોટી છે, આ લાક્ષણિકતામાં દ્વિપક્ષી આલેખના વર્ગને એક પ્રતિબંધિત ગૌણ દ્વારા બદલી શકાય છે. જો કે, એવા નમૂનાઓ માટે કે જેમાં સાતત્ય પૂર્વધારણા સાચી છે, આ વર્ગમાં એવા આલેખ છે જે નાના ક્રમમાં એકબીજા સાથે અજોડ છે. અંત અને માપનક્ષમતા સામાન્ય ફેલાયેલા વૃક્ષો પણ અનંત આલેખના અંત સાથે નજીકથી સંબંધિત છે, અનંત માર્ગોના સમાનતા વર્ગો, જે સહજ ભાવે, સમાન દિશામાં અનંત તરફ જાય છે. જો આલેખમાં સામાન્ય ફેલાયેલું વૃક્ષ હોય, તો આ વૃક્ષમાં આલેખના દરેક છેડા માટે બરાબર એક અનંત માર્ગ હોવો જોઈએ. અનંત આલેખનો ઉપયોગ આલેખને એક સરળ સંકુલ તરીકે જોઈને અને આલેખના દરેક છેડા માટે અનંત પર એક બિંદુ ઉમેરીને ટોપોલોજિકલ જગ્યા બનાવવા માટે કરી શકાય છે. આ ટોપોલોજી સાથે, ગ્રાફમાં સામાન્ય ફેલાયેલું વૃક્ષ હોય છે જો અને માત્ર ત્યારે જ જો તેના શિરોબિંદુઓના સમૂહને બંધ સમૂહોના ગણતરીપાત્ર જોડાણમાં વિઘટિત કરી શકાય. વધુમાં, આ ટોપોલોજિકલ જગ્યાને મેટ્રિક જગ્યા દ્વારા રજૂ કરી શકાય છે જો અને માત્ર ત્યારે જ જો ગ્રાફમાં સામાન્ય ફેલાયેલું વૃક્ષ હોય. સંદર્ભ આલેખ સિદ્ધાંત ઓબ્જેક્ટ્સ વૃક્ષનો વિસ્તાર આલેખ લઘુ સિદ્ધાંત અનંત આલેખ