Euler tour technique
યુલર પ્રવાસ તકનીક (ETT), જેનું નામ લિયોનહાર્ડ યુલરના નામ પરથી રાખવામાં આવ્યું છે, તે વૃક્ષોનું પ્રતિનિધિત્વ કરવા માટે આલેખ સિદ્ધાંતમાં એક પદ્ધતિ છે. વૃક્ષને નિર્દેશિત આલેખ તરીકે જોવામાં આવે છે જેમાં વૃક્ષની દરેક ધાર માટે બે નિર્દેશિત ધાર હોય છે. પછી વૃક્ષને નિર્દેશિત આલેખના યુલરિયન સર્કિટ તરીકે રજૂ કરી શકાય છે, જેને વૃક્ષના યુલર ટૂર રિપ્રેઝન્ટેશન (ઇટીઆર) તરીકે ઓળખવામાં આવે છે. ETT એલ્ગોરિધમિક ગ્રાફ થિયરીમાં સામાન્ય સમસ્યાઓના ઉકેલોની કાર્યક્ષમ, સમાંતર ગણતરી માટે પરવાનગી આપે છે. તે 1984માં ટાર્જન અને વિશકિન દ્વારા રજૂ કરવામાં આવ્યું હતું. બાંધકામને બાજુઓના સમૂહ તરીકે પ્રસ્તુત કરાયેલ દિશાહીન વૃક્ષને જોતાં, યુલર પ્રવાસ પ્રતિનિધિત્વ (ETR) ને નીચે પ્રમાણે સમાંતર રીતે બનાવી શકાય છેઃ આપણે દિશા નિર્દેશિત ધારની સમપ્રમાણ સૂચિ બનાવીએ છીએઃ વૃક્ષની દરેક દિશાહીન ધાર {u, v} માટે, ધાર સૂચિમાં (u, v) અને (v, u) દાખલ કરો. ધારની સૂચિને લેક્સિકોગ્રાફિક રીતે ગોઠવો. (અહીં આપણે ધારીએ છીએ કે વૃક્ષની ગાંઠો ક્રમબદ્ધ છે, અને મૂળ આ ક્રમમાં પ્રથમ તત્વ છે.) દરેક નોડ (જેને આગળ કહેવામાં આવે છે) માટે નિકટતા સૂચિની રચના કરો અને નોડ્સમાંથી નિકટતા સૂચિની પ્રથમ એન્ટ્રીઓ (જેને પ્રથમ કહેવામાં આવે છે) માટે નકશો બનાવોઃ સૂચિમાં દરેક ધાર (યુ, વી) માટે, સમાંતર બનાવોઃ જો અગાઉની ધાર (x, y) પાસે x ≤ યુ હોય, એટલે કે. એક અલગ નોડથી શરૂ થાય છે, પહેલા સુયોજિત કરો (યુ) = (યુ, વી) અન્યથા જો x = યુ, એટલે કે. તે જ નોડથી શરૂ કરીને, આગામી (x, y) = (u, v) સુયોજિત કરો. યુલર પ્રવાસ ક્રમમાં તમામ ધાર (u, v) માટે પોઇન્ટર સક્ (u, v) ને નીચે આપેલા નિયમ અનુસાર સમાંતર સુયોજિત કરીને ધાર સૂચિ (જેને સક્ કહેવાય છે) બનાવોઃ પરિણામી સૂચિ સક્ ગોળાકાર હશે. જો વૃક્ષમાં n ગાંઠો હોય તો એકંદર રચનામાં W (n) = O (સૉર્ટ (n)) (n વસ્તુઓને સમાંતર રીતે સૉર્ટ કરવામાં લાગતો સમય) કામ લે છે, કારણ કે વૃક્ષોમાં કિનારીઓની સંખ્યા ગાંઠોની સંખ્યા કરતાં એક ઓછી હોય છે. જો વૃક્ષનું મૂળ હોય, તો આપણે તે મૂળ પર ગોળાકાર સૂચિને વિભાજિત કરી શકીએ છીએ. તે કિસ્સામાં, આપણે એડવાન્સ અને રીટ્રીટ ધારની વાત કરી શકીએ છીએઃ યુ, વી નોડ્સની જોડી આપવામાં આવે તો, ઇટીઆરમાં (યુ, વી) અથવા (વી, યુ) ની પ્રથમ ઘટનાને એડવાન્સ ધાર કહેવામાં આવે છે, અને બીજી ઘટનાને રીટ્રીટ ધાર કહેવામાં આવે છે. આ અંતઃપ્રેરણાને અપીલ કરે છે કે પ્રથમ વખત આવી ધારને પાર કરવામાં આવે ત્યારે મૂળનું અંતર વધે છે, જ્યારે બીજી વખત અંતર ઘટે છે. નવા મૂળ પર ગોળાકાર સૂચિને વિભાજિત કરીને વૃક્ષને ફરીથી ગોઠવવાનું સતત સમય O (1) માં કરી શકાય છે. એપ્લિકેશન્સ નીચેની તમામ સમસ્યાઓ O (ઉપસર્ગ રકમ (n)) માં ઉકેલી શકાય છે (n વસ્તુઓની સૂચિ માટે ઉપસર્ગ રકમ સમસ્યાને સમાંતર ઉકેલવામાં જે સમય લાગે છે): એડવાન્સ અને રીટ્રીટ ધારને વર્ગીકૃત કરવીઃ ETR પર લિસ્ટ રેન્કિંગ કરો અને પરિણામને દ્વિ-પરિમાણીય એરે A માં સાચવો. પછી (યુ, વી) એ એ (યુ, વી) <એ (વી, યુ) ની અગાઉની ધાર છે, અને અન્યથા પીછેહઠની ધાર છે. દરેક નોડનું સ્તર નક્કી કરોઃ ETR પર ઉપસર્ગ સરવાળો કરો, જ્યાં દરેક અગાઉથી ધાર 1 તરીકે ગણવામાં આવે છે, અને દરેક પીછેહઠ ધાર-1 તરીકે ગણવામાં આવે છે. પછી એડવાન્સ એજ (યુ, વી) પરનું મૂલ્ય એ વીનું સ્તર છે. વી પર મૂળ ધરાવતા સબટ્રીમાં ગાંઠોની સંખ્યાઃ ધારો કે વીનો પેરેન્ટ યુ છે, એડવાન્સ એજ (યુ, વી) અને રીટ્રીટ એજ (વી, યુ) સમાંતર રીતે નક્કી કરો, અને પછી ઉપસર્ગ રકમનો ઉપયોગ કરીને (યુ, વી) અને (વી, યુ) વચ્ચેની એડવાન્સ એજની સંખ્યાની ગણતરી કરો. નોડ v નો ઊંડાઈ-પ્રથમ શોધ અનુક્રમણિકાઃ (u, v) સુધી અને તેના સહિત અગાઉથી ધારની સંખ્યાની ગણતરી કરો. બે ગાંઠોના સૌથી ઓછા સામાન્ય પૂર્વજ નક્કી કરો. યુલર પ્રવાસ વૃક્ષો હેન્ઝિંગર અને કિંગ તેના યુલર પ્રવાસને સંતુલિત દ્વિસંગી શોધ વૃક્ષમાં રાખીને આપેલ વૃક્ષનું પ્રતિનિધિત્વ કરવાનું સૂચન કરે છે, જે પ્રવાસમાં અનુક્રમણિકા દ્વારા ચાવીરૂપ છે. તેથી ઉદાહરણ તરીકે, ઉપરના ઉદાહરણમાં અસંતુલિત વૃક્ષ, 7 ગાંઠો ધરાવતું, 14 ગાંઠો સાથે સંતુલિત દ્વિસંગી વૃક્ષ દ્વારા રજૂ કરવામાં આવશે, દરેક વખતે દરેક ગાંઠો પ્રવાસ પર દેખાય ત્યારે એક. આપણે ET વૃક્ષોના સંગ્રહનો ઉપયોગ કરીને જંગલ (એક ચક્રીય આલેખ) નું પ્રતિનિધિત્વ કરી શકીએ છીએ-એક વન વૃક્ષ માટે એક ET વૃક્ષ. આ રજૂઆત આપણને આ પ્રશ્નનો ઝડપથી જવાબ આપવા માટે પરવાનગી આપે છે "નોડ v નું મૂળ શું છે?" માત્ર ET વૃક્ષના પ્રથમ નોડ પર જઈને (કારણ કે ET વૃક્ષમાં ગાંઠો યુલર પ્રવાસમાં તેમના સ્થાન દ્વારા કી કરવામાં આવે છે, અને રૂટ એ પ્રવાસમાં પ્રથમ અને છેલ્લો નોડ છે). જ્યારે રજૂ થયેલ જંગલને અપડેટ કરવામાં આવે છે (દા. ત. બે વૃક્ષોને એક જ વૃક્ષ સાથે જોડીને અથવા એક વૃક્ષને બે વૃક્ષોમાં વિભાજીત કરીને), સંબંધિત યુલર-ટૂર માળખું સમય O (લોગ (એન)) માં સુધારી શકાય છે. કડી/કાપેલા વૃક્ષો સમાન કામગીરીની બાંયધરી ધરાવે છે. જ્યારે એલ. સી. વૃક્ષો વૃક્ષના માર્ગો પર એકત્રીકરણ જાળવવા માટે સારા છે (જે તેને નેટવર્ક ફ્લો અલ્ગોરિધમ્સમાં સારી પસંદગીનું ડેટા માળખું બનાવે છે), ET વૃક્ષો સબટ્રીઝ પર એકંદર માહિતી રાખવામાં વધુ સારા છે. સંદર્ભો ગ્રાફ અલ્ગોરિધમ્સ સમાંતર કમ્પ્યુટિંગ