नियमित ग्राफ

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph|t-transitive, t ≥ 2]]		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

ग्राफ़ सिद्धांत में, एक नियमित ग्राफ़ एक ऐसा ग्राफ़ होता है जहाँ प्रत्येक शीर्ष पर निकटतम संख्या समान होती है; यानी हर शीर्ष में एक ही डिग्री (ग्राफ सिद्धांत) या वैलेंसी होती है। एक नियमित रूप से निर्देशित ग्राफ को मजबूत स्थिति को भी पूरा करना चाहिए क्योंकि प्रत्येक आंतरिक शीर्ष की डिग्री और बाहरी डिग्री एक दूसरे के बराबर होती है। डिग्री k के शीर्ष वाले नियमित ग्राफ़ को k‑नियामक ग्राफ या डिग्री k का नियमित ग्राफ कहा जाता है। साथ ही, हैंडशेकिंग लेम्मा से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है।

अधिक से अधिक 2 डिग्री के नियमित ग्राफ़ को वर्गीकृत करना आसान है: 0-नियमित ग्राफ़ में डिस्कनेक्टेड वर्टिकल होते हैं, 1-नियमित ग्राफ़ में वियोजित किए गए किनारे होते हैं, और 2-नियमित ग्राफ़ में चक्रों और अनंत श्रृंखलाओं का एक अलग संयोजन होता है।

एक 3-नियमित ग्राफ को क्यूबिक ग्राफ के रूप में जाना जाता है।

एक दृढ़ता से नियमित ग्राफ़ एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न जोड़े के कोने में समान संख्या होती है l निकटतम की उभयनिष्ठता, और प्रत्येक गैर-निकटवर्ती जोड़ी के शीर्षों की संख्या समान है n आम निकटतम में से। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, चक्र ग्राफ़ और 6 वर्टिकल पर गोलाकार ग्राफ ़ हैं।

पूरा ग्राफ K_m किसी के लिए दृढ़ता से नियमित है m.

क्रिस्पिन सेंट जेए नैश-विलियम्स द्वारा एक प्रमेय | नैश-विलियम्स का कहना है कि हर k‑regular ग्राफ पर 2k + 1 शीर्षों में हैमिल्टनियन चक्र होता है।

• 

  0-नियमित ग्राफ

• 

  1-नियमित ग्राफ

• 

  2-नियमित ग्राफ

• 

  3-नियमित ग्राफ

अस्तित्व

यह सर्वविदित है कि ए के लिए आवश्यक और पर्याप्त शर्तें $k$ आदेश का नियमित ग्राफ $n$ मौजूद हैं $n\geq k+1$ ओर वो $nk$ सम है।

प्रमाण: जैसा कि हम जानते हैं कि एक पूर्ण ग्राफ में अलग-अलग शीर्षों की प्रत्येक जोड़ी एक अद्वितीय किनारे से एक दूसरे से जुड़ी होती है। इसलिए पूरे ग्राफ में किनारे अधिकतम होते हैं और किनारों की संख्या होती है ${\binom {n}{2}}={\dfrac {n(n-1)}{2}}$ और डिग्री यहाँ है $n-1$. इसलिए $k=n-1,n=k+1$. यह न्यूनतम है $n$ एक विशेष के लिए $k$. यह भी ध्यान दें कि यदि किसी नियमित ग्राफ में क्रम है $n$ तो किनारों की संख्या है ${\dfrac {nk}{2}}$ इसलिए $nk$ सम होना चाहिए। ऐसे मामले में परिसंचारी ग्राफ के लिए उपयुक्त मापदंडों पर विचार करके नियमित ग्राफ बनाना आसान है।

बीजगणितीय गुण

A को एक ग्राफ का आसन्न मैट्रिक्स होने दें। फिर ग्राफ नियमित है अगर और केवल अगर ${\textbf {j}}=(1,\dots ,1)$ A का आइजन्वेक्टर है। इसका eigenvalue ग्राफ की निरंतर डिग्री होगी। अन्य eigenvalues ​​​​के अनुरूप eigenvectors ओर्थोगोनल हैं ${\textbf {j}}$, इसलिए ऐसे ईजेनवेक्टरों के लिए $v=(v_{1},\dots ,v_{n})$, अपने पास $\sum _{i=1}^{n}v_{i}=0$.

डिग्री k का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर eigenvalue k में बहुलता है। केवल अगर दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।

नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ $J_{ij}=1$, ग्राफ के आसन्न बीजगणित में है (अर्थात् यह ए की शक्तियों का एक रैखिक संयोजन है)। G को व्यास D और आसन्न मैट्रिक्स के eigenvalues ​​​​के साथ एक k-नियमित ग्राफ होने दें $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$. यदि जी द्विपक्षीय नहीं है, तो

$D\leq {\frac {\log {(n-1)}}{\log(\lambda _{0}/\lambda _{1})}}+1.$

पीढ़ी

आइसोमॉर्फिज्म तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम मौजूद हैं।

यह भी देखें

• यादृच्छिक नियमित ग्राफ
• मजबूत नियमित ग्राफ
• मूर ग्राफ
• केज ग्राफ
• अत्यधिक अनियमित ग्राफ

बाहरी संबंध

• Weisstein, Eric W. "Regular Graph". MathWorld.
• Weisstein, Eric W. "Strongly Regular Graph". MathWorld.
• GenReg software and data by Markus Meringer.
• Nash-Williams, Crispin (1969), Valency Sequences which force graphs to have Hamiltonian Circuits, University of Waterloo Research Report, Waterloo, Ontario: University of Waterloo