નિર્દેશિત અને અન્ડરડાઈડ ગ્રાફ વચ્ચેનો તફાવત

નિર્દેશિત વિ અન્ડરડાઈડ ગ્રાફ

ગ્રાફ એ ગાણિતિક રચના છે જે શિરોબિંદુઓ અને કિનારીઓના સમૂહથી બનેલું છે. એક ગ્રાફ ઑબ્જેક્ટ્સનો એક સમૂહ રજૂ કરે છે (શિરોબિંદુઓ દ્વારા રજૂ થાય છે) જે કેટલાક લિંક્સ (કિનારીઓ દ્વારા રજૂ થયેલ) દ્વારા જોડાયેલ છે. ગાણિતિક સંકેતોનો ઉપયોગ કરીને, ગ્રાફને G દ્વારા રજૂ કરી શકાય છે, જ્યાં G = (V, E) અને V શિરોબિંદુઓનો સમૂહ છે અને E એ કિનારીઓનો સમૂહ છે. એક અનધિકૃત ગ્રાફમાં શિરોબિંદુઓને જોડતી ધાર સાથે કોઈ દિશા નિર્દેશ નથી. નિર્દેશિત ગ્રાફમાં શિરોબિંદુઓને જોડતી કિનારીઓ સાથે સંકળાયેલ દિશા છે.

અન્ડરડાઈડ ગ્રાફ

અગાઉ સૂચવ્યા મુજબ, એક અનધિકૃત ગ્રાફ એક આલેખ છે, જેમાં કિનારીઓ કે જે શિરોબિંદુઓને ગ્રાફમાં લિંક કરે છે તેમાં કોઈ દિશા નથી. આકૃતિ 1 શિરોબિંદુ V = {V1, V2, V3} સાથે એક અનધિકૃત ગ્રાફ દર્શાવે છે. ઉપરોક્ત ગ્રાફમાં કિનારીઓના સેટને V = {(V1, V2), (V2, V3), (V1, V3)} તરીકે લખી શકાય છે. તે પણ નોંધી શકાય છે કે કિનારીઓના દિશામાં V = {(V2, V1), (V3, V2), (V3, V1)} તરીકે કાંડાઓના સમૂહને લખવાનું કંઇ અટકાવતું નથી. તેથી, અનધિકૃત ગ્રાફમાં કિનારીઓને જોડી ક્રમાંકિત નથી. આ એક અનધિકૃત ગ્રાફનું મુખ્ય લક્ષણ છે. અનધિકૃત આલેખનો ઉપયોગ પદાર્થો વચ્ચે સપ્રમાણ સંબંધો રજૂ કરવા માટે કરી શકાય છે જે શિરોબિંદુ દ્વારા રજૂ થાય છે. ઉદાહરણ તરીકે, બે રસ્તા માર્ગ નેટવર્ક કે જે શહેરોના સમૂહને જોડે છે તે અનધિકૃત ગ્રાફનો ઉપયોગ કરીને રજૂ કરી શકાય છે. શહેરોને આલેખમાં શિરોબિંદુઓ દ્વારા રજૂ કરી શકાય છે અને કિનારી બે રસ્તા રસ્તાઓનું પ્રતિનિધિત્વ કરે છે જે શહેરોને જોડે છે.

નિર્દેશિત ગ્રાફ

નિર્દેશિત ગ્રાફ એ એક આલેખ છે જેમાં શિરોબિંદુઓને લિંક કરતા ગ્રાફમાં કિનારીઓ દિશા ધરાવે છે. આકૃતિ 2 શિરોબિંદુ V = {V1, V2, V3} સાથે નિર્દિષ્ટ ગ્રાફ દર્શાવે છે. ઉપરોક્ત ગ્રાફમાં કિનારીઓના સેટને V = {(V1, V2), (V2, V3), (V1, V3)} તરીકે લખી શકાય છે. એક અનધિકૃત ગ્રાફમાં ધારને આદેશ આપ્યો જોડી છે. ઔપચારિક રીતે, નિર્દેશિત ગ્રાફમાં ધાર અને ક્રમાંકના ક્રમાંકિત જોડી e = (x, y) દ્વારા રજૂ કરી શકાય છે જ્યાં x એ શિરોબિંદુ છે જેને મૂળ, સ્રોત અથવા ધારની પ્રારંભિક બિંદુ કહેવાય છે અને શિરોબિંદુ y એ ટર્મિનસ તરીકે ઓળખાય છે, શિરોબિંદુ અથવા ટર્મિનલ બિંદુ સમાપ્ત. ઉદાહરણ તરીકે, એક માર્ગ માર્ગ કે જે એક માર્ગ રસ્તાઓનો ઉપયોગ કરીને શહેરોનો સમૂહ જોડે છે તે રોડ નેટવર્ક અનધિકૃત ગ્રાફનો ઉપયોગ કરીને રજૂ કરી શકાય છે. આ શહેરોને આલેખમાં શિરોબિંદુઓ દ્વારા રજૂ કરી શકાય છે અને નિર્દેશિત કિનારી રસ્તાઓનું પ્રતિનિધિત્વ કરે છે, જે રસ્તામાં ટ્રાફિકના પ્રવાહમાં દિશા નિર્દેશ કરે છે તે દિશામાં શહેરોને જોડે છે.

નિર્દેશિત ગ્રાફ અને અનધિકૃત ગ્રાફ વચ્ચે શું તફાવત છે?

નિર્દેશિત ગ્રાફમાં ધાર એ આદેશિત જોડી છે, જ્યાં આદેશ આપ્યો જોડી ધારની દિશાને દર્શાવે છે જે બે શિરોલંબને લિંક કરે છે. પ્રશ્નની બીજી બાજુએ, એક અનધિકૃત ગ્રાફમાં, ધાર એક અનનોર્ડ જોડી છે, કારણ કે કોઈ ધાર સાથે સંકળાયેલ કોઈ દિશા નથી.અનધિકૃત આલેખનો ઉપયોગ પદાર્થો વચ્ચે સપ્રમાણ સંબંધોનું પ્રતિનિધિત્વ કરવા માટે કરી શકાય છે. અનધિકૃત ગ્રાફમાં દરેક નોડમાં ડિગ્રી અને આઉટ ડિગ્રી બરાબર છે પરંતુ આ નિર્દેશિત ગ્રાફ માટે સાચું નથી. કોઈ અનિશ્ચિત ગ્રાફને રજૂ કરવા માટે મેટ્રિક્સનો ઉપયોગ કરતી વખતે, મેટ્રિક્સ હંમેશા સપ્રમાણ ગ્રાફ બને છે, પરંતુ આ નિર્દેશિત આલેખ માટે સાચું નથી એક અનધિકૃત ગ્રાફ વિભિન્ન દિશામાં જઈને બે નિર્દેશિત ધાર સાથે દરેક ધારને બદલીને નિર્દેશિત ગ્રાફમાં રૂપાંતરિત કરી શકાય છે. જો કે, નિર્દિષ્ટ ગ્રાફને એક અનધિકૃત ગ્રાફમાં રૂપાંતર કરવું શક્ય નથી.