Strongly regular graph
ग्राफ सिद्धांत में, एक प्रबल नियमित ग्राफ (एस. आर. जी.) शीर्षों और डिग्री के साथ एक नियमित ग्राफ है जिसमें कुछ दिए गए पूर्णांकों के लिए प्रत्येक दो आसन्न शीर्षों के समान पड़ोसी होते हैं, और प्रत्येक दो गैर-आसन्न शीर्षों के समान पड़ोसी होते हैं। इस तरह के एक मजबूत नियमित ग्राफ को दर्शाया जाता है। इसका पूरक भी दृढ़ता से नियमित हैः एक दृढ़ता से नियमित ग्राफ व्यास 2 के साथ एक दूरी-नियमित ग्राफ है जब भी μ गैर-शून्य होता है। यह हर समय स्थानीय रूप से रैखिक ग्राफ होता है। व्युत्पत्ति एक दृढ़ता से नियमित ग्राफ को साहित्य में एक srg (v, k, λ, μ) के रूप में दर्शाया जाता है। परंपरा के अनुसार, जो ग्राफ परिभाषा को मामूली रूप से संतुष्ट करते हैं, उन्हें विस्तृत अध्ययनों और दृढ़ता से नियमित ग्राफ की सूचियों से बाहर रखा जाता है। इनमें एक या अधिक समान आकार के पूर्ण ग्राफों का असंबद्ध संघ, और उनके पूरक, समान आकार के स्वतंत्र सेटों के साथ पूर्ण बहुपक्षीय ग्राफ शामिल हैं। एंड्रीज़ ब्रोवर और हेंड्रिक वैन माल्डेगेम (देखें #References) वर्णक्रमीय ग्राफ सिद्धांत पर आधारित एक मजबूत नियमित ग्राफ की एक वैकल्पिक लेकिन पूरी तरह से समकक्ष परिभाषा का उपयोग करते हैंः एक मजबूत नियमित ग्राफ एक सीमित नियमित ग्राफ है जिसमें बिल्कुल तीन आइगेनवैल्यू होते हैं, जिनमें से केवल एक गुणन 1 की डिग्री k के बराबर होता है। यह स्वचालित रूप से पूरी तरह से जुड़े ग्राफ (जिनमें केवल दो अलग-अलग आइगेनवैल्यू हैं, तीन नहीं) और डिस्कनेक्टेड ग्राफ (जिनकी डिग्री k की बहुलता विभिन्न जुड़े घटकों की संख्या के बराबर है, जो इसलिए एक से अधिक होगी) को खारिज कर देता है। ब्राउवर सहित अधिकांश साहित्य, बड़े आइगेनवैल्यू को r (गुणन f के साथ) और छोटे को s (गुणन g के साथ) के रूप में संदर्भित करते हैं। इतिहास आर. सी. द्वारा प्रबल रूप से नियमित ग्राफ पेश किए गए थे। 1963 में बोस। उन्होंने 1950 के दशक में वर्णक्रमीय ग्राफ सिद्धांत के तत्कालीन नए क्षेत्र में पहले के काम पर निर्माण किया। उदाहरण लंबाई 5 का चक्र एक एस. आर. जी. (5,2,0,1) है। पीटरसन ग्राफ एक एस. आर. जी. (10,3,0,1) है। क्लेबश ग्राफ एक एस. आर. जी. (16,5,0,2) है। श्रीखंडे ग्राफ एक एस. आर. जी. (16,6,2,2) है जो एक दूरी-संक्रमणशील ग्राफ नहीं है। एन × एन वर्ग रुक का ग्राफ, अर्थात, एक संतुलित पूर्ण द्विदलीय ग्राफ का रेखा ग्राफ एन, एन, एक एस. आर. जी (एन2,2एन-2, एन-2,2) है। इसके लिए मापदंड श्रीखंडे ग्राफ के साथ मेल खाते हैं, लेकिन दोनों ग्राफ समरूप नहीं हैं। एक पूर्ण ग्राफ Kn का रेखाचित्र एक है। चांग ग्राफ एस. आर. जी. (28,12,6,4) हैं, जो के8 के रेखा ग्राफ के समान हैं, लेकिन ये चार ग्राफ समरूप नहीं हैं। क्रम (s, t) का प्रत्येक सामान्यीकृत चतुर्भुज अपने रेखाचित्र के रूप में एक srg ((s + 1) (st + 1), s (t + 1), s-1, t + 1) देता है। उदाहरण के लिए, जी. क्यू. (2,4) एस. आर. जी. (27,10,1,5) को अपने रेखाचित्र के रूप में देता है। श्लाफली ग्राफ एक एस. आर. जी. (27,16,10,8) है। हॉफमैन-सिंगलटन ग्राफ एक एस. आर. जी. (50,7,0,1) है। सिम्स-गेवर्ट्ज़ ग्राफ एक (56,10,0,2) है। एम22 ग्राफ उर्फ मेसनर ग्राफ एक एस. आर. जी. (77,16,0,4) है। ब्रोवर-हेमर्स ग्राफ एक एस. आर. जी. (81,20,1,6) है। हिगमैन-सिम्स ग्राफ एक एस. आर. जी. (100,22,0,6) है। स्थानीय मैकलॉघलिन ग्राफ एक एस. आर. जी. (162,56,10,24) है। कैमरून ग्राफ एक एस. आर. जी. (एस. आर. जी.) (एस. आर. जी.) है। बर्लेकैम्प-वान लिंट-सीडेल ग्राफ एक एस. आर. जी. (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 में चुनें। फिर इसके के पड़ोसी स्तर 1 में स्थित हैं, और अन्य सभी शीर्ष स्तर 2 में स्थित हैं। स्तर 1 में वर्टीस सीधे जड़ से जुड़े होते हैं, इसलिए उनके पास मूल के साथ समान रूप से λ अन्य पड़ोसी होने चाहिए, और ये सामान्य पड़ोसी भी स्तर 1 में होने चाहिए। चूँकि प्रत्येक शीर्ष में डिग्री k होती है, इसलिए स्तर 2 में शीर्षों से जुड़ने के लिए प्रत्येक स्तर 1 नोड के लिए किनारे शेष रहते हैं। इसलिए, स्तर 1 और स्तर 2 के बीच किनारे हैं। स्तर 2 में वर्टीस सीधे जड़ से नहीं जुड़े होते हैं, इसलिए उनके पास मूल के साथ सामान्य पड़ोसी होने चाहिए, और ये सामान्य पड़ोसी सभी स्तर 1 में होने चाहिए। स्तर 2 में शीर्ष हैं, और प्रत्येक स्तर 1 में μ शीर्षों से जुड़ा हुआ है। इसलिए स्तर 1 और स्तर 2 के बीच किनारों की संख्या है। स्तर 1 और स्तर 2 के बीच के किनारों के लिए दो अभिव्यक्तियों की बराबरी करते हुए, संबंध इस प्रकार है। एडजसेंसी मैट्रिक्स समीकरण आइए मैं आइडेंटिटी मैट्रिक्स को दर्शाता हूं और J को एक के मैट्रिक्स को दर्शाता हूं, दोनों क्रम के मैट्रिक्स v. एक प्रबल नियमित ग्राफ का आसन्न मैट्रिक्स A दो समीकरणों को संतुष्ट करता है। पहलाः जो नियमितता आवश्यकता का पुनर्कथन है। इससे पता चलता है कि k ऑल-वन आइगेनवेक्टर के साथ निकटता मैट्रिक्स का एक आइगेनवैल्यू है। दूसराः जो मजबूत नियमितता को व्यक्त करता है। बायीं ओर का ij-th तत्व i से j तक दो-चरणीय पथों की संख्या देता है। दाहिने हाथ की ओर का पहला पद i से i तक दो-चरणीय पथों की संख्या देता है, अर्थात् k किनारे बाहर और पीछे। दूसरा पद दो-चरणीय पथों की संख्या देता है जब i और j सीधे जुड़े होते हैं। तीसरा पद संबंधित मान देता है जब i और j जुड़े नहीं होते हैं। चूँकि ये तीनों मामले पारस्परिक रूप से अनन्य और सामूहिक रूप से संपूर्ण हैं, इसलिए सरल योगात्मक समानता का अनुसरण किया जाता है। इसके विपरीत, एक ग्राफ जिसका निकटता मैट्रिक्स उपरोक्त दोनों स्थितियों को संतुष्ट करता है और जो एक पूर्ण या शून्य ग्राफ नहीं है, एक दृढ़ता से नियमित ग्राफ है। आइगेनवैल्यूज और ग्राफ स्पेक्ट्रम चूंकि निकटता मैट्रिक्स ए सममित है, इसलिए यह इस प्रकार है कि इसके आइगेनवेक्टर ऑर्थोगोनल हैं। हम पहले से ही एक आइगेनवेक्टर को देख चुके हैं जो ऊपर सभी से बना है, जो आइगेनवैल्यू 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 है, तो एक पूर्ण वर्ग है। प्रतिस्थापनः चूँकि दोनों भुजाएँ पूर्णांक हैं, इसलिए एक पूर्णांक होना चाहिए, इसलिए टी 15 का एक कारक है, अर्थात्। बदले मेंः k = 1 और v = 2 एक किनारे से जुड़े दो शीर्षों का एक तुच्छ ग्राफ देता है, k = 3 और v = 10 पीटरसन ग्राफ देता है, k = 7 और v = 50 हॉफमैन-सिंगलेटन ग्राफ देता है, जिसे हॉफमैन और सिंगलटन द्वारा इस विश्लेषण के दौरान खोजा गया था, और k = 57 और v = 3250 एक प्रसिद्ध ग्राफ की भविष्यवाणी करता है जिसकी न तो 1960 से खोज की गई है, और न ही इसके अस्तित्व को गलत ठहराया गया है। हॉफमैन-सिंगलेटन प्रमेय में कहा गया है कि ऊपर सूचीबद्ध ग्राफों को छोड़कर कोई नियमित परिधि-5 मूर ग्राफ नहीं हैं। आंशिक ज्यामिति सीडल निकटता मैट्रिक्स टू-ग्राफ नोट्स संदर्भ एंड्रीस ब्रोवर और हेंड्रिक वैन माल्डेगेम (2022), स्ट्रॉन्गली रेगुलर ग्राफ भी देखें। कैम्ब्रिजः कैम्ब्रिज यूनिवर्सिटी प्रेस। .. ए. ई. ब्रोवर, ए. एम. कोहेन और ए. न्यूमेयर (1989), डिस्टेंस रेगुलर ग्राफ। बर्लिन, न्यूयॉर्कः स्प्रिंगर-वेरलैग। , क्रिस गॉडसिल और गॉर्डन रॉयले (2004), बीजगणितीय ग्राफ सिद्धांत। न्यूयॉर्कः स्प्रिंगर-वेरलैग। बाहरी लिंक एरिक डब्ल्यू. वीज़स्टीन, मैथवर्ल्ड लेख कई उदाहरणों के साथ। गॉर्डन रॉयले, बड़े आलेखों और परिवारों की सूची। एंड्रीज़ ई. ब्रोवर, प्रबल रूप से नियमित ग्राफ के मापदंड। ब्रेंडन मैके, ग्राफ के कुछ संग्रह। टेड स्पेन्स, अधिकतम 64 शीर्षों पर नियमित रूप से ग्राफ करते हैं। ग्राफ परिवार बीजगणितीय ग्राफ सिद्धांत नियमित ग्राफ