Ear decomposition
આલેખ સિદ્ધાંતમાં, દિશાહીન આલેખ G નો કાન એ એક માર્ગ P છે જ્યાં માર્ગના બે અંતિમ બિંદુઓ એક સાથે આવી શકે છે, પરંતુ જ્યાં અન્યથા ધાર અથવા શિરોબિંદુઓનું પુનરાવર્તન કરવાની મંજૂરી નથી, તેથી P ના દરેક આંતરિક શિરોબિંદુ G માં બે ડિગ્રી ધરાવે છે. વધુમાં, મોટાભાગના કિસ્સાઓમાં ક્રમમાં પ્રથમ કાન એક ચક્ર હોવો જોઈએ. ખુલ્લા કાનનું વિઘટન અથવા યોગ્ય કાનનું વિઘટન એ કાનનું વિઘટન છે જેમાં પ્રથમ પછી દરેક કાનના બે અંતિમ બિંદુઓ એકબીજાથી અલગ હોય છે. કાનના વિઘટનનો ઉપયોગ કેટલાક મહત્વપૂર્ણ ગ્રાફ વર્ગોને લાક્ષણિકતા આપવા માટે અને કાર્યક્ષમ ગ્રાફ અલ્ગોરિધમ્સના ભાગ રૂપે થઈ શકે છે. તેમને આલેખથી માંડીને મેટ્રોઇડ સુધી પણ સામાન્યીકૃત કરી શકાય છે. આલેખ વર્ગોની લાક્ષણિકતા આલેખના કેટલાક મહત્વપૂર્ણ વર્ગોને ચોક્કસ પ્રકારના કાનના વિઘટન ધરાવતા આલેખ તરીકે વર્ગીકૃત કરી શકાય છે. ગ્રાફ જોડાણ જો કોઈપણ (k−1) શિરોબિંદુઓને દૂર કરવાથી જોડાયેલ સબગ્રાફ નીકળી જાય તો ગ્રાફ k-વર્ટેક્સ-જોડાયેલ હોય છે, અને જો કોઈપણ (k−1) ધારને દૂર કરવાથી જોડાયેલ સબગ્રાફ નીકળી જાય તો k-ધાર-જોડાયેલ હોય છે. નીચેનું પરિણામ આના કારણે છેઃ સાથેનો આલેખ 2-વર્ટેક્સ-જોડાયેલ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં ખુલ્લા કાનનું વિઘટન હોય. નીચેનું પરિણામ આના કારણે છેઃ ગ્રાફ 2-ધાર-જોડાયેલ હોય છે જો અને માત્ર ત્યારે જ જો તેમાં કાનનું વિઘટન હોય. બંને કિસ્સાઓમાં કાનની સંખ્યા આવશ્યકપણે આપેલ આલેખના સર્કિટ ક્રમની બરાબર હોય છે. રોબિન્સે રોબિન્સ પ્રમેયને સાબિત કરવા માટે એક સાધન તરીકે 2-ધાર સાથે જોડાયેલા આલેખના કાનના વિઘટનની રજૂઆત કરી હતી, કે આ બરાબર એવા આલેખ છે જેને મજબૂત રીતે જોડાયેલ દિશા આપી શકાય છે. કાનના વિઘટન પર વ્હિટની અને રોબિન્સના અગ્રણી કાર્યને કારણે, કાનના વિઘટનને કેટલીકવાર વ્હિટની-રોબિન્સ સંશ્લેષણ પણ કહેવામાં આવે છે. બિન-વિભાજીત કાનનું વિઘટન એ ખુલ્લા કાનનું વિઘટન છે, જેમ કે, માત્ર એક અપવાદ સાથે દરેક શિરોબિંદુ વી માટે, વી પાસે એક પાડોશી છે જેનો વિઘટનમાં પ્રથમ દેખાવ વીના પ્રથમ દેખાવ કરતાં પછીના કાનમાં હોય છે. આ પ્રકારના કાનના વિઘટનનો ઉપયોગ વ્હિટનીના પરિણામને સામાન્ય બનાવવા માટે થઈ શકે છેઃ જો જી પાસે બિન-વિભાજીત કાનનું વિઘટન હોય તો જ 3-વર્ટેક્સ સાથે ગ્રાફ જોડાયેલ હોય છે. જો આવું વિઘટન અસ્તિત્વમાં હોય, તો તેને G ની ચોક્કસ ધાર uv ના સંદર્ભમાં એવી રીતે પસંદ કરી શકાય છે કે u પ્રથમ કાનમાં હોય, v એ છેલ્લા કાનમાં એકથી વધુ ધાર સાથેનું નવું શિરોબિંદુ હોય અને uv એ એક ધારવાળું કાન હોય. આ પરિણામ સૌપ્રથમ સ્પષ્ટ રીતે લી મોન્ડશેઇન દ્વારા જણાવવામાં આવ્યું હતું, પરંતુ વર્ણવ્યા મુજબ, તે લી મોન્ડશેઇનના 1971 પીએચ. ડી. થીસીસના પરિણામની સમકક્ષ છે. મહત્તમ સમતલીય આલેખના બિન-વિભાજીત કાનના વિઘટન સાથે નજીકથી સંબંધિત માળખાં, જેને કેનોનિકલ ઓર્ડર કહેવાય છે, તે પણ આલેખ ચિત્રમાં એક પ્રમાણભૂત સાધન છે. નિર્દેશિત આલેખની મજબૂત જોડાણ ઉપરોક્ત વ્યાખ્યાઓ નિર્દેશિત આલેખ પર પણ લાગુ કરી શકાય છે. કાન પછી એક નિર્દેશિત માર્ગ હશે જ્યાં તમામ આંતરિક શિરોબિંદુઓ 1 ની બરાબર અસ્પષ્ટ અને બાહ્ય ડિગ્રી ધરાવે છે. નિર્દેશિત આલેખ મજબૂત રીતે જોડાયેલ હોય છે જો તેમાં દરેક શિરોબિંદુથી દરેક અન્ય શિરોબિંદુ સુધી નિર્દેશિત માર્ગ હોય. પછી આપણી પાસે નીચેનો પ્રમેય છેઃ નિર્દેશિત આલેખ મજબૂત રીતે જોડાયેલો હોય છે જો અને માત્ર ત્યારે જ જો તેમાં કાનનું વિઘટન હોય. પરિબળ-નિર્ણાયક આલેખ કાનનું વિઘટન વિચિત્ર છે જો તેના દરેક કાન વિચિત્ર સંખ્યામાં ધારનો ઉપયોગ કરે છે. પરિબળ-નિર્ણાયક આલેખ એ શિરોબિંદુઓની વિષમ સંખ્યા ધરાવતો આલેખ છે, જેમ કે દરેક શિરોબિંદુ v માટે, જો v ને આલેખમાંથી દૂર કરવામાં આવે તો બાકીના શિરોબિંદુઓ સંપૂર્ણ મેળ ખાય છે. એવું જાણવા મળ્યું કેઃ ગ્રાફ G એ પરિબળ-નિર્ણાયક છે જો અને માત્ર ત્યારે જ જો G માં વિચિત્ર કાનનું વિઘટન હોય. વધુ સામાન્ય રીતે, તેનું પરિણામ કોઈપણ ગ્રાફ G માં સૌથી ઓછા સરખા કાન સાથે કાનનું વિઘટન શોધવાનું શક્ય બનાવે છે. શ્રેણી-સમાંતર આલેખ વૃક્ષના કાનનું વિઘટન એ યોગ્ય કાનનું વિઘટન છે જેમાં પ્રથમ કાન એક જ ધાર ધરાવે છે અને પછીના દરેક કાન માટે એક જ કાન હોય છે, જેમ કે બંને અંતિમ બિંદુઓ તેના પર હોય છે. નેસ્ટેડ કાનનું વિઘટન એ વૃક્ષના કાનનું વિઘટન છે, જેમ કે, દરેક કાનની અંદર, અન્ય કાનના અંતિમ બિંદુઓની જોડીનો સમૂહ જે નેસ્ટેડ અંતરાલોના સમૂહની રચના કરે છે. શ્રેણી-સમાંતર આલેખ એ બે નિયુક્ત ટર્મિનલ s અને t સાથેનો આલેખ છે જે બેમાંથી એક રીતે નાના શ્રેણી-સમાંતર આલેખને જોડીને પુનરાવર્તિત રીતે બનાવી શકાય છેઃ શ્રેણી રચના (એક નાના ગ્રાફમાંથી એક ટર્મિનલને અન્ય નાના ગ્રાફમાંથી એક ટર્મિનલ સાથે ઓળખવું, અને અન્ય બે ટર્મિનલ્સને સંયુક્ત ગ્રાફના ટર્મિનલ તરીકે રાખવું) અને સમાંતર રચના (બે નાના ગ્રાફમાંથી ટર્મિનલની બંને જોડીને ઓળખવી). નીચેનું પરિણામ આના કારણે છેઃ 2-વર્ટેક્સ-જોડાયેલ આલેખ શ્રેણી-સમાંતર હોય છે જો અને માત્ર ત્યારે જ જો તેમાં નેસ્ટેડ કાનનું વિઘટન હોય. વધુમાં, 2-વર્ટેક્સ-જોડાયેલ શ્રેણી-સમાંતર આલેખના કોઈપણ ખુલ્લા કાનના વિઘટનને નેસ્ટેડ કરવું આવશ્યક છે. પરિણામને બે ટર્મિનલ વચ્ચેના માર્ગથી શરૂ થતા ખુલ્લા કાનના વિઘટનનો ઉપયોગ કરીને શ્રેણી-સમાંતર આલેખ સુધી વિસ્તૃત કરી શકાય છે જે 2-વર્ટેક્સ સાથે જોડાયેલા નથી. મેટ્રોઇડ્સ કાનના વિઘટનની વિભાવનાને આલેખથી મેટ્રોઇડ્સ સુધી વિસ્તૃત કરી શકાય છે. મેટ્રોઇડના કાનના વિઘટનને બે ગુણધર્મો સાથે મેટ્રોઇડના સર્કિટ્સના ક્રમ તરીકે વ્યાખ્યાયિત કરવામાં આવે છેઃ અનુક્રમમાં દરેક સર્કિટ અગાઉના સર્કિટ્સ સાથે બિન-ખાલી આંતરછેદ ધરાવે છે, અને અનુક્રમમાં દરેક સર્કિટ એક સર્કિટ રહે છે, પછી ભલે તે ક્રમમાં અગાઉના તમામ સર્કિટ્સ સંકુચિત હોય. જ્યારે ગ્રાફ G ના ગ્રાફિક મેટ્રોઇડ પર લાગુ કરવામાં આવે છે, ત્યારે કાનના વિઘટનની આ વ્યાખ્યા G ના યોગ્ય કાનના વિઘટનની વ્યાખ્યા સાથે મેળ ખાય છેઃ અયોગ્ય વિઘટનને એ જરૂરિયાત દ્વારા બાકાત રાખવામાં આવે છે કે દરેક સર્કિટમાં ઓછામાં ઓછી એક ધાર હોય જે અગાઉની સર્કિટની પણ હોય. આ વ્યાખ્યાનો ઉપયોગ કરીને, મેટ્રોઇડને પરિબળ-નિર્ણાયક તરીકે વ્યાખ્યાયિત કરી શકાય છે જ્યારે તેમાં કાનનું વિઘટન હોય છે જેમાં અનુક્રમમાં દરેક સર્કિટમાં વિચિત્ર સંખ્યામાં નવા ઘટકો હોય છે. એલ્ગોરિધમ્સ શાસ્ત્રીય કમ્પ્યુટર્સ પર, 2-ધાર-જોડાયેલા આલેખના કાનના વિઘટન અને 2-વર્ટેક્સ-જોડાયેલા આલેખના ખુલ્લા કાનના વિઘટન લોભી અલ્ગોરિધમ્સ દ્વારા મળી શકે છે જે દરેક કાનને એક સમયે એક શોધે છે. એક સરળ લોભી અભિગમ કે જે એક જ સમયે રેખીય સમયમાં (જો અસ્તિત્વમાં હોય તો) કાનના વિઘટન, ખુલ્લા કાનના વિઘટન, એસ. ટી.-નંબરિંગ અને-ઓરિએન્ટેશનની ગણતરી કરે છે. આ અભિગમ એક પાથ-જનરેટિંગ નિયમ દ્વારા સાંકળ વિઘટન નામના ખાસ કાનના વિઘટનની ગણતરી પર આધારિત છે. તે દર્શાવે છે કે બિન-વિભાજીત કાનનું વિઘટન પણ રેખીય સમયમાં થઈ શકે છે. , અને વિવિધ પ્રકારના કાનના વિઘટનના નિર્માણ માટે કાર્યક્ષમ સમાંતર અલ્ગોરિધમ્સ પ્રદાન કર્યા. દાખલા તરીકે, 2-ધાર સાથે જોડાયેલા આલેખના કાનના વિઘટનને શોધવા માટે, નીચેના પગલાંઓ અનુસાર આવકનું અલ્ગોરિધમ શોધોઃ આપેલ આલેખનું ફેલાયેલું વૃક્ષ શોધો અને વૃક્ષ માટે મૂળ પસંદ કરો. વૃક્ષની ભાગ ન હોય તેવી દરેક ધાર uv માટે, મૂળ અને u અને v ના સૌથી નીચલા સામાન્ય પૂર્વજ વચ્ચેનું અંતર નક્કી કરો. વૃક્ષની ભાગ હોય તેવી દરેક ધાર માટે, અનુરૂપ "મુખ્ય ધાર", એક બિન-વૃક્ષ ધાર wx શોધો, જેથી વૃક્ષમાં wx ઉમેરીને રચાયેલ ચક્ર uv માંથી પસાર થાય અને જેમ કે, આવી ધાર વચ્ચે, w અને x નો સૌથી નીચો સામાન્ય પૂર્વજ હોય જે શક્ય તેટલો મૂળની નજીક હોય (ધાર ઓળખકર્તાઓ દ્વારા તૂટેલા સંબંધો સાથે). દરેક બિન-વૃક્ષ ધાર માટે એક કાન બનાવો, જેમાં તે અને વૃક્ષની ધારનો સમાવેશ થાય છે, જેના માટે તે માલિક છે, અને મૂળથી તેમની મુખ્ય ધારના અંતર દ્વારા કાનને ક્રમ આપો (સમાન ટાઈ-બ્રેકિંગ નિયમ સાથે). આ અલ્ગોરિધમ્સનો ઉપયોગ અન્ય સમસ્યાઓ માટે સબરૂટિન તરીકે થઈ શકે છે જેમાં પરીક્ષણ જોડાણ, શ્રેણી-સમાંતર આલેખને ઓળખવા અને આલેખની પ્રથમ-સંખ્યાનું નિર્માણ (પ્લેનેરિટી પરીક્ષણમાં એક મહત્વપૂર્ણ સબરૂટિન) સામેલ છે. દરેક કાનમાં મેટ્રોઇડનું સમાન નિશ્ચિત તત્વ હોય તેવી વધારાની મર્યાદા સાથે આપેલ મેટ્રોઇડનું કાનનું વિઘટન, મેટ્રોઇડ માટે સ્વતંત્ર ઓરેકલની ઍક્સેસ આપવામાં આવતા બહુપદી સમયમાં મળી શકે છે. સંદર્ભો. . . . . . . . . . . . . . . . ગ્રાફ થિયરી ઓબ્જેક્ટ્સ મેટ્રોઇડ થિયરી