Strongly regular graph
આલેખ સિદ્ધાંતમાં, મજબૂત નિયમિત આલેખ (એસ. આર. જી.) એ શિરોબિંદુઓ અને ડિગ્રી સાથેનો નિયમિત આલેખ છે, જેમાં કેટલાક પૂર્ણાંકો માટે દરેક બે અડીને આવેલા શિરોબિંદુઓ સામાન્ય પડોશીઓ ધરાવે છે, અને દરેક બે બિન-અડીને આવેલા શિરોબિંદુઓ સામાન્ય પડોશીઓ ધરાવે છે. આવા મજબૂત નિયમિત આલેખને સૂચવવામાં આવે છે. તેનું પૂરક પણ મજબૂત રીતે નિયમિત છેઃ એક મજબૂત નિયમિત આલેખ એ 2 વ્યાસ સાથેનો અંતર-નિયમિત આલેખ છે જ્યારે પણ μ બિન-શૂન્ય હોય છે. જ્યારે પણ તે સ્થાનિક રીતે રેખીય આલેખ હોય છે. વ્યુત્પત્તિશાસ્ત્ર સાહિત્યમાં મજબૂત નિયમિત આલેખને srg (v, k, λ, μ) તરીકે દર્શાવવામાં આવે છે. પરંપરા મુજબ, વ્યાખ્યાને તુચ્છ રીતે સંતોષતા આલેખને વિગતવાર અભ્યાસો અને મજબૂત નિયમિત આલેખની સૂચિમાંથી બાકાત રાખવામાં આવે છે. આમાં એક અથવા વધુ સમાન-કદના સંપૂર્ણ આલેખના અસંબદ્ધ જોડાણ અને તેમના પૂરક, સમાન-કદના સ્વતંત્ર સમૂહો સાથેના સંપૂર્ણ બહુપક્ષીય આલેખનો સમાવેશ થાય છે. એન્ડ્રીઝ બ્રોવર અને હેન્ડ્રિક વાન માલ્ડેગેમ (જુઓ #References) વર્ણપટ આલેખ સિદ્ધાંત પર આધારિત મજબૂત નિયમિત આલેખની વૈકલ્પિક પરંતુ સંપૂર્ણ સમકક્ષ વ્યાખ્યાનો ઉપયોગ કરે છેઃ મજબૂત નિયમિત આલેખ એ મર્યાદિત નિયમિત આલેખ છે જેમાં બરાબર ત્રણ આઈગન મૂલ્યો હોય છે, જેમાંથી માત્ર એક ગુણાકાર 1 ની ડિગ્રી k ની બરાબર હોય છે. આ આપમેળે સંપૂર્ણપણે જોડાયેલા આલેખ (જેમાં ત્રણ નહીં પણ માત્ર બે અલગ અલગ આઈગન વેલ્યુ હોય છે) અને ડિસ્કનેક્ટેડ આલેખ (જેની ડિગ્રી k ની ગુણાકાર વિવિધ જોડાયેલા ઘટકોની સંખ્યા જેટલી હોય છે, જે તેથી એક કરતાં વધી જશે) ને નકારી કાઢે છે. બ્રોવર સહિત મોટાભાગના સાહિત્યમાં મોટા આઈગન વેલ્યુને r (ગુણાકાર f સાથે) અને નાના મૂલ્યને s (ગુણાકાર g સાથે) તરીકે ઓળખવામાં આવે છે. ઇતિહાસ આર. સી. દ્વારા મજબૂત રીતે નિયમિત આલેખ રજૂ કરવામાં આવ્યા હતા. 1963માં બોસ. તેઓએ 1950ના દાયકામાં સ્પેક્ટ્રલ ગ્રાફ થિયરીના તે સમયના નવા ક્ષેત્રમાં અગાઉના કામ પર નિર્માણ કર્યું હતું. ઉદાહરણો લંબાઈ 5 નું ચક્ર એક srg (5,2,0,1) છે. પીટરસન આલેખ એક srg (10,3,0,1) છે. ક્લેબશ આલેખ એક એસ. આર. જી. (16,5,0,2) છે. શ્રીખંડે આલેખ એક એસ. આર. જી. (16,6,2,2) છે જે અંતર-સંક્રમક આલેખ નથી. n × n ચોરસ રોકનો આલેખ, એટલે કે, સંતુલિત સંપૂર્ણ દ્વિપક્ષી આલેખ Kn, n નો રેખા આલેખ, એક srg (n2,2n−2, n−2,2) છે. આ માટેના પરિમાણો શ્રીખંડે આલેખ સાથે મેળ ખાય છે, પરંતુ બે આલેખ સમરૂપ નથી. સંપૂર્ણ આલેખ Kn નો રેખા આલેખ એક છે. ચાંગ આલેખ srg (28,12,6,4) છે, જે K8ના રેખા આલેખ જેવા જ છે, પરંતુ આ ચાર આલેખ સમરૂપ નથી. ક્રમ (s, t) નો દરેક સામાન્યીકૃત ચતુષ્કોણ તેના રેખા આલેખ તરીકે srg ((s + 1) (st + 1), s (t + 1), s-1, t + 1) આપે છે. ઉદાહરણ તરીકે, GQ (2,4) srg (27,10,1,5) ને તેના રેખા આલેખ તરીકે આપે છે. શ્લાફલી આલેખ એક srg (27,16,10,8) છે. હોફમેન-સિંગલેટન આલેખ એક srg (50,7,0,1) છે. સિમ્સ-ગેવર્ટ્ઝ આલેખ એક (56,10,0,2) છે. M22 આલેખ ઉર્ફે મેસનર આલેખ એક srg (77,16,0,4) છે. બ્રોવર-હેમર્સ આલેખ એક એસ. આર. જી. (81,20,1,6) છે. હિગમેન-સિમ્સ આલેખ એક srg (100,22,0,6) છે. સ્થાનિક મેકલાફલિન આલેખ એક એસ. આર. જી. (162,56,10,24) છે. કેમેરોન આલેખ એક એસ. આર. જી. (239,30,9,3) છે. બર્લેકેમ્પ-વાન લિન્ટ-સીડેલ આલેખ એક એસ. આર. જી. (243,22,1,2) છે. મેકલાફલિન આલેખ એક એસ. આર. જી. (275,112,30,56) છે. ક્રમ q નો પાલે આલેખ એક srg (q, (q−1)/2, (q−5)/4, (q−1)/4) છે. સૌથી નાનો પાલે ગ્રાફ, સાથે, 5-ચક્ર (ઉપર) છે. સ્વ-પૂરક ચાપ-સંક્રમક આલેખ ખૂબ જ નિયમિત હોય છે. જો આલેખ અને તેના પૂરક બંને જોડાયેલા હોય તો મજબૂત નિયમિત આલેખને આદિમ કહેવામાં આવે છે. ઉપરોક્ત તમામ આલેખ આદિમ છે, અન્યથા અથવા. કોનવેની 99-ગ્રાફ સમસ્યા એસ. આર. જી. (99,14,1,2) ના નિર્માણ માટે પૂછે છે. આ પરિમાણો સાથે ગ્રાફ અસ્તિત્વમાં છે કે કેમ તે અજ્ઞાત છે, અને જ્હોન હોર્ટન કોનવેએ આ સમસ્યાના ઉકેલ માટે $1000 નું ઇનામ ઓફર કર્યું હતું. ત્રિકોણ-મુક્ત આલેખ λ = 0 સાથે મજબૂત નિયમિત આલેખ ત્રિકોણ મુક્ત છે. 3 થી ઓછા શિરોબિંદુઓ પરના સંપૂર્ણ આલેખ અને તમામ સંપૂર્ણ દ્વિપક્ષી આલેખ ઉપરાંત, અગાઉ સૂચિબદ્ધ સાત (પંચકોણ, પીટરસન, ક્લેબશ, હોફમેન-સિંગલેટન, ગેવર્ટ્ઝ, મેસનર-એમ22 અને હિગમેન-સિમ્સ) માત્ર જાણીતા આલેખ છે. જીયોડેટિક આલેખ દરેક મજબૂત નિયમિત આલેખ એ જીયોડેટિક આલેખ છે, એક આલેખ જેમાં દરેક બે શિરોબિંદુઓ એક અનન્ય ભારરહિત ટૂંકો માર્ગ ધરાવે છે. એકમાત્ર જાણીતા મજબૂત નિયમિત આલેખ તે છે જ્યાં 0 છે, તેથી ત્રિકોણ-મુક્ત પણ છે. આને મૂરે આલેખ કહેવામાં આવે છે અને નીચે વધુ વિગતવાર શોધવામાં આવી છે. (400,21,2,1) જેવા પરિમાણોના અન્ય સંયોજનોને હજુ સુધી નકારી કાઢવામાં આવ્યા નથી. મજબૂત રીતે નિયમિત આલેખ ધરાવતા ગુણધર્મો પર ચાલુ સંશોધન હોવા છતાં, તે જાણીતું નથી કે શું વધુ અસ્તિત્વ ધરાવે છે અથવા તેમની સંખ્યા મર્યાદિત છે કે કેમ. માત્ર પ્રાથમિક પરિણામ જ જાણીતું છે, જે આવા આલેખ માટે 1 ન હોઈ શકે. મજબૂત નિયમિત આલેખના બીજગણિત ગુણધર્મો પરિમાણો વચ્ચેનો મૂળભૂત સંબંધ srg (v, k, λ, μ) માં ચાર પરિમાણો સ્વતંત્ર નથી. તેઓએ નીચેના સંબંધનું પાલન કરવું જોઈએઃ ઉપરોક્ત સંબંધ નીચે મુજબ ગણતરીની દલીલ દ્વારા મેળવવામાં આવ્યો છેઃ આલેખના શિરોબિંદુઓને ત્રણ સ્તરોમાં હોવાની કલ્પના કરો. સ્તર 0 માં કોઈપણ શિરોબિંદુને મૂળ તરીકે પસંદ કરો. પછી તેના k પડોશીઓ સ્તર 1 માં આવેલા છે, અને અન્ય તમામ શિરોબિંદુઓ સ્તર 2 માં આવેલા છે. સ્તર 1 માં શિરોબિંદુઓ સીધા જ મૂળ સાથે જોડાયેલા હોય છે, તેથી તેમની પાસે λ અન્ય પડોશીઓ મૂળ સાથે સામાન્ય હોવા જોઈએ, અને આ સામાન્ય પડોશીઓ પણ સ્તર 1 માં હોવા જોઈએ. દરેક શિરોબિંદુમાં ડિગ્રી k હોવાથી, સ્તર 2 માં શિરોબિંદુઓ સાથે જોડાવા માટે દરેક સ્તર 1 નોડ માટે ધાર બાકી છે. તેથી, સ્તર 1 અને સ્તર 2 વચ્ચે ધાર છે. સ્તર 2 માં શિરોબિંદુઓ સીધા મૂળ સાથે જોડાયેલા નથી, તેથી તેમની પાસે મૂળ સાથે સામાન્ય પડોશીઓ હોવા જોઈએ, અને આ સામાન્ય પડોશીઓ બધા સ્તર 1 માં હોવા જોઈએ. સ્તર 2 માં શિરોબિંદુઓ છે, અને દરેક સ્તર 1 માં μ શિરોબિંદુઓ સાથે જોડાયેલ છે. તેથી સ્તર 1 અને સ્તર 2 વચ્ચેની ધારની સંખ્યા છે. સ્તર 1 અને સ્તર 2 વચ્ચેની ધાર માટે બે સમીકરણોને સરખાવીને, સંબંધ અનુસરે છે. એડજેસેન્સી મેટ્રિક્સ સમીકરણો ચાલો I ઓળખ મેટ્રિક્સને સૂચવે અને J એ એકના મેટ્રિક્સને સૂચવે, ક્રમના બંને મેટ્રિક્સ v. મજબૂત નિયમિત ગ્રાફનો નિકટતા મેટ્રિક્સ A બે સમીકરણોને સંતોષે છે. પ્રથમઃ જે નિયમિતતાની જરૂરિયાતનું પુનરાવર્તન છે. આ દર્શાવે છે કે k એ ઓલ-વન આઈગનવેક્ટર સાથે અડ્જાસેન્સી મેટ્રિક્સનું આઈગન વેલ્યુ છે. બીજુંઃ જે મજબૂત નિયમિતતા દર્શાવે છે. ડાબી બાજુનું ij-th તત્વ i થી j સુધીના બે પગલાંના રસ્તાઓની સંખ્યા આપે છે. જમણી બાજુની પ્રથમ ટર્મ i થી પાછા i સુધીના બે પગલાંના રસ્તાઓની સંખ્યા આપે છે, એટલે કે k ધાર બહાર અને પાછળ. જ્યારે i અને j સીધા જોડાયેલા હોય ત્યારે બીજો શબ્દ બે-પગલાંના માર્ગોની સંખ્યા આપે છે. જ્યારે i અને j જોડાયેલા ન હોય ત્યારે ત્રીજી ટર્મ અનુરૂપ મૂલ્ય આપે છે. આ ત્રણેય કિસ્સાઓ પરસ્પર વિશિષ્ટ અને સામૂહિક રીતે સંપૂર્ણ હોવાથી, સરળ યોગાત્મક સમાનતા અનુસરે છે. તેનાથી વિપરીત, એક આલેખ કે જેની નિકટતા મેટ્રિક્સ ઉપરોક્ત બંને શરતોને સંતોષે છે અને જે સંપૂર્ણ અથવા શૂન્ય આલેખ નથી તે મજબૂત નિયમિત આલેખ છે. આઇગનવેલ્યુઝ અને ગ્રાફ સ્પેક્ટ્રમ નિકટતા મેટ્રિક્સ A સપ્રમાણ હોવાથી, તે અનુસરે છે કે તેના આઇગનવેક્ટર્સ ઓર્થોગોનલ છે. આપણે પહેલેથી જ એક આઈગનવેક્ટરનું અવલોકન કર્યું છે જે ઉપરના બધાથી બનેલું છે, જે આઈગન વેલ્યુ k ને અનુરૂપ છે. તેથી અન્ય આઈગનવેક્ટર્સ x એ બધાને સંતોષવા જોઈએ જ્યાં J એ પહેલાની જેમ ઓલ-વન મેટ્રિક્સ છે. અગાઉ સ્થાપિત થયેલ સમીકરણને લોઃ અને ઉપરોક્ત સમીકરણને આઈગનવેક્ટર x દ્વારા ગુણાકારોઃ અનુરૂપ આઈગન વેલ્યુ p ને કૉલ કરો (ગ્રાફ પરિમાણ સાથે મૂંઝવણ ન કરો) અને અવેજી કરો, અનેઃ x ને દૂર કરો અને દ્વિઘાત મેળવવા માટે ફરીથી ગોઠવોઃ આ બે વધારાના આઈગનવેલ્યુ આપે છે. આમ મજબૂત નિયમિત મેટ્રિક્સ માટે બરાબર ત્રણ આઈગન વેલ્યુ છે. તેનાથી વિપરીત, માત્ર ત્રણ આઈગન મૂલ્યો સાથે જોડાયેલ નિયમિત આલેખ મજબૂત રીતે નિયમિત છે. મોટા ભાગના મજબૂત નિયમિત આલેખ સાહિત્યમાં પરિભાષાને અનુસરીને, મોટા આઈગન વેલ્યુને ગુણાકાર f સાથે r કહેવામાં આવે છે અને નાના એકને ગુણાકાર g સાથે s કહેવામાં આવે છે. કારણ કે તમામ આઈગન વેલ્યુઓનો સરવાળો એ નિકટતા મેટ્રિક્સનું ટ્રેસ છે, જે આ કિસ્સામાં શૂન્ય છે, તેથી સંબંધિત ગુણાકાર f અને g ની ગણતરી કરી શકાય છેઃ આઈગન વેલ્યુ k પાસે ગુણાકાર 1 છે. આઈગન વેલ્યુમાં બહુમતી છે. આઈગન વેલ્યુમાં બહુમતી છે. જેમ કે ગુણાકાર પૂર્ણાંકો હોવા જ જોઈએ, તેમની અભિવ્યક્તિઓ v, k, μ અને λ ના મૂલ્યો પર વધુ અવરોધો પૂરા પાડે છે. મજબૂત રીતે નિયમિત આલેખ જેમાં અસમાન ગુણાકાર સાથે પૂર્ણાંક આઈગનવેલ્યુ હોય છે. મજબૂત રીતે નિયમિત આલેખ કે જેના માટે સમપ્રમાણ પરિષદ મેટ્રિસીસ સાથેના જોડાણને કારણે પરિષદ આલેખ કહેવામાં આવે છે. તેમના પરિમાણો ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટતાં ઘટ વધુમાં, આ કિસ્સામાં, v એ બ્રુક-રાયસર-ચૌલા પ્રમેય સાથે સંબંધિત બે વર્ગોનો સરવાળો હોવો જોઈએ. આઈગન મૂલ્યો અને તેમના ગુણાકારના વધુ ગુણધર્મો આ પ્રમાણે છેઃ, તેથી આઈગન મૂલ્યો r અને s સાથે an આપવામાં આવે તો, તેના પૂરકમાં આઈગન મૂલ્યો-1-s અને-1-r હોય છે. ઉપસંહાર તરીકે, જો અને માત્ર જો અમુક ક્રમમાં. ક્રેઇન શરતોઃ અને સંપૂર્ણ બંધાયેલઃ અને. ક્લો બાઉન્ડઃ જો, પછી અથવા. જો કોઈપણ પરિમાણોના સમૂહ માટે ઉપરોક્ત શરતોનું ઉલ્લંઘન કરવામાં આવે, તો તે પરિમાણો માટે કોઈ મજબૂત નિયમિત આલેખ અસ્તિત્વમાં નથી. બ્રોવરે અસ્તિત્વ અથવા બિન-અસ્તિત્વની આવી યાદીઓ જો કોઈ હોય તો તેના કારણો સાથે અહીં સંકલિત કરી છે. હોફમેન-સિંગલેટન પ્રમેય ઉપર નોંધ્યા મુજબ, આઈગનવેલ્યુનો ગુણાકાર જેના દ્વારા પૂર્ણાંકો હોવા જોઈએ તે આપવામાં આવે છે. 1960માં, એલન હોફમેન અને રોબર્ટ સિંગલટને λ = 0 અને μ = 1 ધરાવતા મૂરે આલેખ પર લાગુ કરતી વખતે તે અભિવ્યક્તિઓની તપાસ કરી હતી. આવા આલેખ ત્રિકોણથી મુક્ત હોય છે (અન્યથા λ શૂન્ય કરતાં વધી જશે) અને ચતુર્ભુજ (અન્યથા μ 1 કરતાં વધી જશે), તેથી તેમનો ઘેર 5નો હોય છે (સૌથી નાનો ચક્ર લંબાઈ). સમીકરણમાં λ અને μ ના મૂલ્યોને બદલીને, તે જોઈ શકાય છે કે, અને આઈગન વેલ્યુ ગુણાકાર ઘટાડીને શૂન્ય થાય છે. જો અંશ શૂન્ય હોય, તો શક્યતાઓ છેઃ k = 0 અને v = 1 એક શિરોબિંદુ સાથે તુચ્છ આલેખ આપે છે અને કોઈ ધાર નથી, અને k = 2 અને v = 5 5-શિરોબિંદુ ચક્ર આલેખ આપે છે, જે સામાન્ય રીતે નિયમિત પંચકોણ તરીકે દોરવામાં આવે છે. જો છેદ પૂર્ણાંક t હોય, તો તે એક સંપૂર્ણ વર્ગ છે. અવેજીઃ બંને બાજુઓ પૂર્ણાંકો હોવાથી, તે પૂર્ણાંક હોવો જોઈએ, તેથી t એ 15 નો પરિબળ છે, એટલે કે. બદલામાંઃ k = 1 અને v = 2 ધાર સાથે જોડાયેલા બે શિરોબિંદુઓનો તુચ્છ આલેખ આપે છે, k = 3 અને v = 10 પીટરસન આલેખ આપે છે, k = 7 અને v = 50 હોફમેન-સિંગલેટન આલેખ આપે છે, જે આ વિશ્લેષણ દરમિયાન હોફમેન અને સિંગલેટન દ્વારા શોધાયો હતો, અને k = 57 અને v = 3250 એક પ્રસિદ્ધ આલેખની આગાહી કરે છે જે ન તો 1960 થી શોધાયો છે, ન તો તેના અસ્તિત્વને નકારી કાઢવામાં આવ્યો છે. હોફમેન-સિંગલેટન પ્રમેય જણાવે છે કે ઉપર સૂચિબદ્ધ આલેખ સિવાય કોઈ મજબૂત નિયમિત ઘેરાવ-5 મૂરે આલેખ નથી. આંશિક ભૂમિતિ સીડેલ સંલગ્નતા મેટ્રિક્સ બે-આલેખ નોંધો સંદર્ભો એન્ડ્રીઝ બ્રોવર અને હેન્ડ્રિક વાન માલ્ડેગેમ (2022), મજબૂત નિયમિત આલેખ પણ જુઓ. કેમ્બ્રિજઃ કેમ્બ્રિજ યુનિવર્સિટી પ્રેસ. . એ. ઇ. બ્રોવર, એ. એમ. કોહેન, અને એ. ન્યુમેયર (1989), ડિસ્ટન્સ રેગ્યુલર ગ્રાફ્સ. બર્લિન, ન્યૂયોર્કઃ સ્પ્રિંગર-વેરલેગ. , ક્રિસ ગોડસિલ અને ગોર્ડન રોયલે (2004), બીજગણિત આલેખ સિદ્ધાંત. ન્યૂ યોર્કઃ સ્પ્રિંગર-વેરલેગ. બાહ્ય લિંક્સ એરિક ડબ્લ્યુ. વેઇઝસ્ટીન, અસંખ્ય ઉદાહરણો સાથે મેથવર્લ્ડ લેખ. ગોર્ડન રોયલે, મોટા આલેખ અને પરિવારોની યાદી. એન્ડ્રીઝ ઇ. બ્રોવર, મજબૂત નિયમિત ગ્રાફના પરિમાણો. બ્રેન્ડન મેકકે, આલેખનો અમુક સંગ્રહ. ટેડ સ્પેન્સ, મહત્તમ 64 શિરોબિંદુઓ પર મજબૂત રીતે નિયમિત આલેખ ધરાવે છે. આલેખ પરિવારો બીજગણિત આલેખ સિદ્ધાંત નિયમિત આલેખ