Algebraic graph theory
બીજગણિત આલેખ સિદ્ધાંત એ ગણિતની એક શાખા છે જેમાં આલેખ વિશેની સમસ્યાઓ પર બીજગણિત પદ્ધતિઓ લાગુ કરવામાં આવે છે. આ ભૌમિતિક, સંયુક્ત અથવા અલ્ગોરિધમિક અભિગમોથી વિપરીત છે. બીજગણિત આલેખ સિદ્ધાંતની ત્રણ મુખ્ય શાખાઓ છે, જેમાં રેખીય બીજગણિતનો ઉપયોગ, જૂથ સિદ્ધાંતનો ઉપયોગ અને આલેખ અચળાંકનો અભ્યાસ સામેલ છે. બીજગણિત આલેખ સિદ્ધાંતની શાખાઓ રેખીય બીજગણિતનો ઉપયોગ કરીને બીજગણિત આલેખ સિદ્ધાંતની પ્રથમ શાખામાં રેખીય બીજગણિતના સંબંધમાં આલેખનો અભ્યાસ સામેલ છે. ખાસ કરીને, તે સંલગ્નતા મેટ્રિક્સના વર્ણપટ અથવા ગ્રાફના લાપ્લેસીયન મેટ્રિક્સનો અભ્યાસ કરે છે (બીજગણિત આલેખ સિદ્ધાંતના આ ભાગને વર્ણપટ આલેખ સિદ્ધાંત પણ કહેવામાં આવે છે). ઉદાહરણ તરીકે, પીટરસન આલેખ માટે, નિકટતા મેટ્રિક્સનો વર્ણપટ (−2, −2, −2, −2,1,1,1,1,3) છે. કેટલાક પ્રમેયો વર્ણપટના ગુણધર્મોને અન્ય આલેખ ગુણધર્મો સાથે સંબંધિત કરે છે. એક સરળ ઉદાહરણ તરીકે, વ્યાસ D સાથે જોડાયેલા આલેખમાં તેના વર્ણપટમાં ઓછામાં ઓછા D + 1 અલગ મૂલ્યો હશે. આલેખ વર્ણપટના પાસાઓનો ઉપયોગ નેટવર્કની સુમેળનું વિશ્લેષણ કરવા માટે કરવામાં આવ્યો છે. જૂથ સિદ્ધાંતનો ઉપયોગ બીજગણિત આલેખ સિદ્ધાંતની બીજી શાખામાં જૂથ સિદ્ધાંત, ખાસ કરીને ઓટોમોર્ફિઝમ જૂથો અને ભૌમિતિક જૂથ સિદ્ધાંતના સંબંધમાં આલેખનો અભ્યાસ સામેલ છે. સમપ્રમાણતા (જેમ કે સપ્રમાણ આલેખ, શિરોબિંદુ-સંક્રમણ આલેખ, ધાર-સંક્રમણ આલેખ, અંતર-સંક્રમણ આલેખ, અંતર-નિયમિત આલેખ અને મજબૂત નિયમિત આલેખ) અને આ પરિવારો વચ્ચેના સમાવેશ સંબંધો પર આધારિત આલેખના વિવિધ પરિવારો પર ધ્યાન કેન્દ્રિત કરવામાં આવે છે. આલેખની આવી કેટલીક શ્રેણીઓ એટલી વિરલ છે કે આલેખની યાદી તૈયાર કરી શકાય છે. ફ્રુક્ટના પ્રમેય દ્વારા, તમામ જૂથોને જોડાયેલા આલેખ (ખરેખર, ઘન આલેખના) ના ઓટોમોર્ફિઝમ જૂથ તરીકે રજૂ કરી શકાય છે. જૂથ સિદ્ધાંત સાથે અન્ય જોડાણ એ છે કે, કોઈપણ જૂથને જોતાં, કેલે આલેખ તરીકે ઓળખાતા સપ્રમાણ આલેખ પેદા કરી શકાય છે, અને તેમાં જૂથની રચના સાથે સંબંધિત ગુણધર્મો હોય છે. બીજગણિત આલેખ સિદ્ધાંતની આ બીજી શાખા પ્રથમ સાથે સંબંધિત છે, કારણ કે આલેખના સમપ્રમાણતા ગુણધર્મો તેના વર્ણપટમાં પ્રતિબિંબિત થાય છે. ખાસ કરીને, પીટરસન આલેખ જેવા અત્યંત સપ્રમાણ આલેખના વર્ણપટમાં થોડા અલગ મૂલ્યો હોય છે (પીટરસન આલેખમાં 3 હોય છે, જે તેના વ્યાસને જોતાં ઓછામાં ઓછું શક્ય છે). કેલે આલેખ માટે, વર્ણપટ સીધા જૂથના માળખા સાથે સંબંધિત હોઈ શકે છે, ખાસ કરીને તેના ઈરીડ્યુસિબલ અક્ષરો સાથે. ગ્રાફ અપરિવર્તનોનો અભ્યાસ છેલ્લે, બીજગણિત ગ્રાફ સિદ્ધાંતની ત્રીજી શાખા ગ્રાફના અપરિવર્તનના બીજગણિત ગુણધર્મો અને ખાસ કરીને રંગીન બહુપદી, ટુટ્ટે બહુપદી અને ગાંઠ અપરિવર્તન સાથે સંબંધિત છે. ગ્રાફની રંગીન બહુપદી, ઉદાહરણ તરીકે, તેના યોગ્ય શિરોબિંદુ રંગોની સંખ્યાની ગણતરી કરે છે. પીટરસન આલેખ માટે, આ બહુપદી છે. ખાસ કરીને, આનો અર્થ એ છે કે પીટરસન ગ્રાફને એક કે બે રંગોથી યોગ્ય રીતે રંગીન કરી શકાતો નથી, પરંતુ તેને 3 રંગોથી 120 જુદી જુદી રીતે રંગીન કરી શકાય છે. બીજગણિત આલેખ સિદ્ધાંતના આ ક્ષેત્રમાં ઘણું કામ ચાર રંગ પ્રમેયને સાબિત કરવાના પ્રયાસોથી પ્રેરિત હતું. જો કે, હજુ પણ ઘણી ખુલ્લી સમસ્યાઓ છે, જેમ કે સમાન રંગીન બહુપદી ધરાવતા આલેખની લાક્ષણિકતા દર્શાવવી અને કઈ બહુપદી રંગીન છે તે નક્કી કરવું. આ પણ જુઓ વર્ણપટ આલેખ સિદ્ધાંત બીજગણિત સંયોજન બીજગણિત જોડાણ ડુલમેજ-મેન્ડેલસોહન વિઘટન આલેખ ગુણધર્મ એડજેસેન્સી મેટ્રિક્સ સંદર્ભો. બાહ્ય કડીઓ