End (graph theory)
અનંત આલેખના ગણિતમાં, આલેખનો અંત, સહજ ભાવે, તે દિશાને રજૂ કરે છે જેમાં આલેખ અનંત સુધી વિસ્તરે છે. અંતને ગાણિતિક રીતે અનંત માર્ગોના સમાનતા વર્ગો તરીકે ઔપચારિક બનાવી શકાય છે, જેમ કે આલેખ પર પીછો-ચોરી રમતો માટેની વ્યૂહરચનાઓનું વર્ણન કરતા આશ્રયસ્થાનો તરીકે, અથવા (સ્થાનિક રીતે મર્યાદિત આલેખના કિસ્સામાં) આલેખ સાથે સંકળાયેલ ટોપોલોજિકલ જગ્યાઓના ટોપોલોજિકલ અંત તરીકે. મર્યાદિત રીતે પેદા થયેલા જૂથોના અંતને વ્યાખ્યાયિત કરવા માટે આલેખના અંતનો ઉપયોગ (કેલે આલેખ દ્વારા) થઈ શકે છે. મર્યાદિત રીતે ઉત્પન્ન થયેલા અનંત જૂથોના એક, બે અથવા અનંત ઘણા છેડા હોય છે, અને જૂથોના છેડા વિશેનો સ્ટેલિંગનો સિદ્ધાંત એકથી વધુ છેડા ધરાવતા જૂથો માટે વિઘટન પ્રદાન કરે છે. વ્યાખ્યા અને લાક્ષણિકતા આલેખના અંતને અનંત માર્ગોના સમાનતા વર્ગોના સંદર્ભમાં વ્યાખ્યાયિત કરવામાં આવ્યા હતા. અનંત આલેખમાં A એ અર્ધ-અનંત સરળ માર્ગ છે; એટલે કે, તે શિરોબિંદુઓનો અનંત ક્રમ છે જેમાં દરેક શિરોબિંદુ અનુક્રમમાં વધુમાં વધુ એક વાર દેખાય છે અને અનુક્રમમાં દરેક બે સળંગ શિરોબિંદુઓ આલેખમાં ધારના બે અંતિમ બિંદુઓ છે. હેલિનની વ્યાખ્યા અનુસાર, બે કિરણો અને સમાન હોય છે જો ત્યાં એક કિરણો હોય (જે આપેલ બે કિરણોમાંથી એકની બરાબર હોઈ શકે છે) જેમાં અને દરેકમાં અનંત સંખ્યાબંધ શિરોબિંદુઓ હોય. આ એક સમાનતા સંબંધ છેઃ દરેક કિરણ પોતાની સમકક્ષ હોય છે, વ્યાખ્યા બે કિરણોના ક્રમના સંદર્ભમાં સમપ્રમાણ હોય છે, અને તેને સંક્રમક તરીકે દર્શાવી શકાય છે. તેથી, તે તમામ કિરણોના સમૂહને સમાનતા વર્ગોમાં વિભાજિત કરે છે, અને હેલિને અંતને આ સમાનતા વર્ગોમાંથી એક તરીકે વ્યાખ્યાયિત કર્યો છે. સમાન સમાનતા સંબંધની વૈકલ્પિક વ્યાખ્યાનો પણ ઉપયોગ કરવામાં આવ્યો છેઃ બે કિરણો અને સમકક્ષ હોય છે જો શિરોબિંદુઓનો કોઈ મર્યાદિત સમૂહ ન હોય જે તેના અનંત ઘણા શિરોબિંદુઓને તેના અનંત ઘણા શિરોબિંદુઓથી અલગ કરે. આ હેલિનની વ્યાખ્યાની સમકક્ષ છેઃ જો હેલિનની વ્યાખ્યામાંથી કિરણ અસ્તિત્વમાં હોય, તો કોઈપણ વિભાજકમાં અનંત સંખ્યાબંધ બિંદુઓ હોવા જોઈએ અને તેથી તે મર્યાદિત ન હોઈ શકે, અને તેનાથી વિપરીત જો અસ્તિત્વમાં ન હોય તો એક માર્ગ જે શક્ય તેટલી વખત વચ્ચે ફેરબદલ કરે છે અને ઇચ્છિત મર્યાદિત વિભાજક બનાવવો જોઈએ. એન્ડ્સમાં હેવનની દ્રષ્ટિએ વધુ નક્કર લાક્ષણિકતા પણ હોય છે, જે કાર્યો ગ્રાફ પર પર્સ્યુટ-ઇવેઝન રમતો માટે કરચોરીની વ્યૂહરચનાઓનું વર્ણન કરે છે. પ્રશ્નની રમતમાં, એક લૂંટારો તેની ધારની સાથે શિરોબિંદુથી શિરોબિંદુ તરફ આગળ વધીને પોલીસકર્મીઓના સમૂહને ટાળવાનો પ્રયાસ કરી રહ્યો છે. પોલીસ પાસે હેલિકોપ્ટર હોય છે અને તેથી ધારને અનુસરવાની જરૂર નથી; જો કે લૂંટારો પોલીસને આવતા જોઈ શકે છે અને હેલિકોપ્ટર ઉતરાણ કરતા પહેલા આગળ ક્યાં જવું તે પસંદ કરી શકે છે. હેવન એ એક કાર્ય છે જે પોલીસ સ્થાનોના દરેક સમૂહને હટાવીને રચાયેલા સબગ્રાફના જોડાયેલા ઘટકોમાંથી એક સાથે મેપ કરે છે; એક લૂંટારો રમતના દરેક રાઉન્ડમાં આ ઘટકની અંદર એક શિરોબિંદુ તરફ આગળ વધીને પોલીસને ટાળી શકે છે. હેવેન્સે સુસંગતતા મિલકતને સંતોષવી આવશ્યક છે (જે જરૂરિયાતને અનુરૂપ છે કે લૂંટારો શિરોબિંદુઓ કે જેના પર પોલીસ પહેલેથી જ ઉતરી ગઈ છે તેમાંથી આગળ વધી શકતો નથી): જો તે પેટા સમૂહ છે, અને બંને અને પોલીસના આપેલ સમૂહ માટે સ્થળોનો માન્ય સમૂહ છે, તો તે સુપરસેટ હોવો આવશ્યક છે. હેવન પાસે ક્રમ હોય છે જો પોલીસ સ્થાનોના સંગ્રહ કે જેના માટે તે એસ્કેપ વ્યૂહરચના પ્રદાન કરે છે તેમાં ગ્રાફમાં શિરોબિંદુઓ કરતાં ઓછા બધા ઉપગણોનો સમાવેશ થાય છે; ખાસ કરીને, તેમાં ક્રમ (સૌથી નાનો આલેફ નંબર) હોય છે જો તે શિરોબિંદુઓના દરેક મર્યાદિત ઉપગણને તેના ઘટક સાથે મેપ કરે છે. દરેક કિરણ ક્રમના આશ્રયસ્થાનને અનુરૂપ છે, એટલે કે, કાર્ય; જે દરેક મર્યાદિત સમૂહને તેના અનન્ય ઘટક સાથે મેળવે છે જેમાં કિરણના અનંત શિરોબિંદુઓ હોય છે. તેનાથી વિપરીત, ક્રમના દરેક આશ્રયસ્થાનને આ રીતે કિરણ દ્વારા વ્યાખ્યાયિત કરી શકાય છે. બે કિરણો સમકક્ષ હોય છે જો અને માત્ર ત્યારે જ જો તેઓ એક જ હેવનને વ્યાખ્યાયિત કરે, તો ગ્રાફના છેડા તેના ક્રમના હેવન સાથે એક-થી-એક અનુરૂપ હોય છે. ઉદાહરણો જો અનંત આલેખ પોતે એક કિરણ હોય, તો તેમાં અનંત રીતે ઘણા કિરણો હોય છે, જે દરેક શિરોબિંદુથી શરૂ થાય છે. જો કે, આ તમામ કિરણો એકબીજાની સમકક્ષ છે, તેથી તેનો માત્ર એક જ છેડો છે. જો જંગલ હોય (એટલે કે, કોઈ મર્યાદિત ચક્ર વિનાનો આલેખ), તો કોઈપણ બે કિરણોનું આંતરછેદ કાં તો એક માર્ગ અથવા એક કિરણ છે; જો તેમનું આંતરછેદ એક કિરણ હોય તો બે કિરણો સમકક્ષ હોય છે. જો દરેક જોડાયેલા ઘટકમાં આધાર શિરોબિંદુ પસંદ કરવામાં આવે, તો પછી દરેક છેડે આધાર શિરોબિંદુઓમાંથી એકથી શરૂ થતું અનન્ય કિરણ હોય છે, તેથી છેડાઓને આ કેનોનિકલ કિરણો સાથે એક-થી-એક પત્રવ્યવહારમાં મૂકી શકાય છે. દરેક ગણતરીપાત્ર આલેખમાં સમાન અંત સાથે ફેલાયેલું જંગલ છે. જો કે, માત્ર એક જ છેડા સાથે અગણિત અનંત આલેખ અસ્તિત્વમાં છે જેમાં દરેક ફેલાયેલા વૃક્ષના અનંત ઘણા છેડા હોય છે. જો અનંત ગ્રીડ ગ્રાફ હોય, તો તેમાં ઘણા કિરણો હોય છે, અને આપખુદ રીતે શિરોબિંદુ-વિચ્છેદિત કિરણોના મોટા સમૂહ હોય છે. જો કે, તેનો માત્ર એક જ અંત છે. હેવનની દ્રષ્ટિએ છેડાના લાક્ષણિકતાઓનો ઉપયોગ કરીને આ સૌથી સરળતાથી જોઈ શકાય છેઃ શિરોબિંદુઓના કોઈપણ મર્યાદિત સમૂહને દૂર કરવાથી બરાબર એક અનંત જોડાયેલા ઘટકને છોડી દેવામાં આવે છે, તેથી ત્યાં માત્ર એક જ હેવન છે (જે દરેક મર્યાદિત સમૂહને અનન્ય અનંત જોડાયેલા ઘટક સાથે મેપ કરે છે). ટોપોલોજિકલ અંત સાથેનો સંબંધ બિંદુ-સમૂહ ટોપોલોજીમાં, એક અંતની વિભાવના છે જે ગ્રાફ સિદ્ધાંતમાં અંતની વિભાવના જેવી જ છે, પરંતુ તદ્દન સમાન નથી, જે ઘણી અગાઉની છે. જો ટોપોલોજિકલ જગ્યાને કોમ્પેક્ટ સમૂહોના નેસ્ટેડ ક્રમ દ્વારા આવરી શકાય છે, તો જગ્યાનો અંત એ કોમ્પેક્ટ સમૂહોના પૂરક ઘટકોનો ક્રમ છે. આ વ્યાખ્યા કોમ્પેક્ટ સમૂહોની પસંદગી પર આધારિત નથીઃ આવી એક પસંદગી દ્વારા વ્યાખ્યાયિત અંતને અન્ય કોઈપણ પસંદગી દ્વારા વ્યાખ્યાયિત અંત સાથે એક-થી-એક પત્રવ્યવહારમાં મૂકી શકાય છે. અનંત આલેખને બે અલગ અલગ પરંતુ સંબંધિત રીતે ટોપોલોજિકલ અવકાશમાં બનાવી શકાય છેઃ આલેખના દરેક શિરોબિંદુને એક બિંદુ દ્વારા અને આલેખની દરેક ધારને ખુલ્લા એકમ અંતરાલ દ્વારા બદલીને આલેખમાંથી હૌસડોર્ફ જગ્યા ઉત્પન્ન થાય છે જેમાં જ્યારે પણ આલેખની ધાર સાથેનું દરેક આંતરછેદ એકમ અંતરાલનો ખુલ્લો સબસેટ હોય ત્યારે સમૂહને ખુલ્લો હોવાનું વ્યાખ્યાયિત કરવામાં આવે છે. આલેખના દરેક શિરોબિંદુને એક બિંદુ દ્વારા અને આલેખની દરેક ધારને એક બિંદુ દ્વારા બદલવાથી બિન-હૌસડોર્ફ જગ્યા ઉત્પન્ન થાય છે જેમાં ખુલ્લા સમૂહો એ ગુણધર્મ સાથેના સમૂહો હોય છે કે, જો તેનો શિરોબિંદુ સંબંધિત હોય, તો દરેક ધાર તેના અંતિમ બિંદુઓમાંથી એક તરીકે હોય છે. બંને કિસ્સાઓમાં, દરેક મર્યાદિત સબગ્રાફ ટોપોલોજિકલ સ્પેસના કોમ્પેક્ટ સબસ્પેસને અનુરૂપ છે, અને દરેક કોમ્પેક્ટ સબસ્પેસ એક મર્યાદિત સબગ્રાફને એકસાથે અનુરૂપ છે, હૌસડોર્ફના કિસ્સામાં, કિનારીઓના મર્યાદિત રીતે ઘણા કોમ્પેક્ટ યોગ્ય સબસેટ્સ. આમ, આલેખ કોમ્પેક્ટ સમૂહોના નેસ્ટેડ ક્રમ દ્વારા આવરી લેવામાં આવી શકે છે જો અને માત્ર ત્યારે જ જો તે સ્થાનિક રીતે મર્યાદિત હોય, દરેક શિરોબિંદુ પર ધારની મર્યાદિત સંખ્યા હોય. જો આલેખ જોડાયેલ હોય અને સ્થાનિક રીતે મર્યાદિત હોય, તો તેમાં એક સઘન આવરણ હોય છે જેમાં સમૂહ એ અમુક મનસ્વી રીતે પસંદ કરેલા પ્રારંભિક શિરોબિંદુથી મહત્તમ અંતરે શિરોબિંદુઓનો સમૂહ હોય છે. આ કિસ્સામાં કોઈપણ હેવન ટોપોલોજિકલ જગ્યાના અંતને વ્યાખ્યાયિત કરે છે જેમાં. અને તેનાથી વિપરીત, જો વ્યાખ્યાયિત ટોપોલોજિકલ સ્પેસનો અંત હોય, તો તે એવા હેવનને વ્યાખ્યાયિત કરે છે જેમાં ઘટક હોય છે, જ્યાં કોઈપણ સંખ્યા પૂરતી મોટી હોય છે. આમ, જોડાયેલા અને સ્થાનિક રીતે મર્યાદિત આલેખ માટે, ટોપોલોજિકલ અંત આલેખ-સૈદ્ધાંતિક અંત સાથે એક-થી-એક અનુરૂપ હોય છે. સ્થાનિક રીતે મર્યાદિત ન હોય તેવા આલેખ માટે, આલેખ અને તેના છેડા પરથી ટોપોલોજિકલ જગ્યાને વ્યાખ્યાયિત કરવી હજુ પણ શક્ય છે. આ જગ્યાને મેટ્રિક જગ્યા તરીકે રજૂ કરી શકાય છે જો અને માત્ર ત્યારે જ જો આલેખમાં સામાન્ય ફેલાયેલું વૃક્ષ હોય, મૂળવાળું ફેલાયેલું વૃક્ષ એવું હોય કે દરેક આલેખ ધાર પૂર્વજો-વંશજોની જોડીને જોડે. જો સામાન્ય ફેલાયેલું વૃક્ષ અસ્તિત્વમાં હોય, તો તેના અંતનો સમૂહ આપેલ આલેખ જેવો જ હોય છેઃ આલેખના દરેક છેડે વૃક્ષમાં બરાબર એક અનંત માર્ગ હોવો આવશ્યક છે. વિશેષ પ્રકારના છેડા મુક્ત છેડા આલેખના અંતને મુક્ત અંત તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જો આલેખના અન્ય તમામ છેડાઓથી અલગ પડે તેવા ગુણધર્મ સાથે શિરોબિંદુઓનો મર્યાદિત સમૂહ હોય. (એટલે કે, આશ્રયસ્થાનોની દ્રષ્ટિએ, દરેક અન્ય અંતથી અલગ છે.) મર્યાદિત રીતે ઘણા છેડા ધરાવતા આલેખમાં, દરેક છેડો મુક્ત હોવો જોઈએ. તે સાબિત કરે છે કે, જો અનંત અંત હોય, તો ક્યાં તો એક અંત અસ્તિત્વમાં છે જે મુક્ત નથી, અથવા કિરણોના અનંત પરિવાર અસ્તિત્વમાં છે જે સામાન્ય પ્રારંભિક શિરોબિંદુને શેર કરે છે અને અન્યથા એકબીજાથી અલગ પડે છે. જાડા છેડા આલેખનો જાડો છેડો એ એક છેડો છે જેમાં અનંત સંખ્યામાં જોડી મુજબના-વિચ્છેદિત કિરણો હોય છે. હેલિનનું ગ્રીડ પ્રમેય એવા આલેખની લાક્ષણિકતા દર્શાવે છે જેમાં જાડા છેડા હોય છેઃ તે બરાબર એવા આલેખ છે જેમાં ષટ્કોણ ટાઇલિંગનો પેટા આલેખ તરીકે પેટા વિભાગ હોય છે. વિશિષ્ટ પ્રકારના આલેખ સમમિતીય અને લગભગ સમમિતીય આલેખ જોડાયેલા સ્થાનિક રીતે મર્યાદિત આલેખને "લગભગ સમમિતીય" તરીકે વ્યાખ્યાયિત કરે છે જો ત્યાં એક શિરોબિંદુ અને એવી સંખ્યા અસ્તિત્વમાં હોય કે, દરેક અન્ય શિરોબિંદુ માટે, આલેખની ઓટોમોર્ફિઝમ હોય જેના માટે છબી અંતરની અંદર હોય; સમકક્ષ રીતે, જો તેના ઓટોમોર્ફિઝમ જૂથમાં મર્યાદિત રીતે ઘણી ભ્રમણકક્ષાઓ હોય તો જોડાયેલ સ્થાનિક રીતે મર્યાદિત આલેખ લગભગ સમમિતીય હોય છે. જેમ તેઓ દર્શાવે છે તેમ, દરેક જોડાયેલા સ્થાનિક રીતે મર્યાદિત લગભગ-સમમિતીય આલેખ માટે, છેડાઓની સંખ્યા કાં તો વધુમાં વધુ બે અથવા અગણિત હોય છે; જો તે અગણિત હોય, તો છેડાઓમાં કેન્ટોર સમૂહની ટોપોલોજી હોય છે. વધુમાં, મોહર દર્શાવે છે કે છેડાઓની સંખ્યા ચીગર અચળાંકને નિયંત્રિત કરે છે જ્યાં આલેખના શિરોબિંદુઓના તમામ મર્યાદિત બિન-ખાલી સમૂહો પર શ્રેણી હોય છે અને જ્યાં એક અંતિમ બિંદુ સાથે ધારોનો સમૂહ સૂચવે છે. અગણિત અંતવાળા લગભગ-સમમિતીય આલેખ માટે, જો કે, માત્ર બે અંતવાળા લગભગ-સમમિતીય આલેખ માટે,. કેલે આલેખ દરેક જૂથ અને જૂથ માટે જનરેટરનો સમૂહ કેલે આલેખ નક્કી કરે છે, એક આલેખ જેના શિરોબિંદુઓ જૂથના ઘટકો છે અને ધાર એ તત્વોની જોડી છે જ્યાં જનરેટરમાંથી એક છે. મર્યાદિત રીતે ઉત્પન્ન થયેલા જૂથના કિસ્સામાં, જૂથના છેડાઓને જનરેટરના મર્યાદિત સમૂહ માટે કેલે ગ્રાફના છેડા તરીકે વ્યાખ્યાયિત કરવામાં આવે છે; આ વ્યાખ્યા જનરેટરની પસંદગી હેઠળ અપરિવર્તનશીલ છે, એ અર્થમાં કે જો જનરેટરના બે અલગ-અલગ મર્યાદિત સમૂહ પસંદ કરવામાં આવે, તો બે કેલે ગ્રાફના છેડા એકબીજા સાથે એક-થી-એક પત્રવ્યવહારમાં હોય છે. દાખલા તરીકે, દરેક મુક્ત જૂથ પાસે કેલી ગ્રાફ (તેના મુક્ત જનરેટર માટે) છે જે એક વૃક્ષ છે. એક જનરેટર પર મુક્ત જૂથ તેના કેલે આલેખ તરીકે બમણો અનંત માર્ગ ધરાવે છે, જેમાં બે છેડા હોય છે. દરેક અન્ય મુક્ત જૂથના અનંત અંત હોય છે. દરેક મર્યાદિત રીતે ઉત્પન્ન થયેલ અનંત જૂથમાં 1,2, અથવા અનંત ઘણા છેડા હોય છે, અને જૂથોના છેડા વિશે સ્ટેલિંગનો સિદ્ધાંત એકથી વધુ છેડા ધરાવતા જૂથોનું વિઘટન પ્રદાન કરે છે. ખાસ કરીનેઃ મર્યાદિત રીતે ઉત્પન્ન થયેલ અનંત જૂથને 2 અંત હોય છે જો અને માત્ર ત્યારે જ જો તેમાં મર્યાદિત અનુક્રમણિકાનું ચક્રીય પેટાજૂથ હોય. મર્યાદિત રીતે ઉત્પન્ન થયેલ અનંત જૂથ અનંત અંત ધરાવે છે જો અને માત્ર ત્યારે જ જો તે એકીકરણ સાથે બિન-તુચ્છ મુક્ત ઉત્પાદન હોય અથવા મર્યાદિત એકીકરણ સાથે એચ. એન. એન.-વિસ્તરણ હોય. મર્યાદિત રીતે પેદા થયેલા અન્ય તમામ અનંત જૂથો બરાબર એક અંત ધરાવે છે. નોંધો સંદર્ભ આલેખ સિદ્ધાંત પદાર્થો અનંત આલેખ