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