Graph canonization
ગ્રાફ થિયરીમાં, ગણિતની એક શાખા, ગ્રાફ કેનોનાઇઝેશન એ આપેલ ગ્રાફ G નું કેનોનિકલ સ્વરૂપ શોધવાની સમસ્યા છે. એક કેનોનિકલ સ્વરૂપ એ લેબલ કરેલ ગ્રાફ કેનન (G) છે જે G માટે આઇસોમોર્ફિક છે, જેમ કે દરેક ગ્રાફ જે G માટે આઇસોમોર્ફિક છે તે G જેવું જ કેનોનિકલ સ્વરૂપ ધરાવે છે. આમ, ગ્રાફ કેનોનાઇઝેશન સમસ્યાના ઉકેલથી, કોઈ ગ્રાફ આઇસોમોર્ફિઝમની સમસ્યાને પણ હલ કરી શકે છેઃ બે ગ્રાફ G અને H આઇસોમોર્ફિક છે કે કેમ તે ચકાસવા માટે, તેમના કેનોનિકલ સ્વરૂપો કેનન (G) અને કેનન (H) ની ગણતરી કરો અને પરીક્ષણ કરો કે આ બે કેનોનિકલ સ્વરૂપો સમાન છે કે કેમ. ગ્રાફનું કેનોનિકલ સ્વરૂપ એ સંપૂર્ણ ગ્રાફ અપરિવર્તનશીલનું ઉદાહરણ છેઃ દરેક બે આઇસોમોર્ફિક ગ્રાફ સમાન કેનોનિકલ સ્વરૂપ ધરાવે છે, અને દરેક બે નોન-આઇસોમોર્ફિક ગ્રાફ અલગ કેનોનિકલ સ્વરૂપો ધરાવે છે. તેનાથી વિપરીત, આલેખના દરેક સંપૂર્ણ અપરિવર્તનનો ઉપયોગ કેનોનિકલ સ્વરૂપ બનાવવા માટે થઈ શકે છે. એન-વર્ટેક્સ આલેખના શિરોબિંદુ સમૂહને 1 થી એન સુધીના પૂર્ણાંકો સાથે ઓળખી શકાય છે, અને આવી ઓળખનો ઉપયોગ કરીને આલેખના કેનોનિકલ સ્વરૂપને તેના શિરોબિંદુઓના ક્રમચય તરીકે પણ વર્ણવી શકાય છે. ગ્રાફના કેનોનિકલ સ્વરૂપોને કેનોનિકલ લેબલિંગ પણ કહેવામાં આવે છે, અને ગ્રાફ કેનોનાઇઝેશનને કેટલીકવાર ગ્રાફ કેનોનિકલાઇઝેશન તરીકે પણ ઓળખવામાં આવે છે. કોમ્પ્યુટેશનલ જટિલતા સ્પષ્ટપણે, ગ્રાફ કેનોનાઇઝેશન સમસ્યા ઓછામાં ઓછી ગ્રાફ આઇસોમોર્ફિઝમ સમસ્યા જેટલી જ કોમ્પ્યુટેશનલ રીતે મુશ્કેલ છે. હકીકતમાં, ગ્રાફ આઇસોમોર્ફિઝમ ગ્રાફ કેનોનાઇઝેશન માટે AC0-ઘટાડી શકાય તેવું છે. જો કે, તે હજુ પણ એક ખુલ્લો પ્રશ્ન છે કે શું બે સમસ્યાઓ બહુપદી સમય સમકક્ષ છે. જ્યારે ગ્રાફ આઇસોમોર્ફિઝમ માટે (નિર્ધારક) બહુપદી અલ્ગોરિધમ્સનું અસ્તિત્વ હજુ પણ કોમ્પ્યુટેશનલ જટિલતા સિદ્ધાંતમાં એક ખુલ્લી સમસ્યા છે, ત્યારે 1977માં લેઝલો બાબાઇએ અહેવાલ આપ્યો હતો કે સંભાવના સાથે ઓછામાં ઓછું 1−એક્સપી (−ઓ (એન)), એક સરળ શિરોબિંદુ વર્ગીકરણ અલ્ગોરિધમ માત્ર બે શુદ્ધિકરણ પગલાં પછી તમામ એન-વર્ટેક્સ ગ્રાફના સમૂહમાંથી એકસરખી રીતે પસંદ કરેલા ગ્રાફનું કેનોનિકલ લેબલિંગ ઉત્પન્ન કરે છે. નાના ફેરફારો અને ઉમેરાયેલ ઊંડાઈ-પ્રથમ શોધ પગલું રેખીય અપેક્ષિત સમયમાં સમાન રીતે પસંદ કરેલા રેન્ડમ ગ્રાફનું કેનોનિકલ લેબલિંગ ઉત્પન્ન કરે છે. આ પરિણામ એ હકીકત પર થોડો પ્રકાશ પાડે છે કે શા માટે ઘણા અહેવાલિત ગ્રાફ આઇસોમોર્ફિઝમ અલ્ગોરિધમ્સ વ્યવહારમાં સારી રીતે વર્તે છે. સંભવિત જટિલતા સિદ્ધાંતમાં આ એક મહત્વપૂર્ણ સફળતા હતી જે તેના હસ્તપ્રત સ્વરૂપમાં વ્યાપકપણે જાણીતી બની હતી અને જે એક પરિસંવાદમાં અહેવાલ આપ્યાના લાંબા સમય પછી પણ "અપ્રકાશિત હસ્તપ્રત" તરીકે ટાંકવામાં આવી હતી. સામાન્ય રીતે જાણીતું કેનોનિકલ સ્વરૂપ એ સમરૂપતા વર્ગની અંદર લેક્સિકોગ્રાફિકલી સૌથી નાનો આલેખ છે, જે લેક્સિકોગ્રાફિકલી સૌથી નાનો સંલગ્નતા મેટ્રિક્સ સાથેનો વર્ગનો આલેખ છે જેને રેખીય શબ્દમાળા તરીકે ગણવામાં આવે છે. જો કે, લેક્સિકોગ્રાફિક રીતે સૌથી નાના ગ્રાફની ગણતરી એન. પી.-હાર્ડ છે. વૃક્ષો માટે, ઓ (એન) જગ્યાની જરૂર હોય તેવું સંક્ષિપ્ત બહુપદી કેનોનાઇઝેશન અલ્ગોરિધમ દ્વારા રજૂ કરવામાં આવે છે. દરેક શિરોબિંદુને શબ્દમાળા 01 સાથે લેબલ કરીને પ્રારંભ કરો. દરેક બિન-પર્ણ x માટે પુનરાવર્તિત રીતે x ના લેબલમાંથી અગ્રણી 0 અને પાછળના 1 ને દૂર કરો; પછી x ના લેબલને બધા નજીકના પાંદડાઓના લેબલ સાથે લેક્સિકોગ્રાફિક ક્રમમાં સૉર્ટ કરો. આ સૉર્ટ કરેલા લેબલને સંયોજિત કરો, અગ્રણી 0 અને પાછળના 1 ને પાછા ઉમેરો, આને x નું નવું લેબલ બનાવો અને નજીકના પાંદડાઓને કાઢી નાખો. જો બે શિરોબિંદુઓ બાકી હોય, તો તેમના લેબલને લેક્સિકોગ્રાફિક ક્રમમાં જોડો. એપ્લિકેશન્સ ગ્રાફ કેનોનાઇઝેશન એ ઘણા ગ્રાફ આઇસોમોર્ફિઝમ અલ્ગોરિધમ્સનો સાર છે. અગ્રણી સાધનોમાંથી એક નૌટી છે. ગ્રાફ કેનોનાઇઝેશનનો એક સામાન્ય ઉપયોગ ગ્રાફિકલ ડેટા માઇનિંગમાં છે, ખાસ કરીને રાસાયણિક ડેટાબેઝ એપ્લિકેશન્સમાં. રાસાયણિક પદાર્થો માટે સંખ્યાબંધ ઓળખકર્તાઓ, જેમ કે એસ. એમ. આઈ. એલ. ઇ. એસ. અને આઈ. એન. સી. એચ. આઈ. તેમની ગણતરીમાં કેનોનિકલાઇઝેશન પગલાંનો ઉપયોગ કરે છે, જે અનિવાર્યપણે આલેખનનું કેનોનિકલાઇઝેશન છે જે અણુનું પ્રતિનિધિત્વ કરે છે. આ ઓળખકર્તાઓ પરમાણુ માહિતીને એન્કોડ કરવા અને ડેટાબેઝમાં અને વેબ પર આવી માહિતીની શોધને સરળ બનાવવા માટે પ્રમાણભૂત (અને કેટલીકવાર માનવ-વાંચી શકાય તેવી) રીત પ્રદાન કરવા માટે રચાયેલ છે. સંદર્ભો આલેખ સિદ્ધાંત