नियमित ग्राफ

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 के लिए दृढ़ता से नियमित है

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

• 

  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