Directed graph
ગણિતમાં, અને ખાસ કરીને આલેખ સિદ્ધાંતમાં, નિર્દેશિત આલેખ (અથવા ડિગ્રાફ) એ એક આલેખ છે જે નિર્દેશિત ધાર દ્વારા જોડાયેલા શિરોબિંદુઓના સમૂહથી બનેલો હોય છે, જેને ઘણીવાર ચાપ કહેવામાં આવે છે. વ્યાખ્યા ઔપચારિક શબ્દોમાં, નિર્દેશિત આલેખ એ એક ક્રમબદ્ધ જોડી છે જ્યાં V એ એક સમૂહ છે જેના તત્વોને શિરોબિંદુઓ, ગાંઠો અથવા બિંદુઓ કહેવામાં આવે છે; A એ શિરોબિંદુઓની ક્રમબદ્ધ જોડીનો સમૂહ છે, જેને ચાપ, નિર્દેશિત ધાર (કેટલીકવાર ફક્ત A ને બદલે E નામના અનુરૂપ સમૂહ સાથે ધાર), તીર અથવા નિર્દેશિત રેખાઓ કહેવાય છે. તે સામાન્ય અથવા દિશાહીન આલેખથી અલગ છે, જેમાં બાદમાં શિરોબિંદુઓની અનિયંત્રિત જોડીની દ્રષ્ટિએ વ્યાખ્યાયિત કરવામાં આવે છે, જેને સામાન્ય રીતે ધાર, કડીઓ અથવા રેખાઓ કહેવામાં આવે છે. ઉપરોક્ત વ્યાખ્યા નિર્દેશિત આલેખને સમાન સ્રોત અને લક્ષ્ય ગાંઠો સાથે બહુવિધ તીર રાખવાની મંજૂરી આપતી નથી, પરંતુ કેટલાક લેખકો એક વ્યાપક વ્યાખ્યાને ધ્યાનમાં લે છે જે નિર્દેશિત આલેખને આવા બહુવિધ કમાનો રાખવાની મંજૂરી આપે છે (એટલે કે, તેઓ ચાપ સમૂહને બહુવિધ સમૂહ બનાવવાની મંજૂરી આપે છે). કેટલીકવાર આ સંસ્થાઓને નિર્દેશિત બહુલેખન (અથવા બહુલેખન) કહેવામાં આવે છે. બીજી બાજુ, ઉપરોક્ત વ્યાખ્યા નિર્દેશિત આલેખને લૂપ્સ (એટલે કે, ચાપ કે જે સીધા ગાંઠોને પોતાની સાથે જોડે છે) રાખવાની મંજૂરી આપે છે, પરંતુ કેટલાક લેખકો એક સાંકડી વ્યાખ્યાને ધ્યાનમાં લે છે જે નિર્દેશિત આલેખને લૂપ્સ રાખવાની મંજૂરી આપતું નથી. લૂપ વગરના નિર્દેશિત આલેખને સરળ નિર્દેશિત આલેખ કહી શકાય, જ્યારે લૂપ સાથેના નિર્દેશિત આલેખને લૂપ-ડિગ્રાફ કહી શકાય (વિભાગ જુઓ નિર્દેશિત આલેખના પ્રકારો). નિર્દેશિત આલેખના પ્રકાર પેટા વર્ગો સમમિતીય નિર્દેશિત આલેખ એ નિર્દેશિત આલેખ છે જ્યાં બધી ધાર બે વાર દેખાય છે, દરેક દિશામાં એક (એટલે કે, ડિગ્રાફ સાથે જોડાયેલા દરેક તીર માટે, અનુરૂપ વ્યસ્ત તીર પણ તેની સાથે સંબંધિત છે). (આવી ધારને કેટલીકવાર "દ્વિદિશ" કહેવામાં આવે છે અને આવા આલેખને કેટલીકવાર "દ્વિદિશ" કહેવામાં આવે છે, પરંતુ આ દ્વિદિશ આલેખના અર્થ સાથે વિરોધાભાસી છે.) સરળ નિર્દેશિત આલેખ એ નિર્દેશિત આલેખ છે જેમાં કોઈ લૂપ્સ (તીર કે જે સીધા શિરોબિંદુઓને પોતાની સાથે જોડે છે) નથી અને સમાન સ્રોત અને લક્ષ્ય ગાંઠો સાથે કોઈ બહુવિધ તીર નથી. પહેલેથી જ રજૂ કરવામાં આવ્યું છે તેમ, બહુવિધ તીરના કિસ્સામાં અસ્તિત્વને સામાન્ય રીતે નિર્દેશિત બહુવિજ્ઞાન તરીકે સંબોધવામાં આવે છે. કેટલાક લેખકો લૂપ સાથેના ડિગ્રાફને લૂપ-ડિગ્રાફ તરીકે વર્ણવે છે. સંપૂર્ણ નિર્દેશિત આલેખ એ સરળ નિર્દેશિત આલેખ છે જ્યાં શિરોબિંદુઓની દરેક જોડી નિર્દેશિત ચાપની સપ્રમાણ જોડી દ્વારા જોડાયેલી હોય છે (તે વિપરીત ચાપની જોડી દ્વારા બદલાયેલી ધાર સાથે દિશાહીન સંપૂર્ણ આલેખની સમકક્ષ હોય છે). તે અનુસરે છે કે સંપૂર્ણ ડિગ્રાફ સપ્રમાણ છે. અર્ધ-પૂર્ણ બહુપક્ષીય ડિગ્રાફ એ સરળ ડિગ્રાફ છે જેમાં શિરોબિંદુ સમૂહને એવા સમૂહમાં વિભાજિત કરવામાં આવે છે કે જેમાં વિવિધ સમૂહમાં x અને y શિરોબિંદુઓની દરેક જોડી માટે, x અને y વચ્ચે એક ચાપ હોય. x અને y વચ્ચે એક ચાપ અથવા વિરુદ્ધ દિશામાં બે ચાપ હોઈ શકે છે. અર્ધ-પૂર્ણ ડિગ્રાફ્સ એ સરળ ડિગ્રાફ્સ છે જ્યાં શિરોબિંદુઓની દરેક જોડી વચ્ચે ચાપ હોય છે. દરેક અર્ધ-પૂર્ણ ડિગ્રાફ એ તુચ્છ રીતે અર્ધ-પૂર્ણ બહુપક્ષીય ડિગ્રાફ છે, જેમાં દરેક શિરોબિંદુ પાર્ટીશનનો સમૂહ બનાવે છે. અર્ધ-સંક્રમક ડિગ્રાફ્સ એ સરળ ડિગ્રાફ્સ છે જ્યાં x થી y અને y થી z સુધીની ચાપવાળા અલગ શિરોબિંદુઓના દરેક ત્રિપલ x, y, z માટે, x અને z વચ્ચે એક ચાપ હોય છે. x અને z વચ્ચે માત્ર એક ચાપ હોઈ શકે છે અથવા વિરુદ્ધ દિશામાં બે ચાપ હોઈ શકે છે. અર્ધ-પૂર્ણ ડિગ્રાફ એ અર્ધ-સંક્રમક ડિગ્રાફ છે. અર્ધ-સંક્રમણશીલ ડિગ્રાફ્સના વિસ્તરણ છે જેને કે-અર્ધ-સંક્રમણશીલ ડિગ્રાફ્સ કહેવાય છે. ઓરિએન્ટેડ આલેખ એ નિર્દેશિત આલેખ છે જેમાં નિર્દેશિત ધારની કોઈ વિરુદ્ધ જોડી નથી (એટલે કે. તેમાંથી વધુમાં વધુ એક અને તે આલેખના તીર હોઈ શકે છે). તે અનુસરે છે કે નિર્દેશિત આલેખ એક લક્ષી આલેખ છે જો અને માત્ર ત્યારે જ જો તેમાં કોઈ 2-ચક્ર ન હોય. ("ઓરિએન્ટેડ ગ્રાફ" નો આ એકમાત્ર અર્થ નથી; ઓરિએન્ટેશન (ગ્રાફ થિયરી) જુઓ.) સ્પર્ધાઓ દિશાહીન સંપૂર્ણ આલેખમાં દરેક ધાર માટે દિશા પસંદ કરીને મેળવેલા લક્ષી આલેખ છે. ટુર્નામેન્ટ એ અર્ધ-પૂર્ણ ડિગ્રાફ છે. નિર્દેશિત આલેખ ચક્રીય હોય છે જો તેમાં કોઈ નિર્દેશિત ચક્ર ન હોય. આવા ડિગ્રાફનું સામાન્ય નામ નિર્દેશિત એસાયક્લિક ગ્રાફ (ડીએજી) છે. મલ્ટીટ્રી એ ડી. એ. જી. છે જેમાં સમાન પ્રારંભિક શિરોબિંદુથી સમાન અંતિમ શિરોબિંદુ સુધી કોઈ બે અલગ નિર્દેશિત માર્ગો નથી. ઓરિએન્ટેડ વૃક્ષો અથવા પોલીટ્રીસ એ ડી. એ. જી. છે જે વૃક્ષોની ધારને દિશા આપીને રચાય છે (જોડાયેલા, એસાયક્લિક દિશાહીન આલેખ). મૂળવાળા વૃક્ષો એવા વૃક્ષો છે જેમાં અંતર્ગત દિશાહીન વૃક્ષની તમામ ધાર કાં તો મૂળથી દૂર અથવા તરફ નિર્દેશિત હોય છે (તેમને અનુક્રમે, આર્બોરેસેન્સિસ અથવા આઉટ-ટ્રીઝ અને ઇન-ટ્રીઝ કહેવામાં આવે છે. ભારિત નિર્દેશિત આલેખ (જેને નિર્દેશિત નેટવર્ક તરીકે પણ ઓળખવામાં આવે છે) એ ભારિત આલેખ (જેને દિશાહીન નેટવર્ક અથવા ભારિત નેટવર્ક તરીકે પણ ઓળખવામાં આવે છે) ની જેમ તેમના તીરને સોંપેલ વજન સાથે (સરળ) નિર્દેશિત આલેખ છે. ફ્લો નેટવર્ક્સ ભારિત નિર્દેશિત આલેખ છે જ્યાં બે નોડ્સ અલગ પડે છે, એક સ્રોત અને એક સિંક. મૂળ નિર્દેશિત આલેખ (જેને પ્રવાહ આલેખ તરીકે પણ ઓળખવામાં આવે છે) એ ડિગ્રાફ છે જેમાં શિરોબિંદુને મૂળ તરીકે ઓળખવામાં આવે છે. નિયંત્રણ-પ્રવાહ આલેખ એ કોમ્પ્યુટર વિજ્ઞાનમાં તેના અમલીકરણ દરમિયાન પ્રોગ્રામ દ્વારા પસાર થઈ શકે તેવા માર્ગોની રજૂઆત તરીકે ઉપયોગમાં લેવાતા મૂળ આકૃતિચિત્રો છે. સિગ્નલ-ફ્લો ગ્રાફ એ નિર્દેશિત ગ્રાફ છે જેમાં નોડ્સ સિસ્ટમ ચલોનું પ્રતિનિધિત્વ કરે છે અને શાખાઓ (ધાર, ચાપ અથવા તીર) નોડ્સની જોડી વચ્ચેના કાર્યાત્મક જોડાણોનું પ્રતિનિધિત્વ કરે છે. ફ્લો ગ્રાફ એ રેખીય બીજગણિત અથવા વિભેદક સમીકરણોના સમૂહ સાથે સંકળાયેલા ડિગ્રાફ છે. રાજ્ય આકૃતિઓ નિર્દેશિત બહુલેખન છે જે મર્યાદિત રાજ્ય યંત્રોનું પ્રતિનિધિત્વ કરે છે. પરિવર્તનીય આકૃતિઓ એ શ્રેણી સિદ્ધાંતમાં ઉપયોગમાં લેવાતા ડિગ્રાફ્સ છે, જ્યાં શિરોબિંદુઓ (ગાણિતિક) પદાર્થોનું પ્રતિનિધિત્વ કરે છે અને તીર મોર્ફિઝમ્સનું પ્રતિનિધિત્વ કરે છે, જે ગુણધર્મ સાથે સમાન શરૂઆત અને અંતિમ બિંદુઓ સાથેના તમામ નિર્દેશિત માર્ગો રચના દ્વારા સમાન પરિણામ તરફ દોરી જાય છે. લાઈ જૂથોના સિદ્ધાંતમાં, ક્વિવર ક્યૂ એ એક નિર્દેશિત આલેખ છે જે ડોમેન તરીકે સેવા આપે છે, અને આમ પ્રતિનિધિત્વ V ના આકારને લાક્ષણિકતા આપે છે, જેને ફંકટર તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, ખાસ કરીને ફંકટર શ્રેણી FinVctKF (Q) નો એક પદાર્થ જ્યાં F (Q) એ Q પર મુક્ત શ્રેણી છે જેમાં Q માં પાથનો સમાવેશ થાય છે અને FinVctK એ ક્ષેત્ર K પર મર્યાદિત-પરિમાણીય વેક્ટર સ્પેસની શ્રેણી છે. ક્વિવરની રજૂઆતો તેના શિરોબિંદુઓને વેક્ટર સ્પેસ અને તેની ધાર (અને તેથી પાથ) સાથે સુસંગત રીતે તેમની વચ્ચેના રેખીય પરિવર્તન સાથે લેબલ કરે છે, અને કુદરતી પરિવર્તન દ્વારા રૂપાંતરિત થાય છે. મૂળભૂત પરિભાષા ચાપને x થી y તરફ નિર્દેશિત માનવામાં આવે છે; y ને હેડ કહેવામાં આવે છે અને x ને ચાપની પૂંછડી કહેવામાં આવે છે; y ને x નો સીધો ઉત્તરાધિકારી કહેવામાં આવે છે અને x ને y નો સીધો પુરોગામી કહેવામાં આવે છે. જો કોઈ પાથ x થી y તરફ દોરી જાય છે, તો y ને x નો અનુગામી અને x થી પહોંચી શકાય તેવું કહેવામાં આવે છે, અને x ને y નો પુરોગામી કહેવામાં આવે છે. આ ચાપને રિવર્સ આર્ક ઓફ કહેવામાં આવે છે. લૂપ્સ સાથે મલ્ટીડિગ્રાફનું નિકટતા મેટ્રિક્સ એ શિરોબિંદુઓને અનુરૂપ પંક્તિઓ અને સ્તંભો સાથેનું પૂર્ણાંક-મૂલ્ય ધરાવતું મેટ્રિક્સ છે, જ્યાં નોનડાયગોનલ એન્ટ્રી એઇજે એ શિરોબિંદુ i થી શિરોબિંદુ j સુધીની કમાનોની સંખ્યા છે, અને કર્ણ એન્ટ્રી એઇઆઈ એ શિરોબિંદુ i પર લૂપ્સની સંખ્યા છે. નિર્દેશિત આલેખની નિકટતા મેટ્રિક્સ એ તાર્કિક મેટ્રિક્સ છે, અને તે પંક્તિઓ અને સ્તંભોના ક્રમચય સુધી અનન્ય છે. નિર્દેશિત આલેખ માટે અન્ય મેટ્રિક્સ રજૂઆત તેના ઇન્સિડેન્સ મેટ્રિક્સ છે. વધુ વ્યાખ્યાઓ માટે દિશા જુઓ. એક શિરોબિંદુ માટે, શિરોબિંદુને અડીને આવેલા માથાના છેડાઓની સંખ્યાને શિરોબિંદુની ઇન્ડીગ્રી કહેવામાં આવે છે અને શિરોબિંદુને અડીને આવેલા પૂંછડીના છેડાઓની સંખ્યા તેની આઉટ ડિગ્રી છે (જેને વૃક્ષોમાં શાખાઓનું પરિબળ કહેવાય છે). દો અને. v ની ઇન્ડીગ્રીને ડીગ − (v) અને તેની આઉટ ડિગ્રીને ડીગ + (v) તરીકે સૂચવવામાં આવે છે. તેની સાથેના શિરોબિંદુને સ્રોત કહેવામાં આવે છે, કારણ કે તે તેની દરેક બહાર આવતી કમાનોનું મૂળ છે. તેવી જ રીતે, તેની સાથેના શિરોબિંદુને સિંક કહેવામાં આવે છે, કારણ કે તે તેની દરેક આવનારી ચાપનો અંત છે. ડિગ્રી સમ સૂત્ર જણાવે છે કે, નિર્દેશિત આલેખ માટે, જો દરેક શિરોબિંદુ માટે, આલેખને સંતુલિત નિર્દેશિત આલેખ કહેવામાં આવે છે. ડિગ્રી ક્રમ નિર્દેશિત આલેખનો ડિગ્રી ક્રમ એ તેની ઇન્ડીગ્રી અને આઉટ ડિગ્રી જોડીની સૂચિ છે; ઉપરોક્ત ઉદાહરણ માટે આપણી પાસે ડિગ્રી ક્રમ ((2,0), (2,2), (0,2), (1,1)) છે. ડિગ્રી ક્રમ એ નિર્દેશિત આલેખ અપરિવર્તનશીલ છે તેથી આઇસોમોર્ફિક નિર્દેશિત આલેખ સમાન ડિગ્રી ક્રમ ધરાવે છે. જો કે, ડિગ્રી ક્રમ, સામાન્ય રીતે, વિશિષ્ટ રીતે નિર્દેશિત આલેખને ઓળખતો નથી; કેટલાક કિસ્સાઓમાં, બિન-આઇસોમોર્ફિક ડિગ્રાફમાં સમાન ડિગ્રી ક્રમ હોય છે. નિર્દેશિત આલેખ અનુભૂતિ સમસ્યા એ ડિગ્રી ક્રમ સાથે નિર્દેશિત આલેખ શોધવાની સમસ્યા છે જે હકારાત્મક પૂર્ણાંક જોડીનો આપેલ ક્રમ છે. (શૂન્યની પાછળની જોડીને અવગણવામાં આવી શકે છે કારણ કે નિર્દેશિત આલેખમાં યોગ્ય સંખ્યામાં અલગ શિરોબિંદુઓ ઉમેરીને તેમને તુચ્છ રીતે સમજવામાં આવે છે.) એક ક્રમ જે અમુક નિર્દેશિત આલેખનો ડિગ્રી ક્રમ છે, એટલે કે. જેના માટે નિર્દેશિત આલેખ અનુભૂતિ સમસ્યાનો ઉકેલ હોય છે, તેને નિર્દેશિત ગ્રાફિક અથવા નિર્દેશિત ગ્રાફિકલ ક્રમ કહેવામાં આવે છે. આ સમસ્યાને કાં તો ક્લેઇટમેન-વાંગ અલ્ગોરિધમ દ્વારા અથવા ફુલ્કરસન-ચેન-એન્સ્ટી પ્રમેય દ્વારા ઉકેલી શકાય છે. નિર્દેશિત આલેખ જોડાણ નિર્દેશિત આલેખ નબળો રીતે જોડાયેલ હોય છે (અથવા ફક્ત જોડાયેલ હોય છે) જો ગ્રાફની તમામ નિર્દેશિત ધારને દિશાહીન ધાર સાથે બદલીને મેળવેલ દિશાહીન અંતર્ગત આલેખ જોડાયેલ આલેખ હોય. નિર્દેશિત આલેખ મજબૂત રીતે જોડાયેલ અથવા મજબૂત હોય છે જો તેમાં શિરોબિંદુઓની દરેક જોડી માટે x થી y (અને y થી x) નો નિર્દેશિત માર્ગ હોય. મજબૂત ઘટકો મહત્તમ મજબૂત રીતે જોડાયેલા સબગ્રાફ છે. જોડાયેલ મૂળ આલેખ (અથવા પ્રવાહ આલેખ) એ છે કે જ્યાં એક વિશિષ્ટ મૂળ શિરોબિંદુથી દરેક શિરોબિંદુ તરફ નિર્દેશિત માર્ગ અસ્તિત્વમાં હોય. નોંધો સંદર્ભો પણ જુઓ (2007ની સુધારેલી પ્રથમ આવૃત્તિ હવે લેખકોની સાઇટ પર મુક્તપણે ઉપલબ્ધ છે; બીજી આવૃત્તિ 2009માં પ્રકાશિત થઈ હતી). . . (ઇલેક્ટ્રોનિક ત્રીજી આવૃત્તિ લેખકની સાઇટ પર મુક્તપણે ઉપલબ્ધ છે). . પૂર્ણાંક ક્રમના ઓન-લાઇન જ્ઞાનકોશમાંથી n નોડ્સ સાથે નિર્દેશિત આલેખ (અથવા નિર્દેશિત આલેખ) ની સંખ્યા બાહ્ય કડીઓ નિર્દેશિત આલેખ સિદ્ધાંત આલેખ માહિતી માળખા