नियमित ग्राफ: Difference between revisions
No edit summary |
No edit summary |
||
Line 11: | Line 11: | ||
एक [[दृढ़ता से नियमित ग्राफ]] एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न युग्म के कोने में समान संख्या {{mvar|l}} होती है उभयनिष्ठ निकटतम की संख्या, और शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म में उभयनिष्ठ निकटतम की समान संख्या ''n'' है। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, [[चक्र ग्राफ]] और 6 वर्टिकल पर [[ गोलाकार ग्राफ |गोलाकार ग्राफ]] होता हैं। | एक [[दृढ़ता से नियमित ग्राफ]] एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न युग्म के कोने में समान संख्या {{mvar|l}} होती है उभयनिष्ठ निकटतम की संख्या, और शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म में उभयनिष्ठ निकटतम की समान संख्या ''n'' है। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, [[चक्र ग्राफ]] और 6 वर्टिकल पर [[ गोलाकार ग्राफ |गोलाकार ग्राफ]] होता हैं। | ||
[[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी | [[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी {{mvar|m}} के लिए दृढ़ता से नियमित है | ||
नैश-विलियम्स की एक प्रमेय कहती है कि {{math|2''k'' + 1}} शीर्षों पर प्रत्येक k-नियमित ग्राफ़ में [[हैमिल्टनियन चक्र]] होता है। | |||
<gallery> | <gallery> |
Revision as of 14:16, 4 April 2023
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 |
ग्राफ़ सिद्धांत में, एक नियमित ग्राफ़ एक ऐसा ग्राफ़ होता है जहाँ प्रत्येक शीर्ष पर निकटतम संख्या समान होती है; यानी हर शीर्ष में एक ही डिग्री (ग्राफ सिद्धांत) या वैलेंसी होती है। एक नियमित रूप से निर्देशित ग्राफ को मजबूत स्थिति को भी पूरा करना चाहिए क्योंकि प्रत्येक आंतरिक शीर्ष की डिग्री और बाहरी डिग्री एक दूसरे के बराबर होती है। [1] डिग्री k के शीर्ष वाले नियमित ग्राफ़ को k‑नियामक ग्राफ या डिग्री k का नियमित ग्राफ कहा जाता है। साथ ही, हैंडशेकिंग लेम्मा से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है।
अधिक से अधिक 2 डिग्री के नियमित ग्राफ़ को वर्गीकृत करना आसान है: 0-नियमित ग्राफ़ में डिस्कनेक्टेड वर्टिकल होते हैं, 1-नियमित ग्राफ़ में वियोजित किए गए किनारे होते हैं, और 2-नियमित ग्राफ़ में चक्रों और अनंत श्रृंखलाओं का एक अलग संयोजन होता है।
एक 3-नियमित ग्राफ को क्यूबिक ग्राफ के रूप में जाना जाता है।
एक दृढ़ता से नियमित ग्राफ एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न युग्म के कोने में समान संख्या l होती है उभयनिष्ठ निकटतम की संख्या, और शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म में उभयनिष्ठ निकटतम की समान संख्या n है। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, चक्र ग्राफ और 6 वर्टिकल पर गोलाकार ग्राफ होता हैं।
पूरा ग्राफ Km किसी m के लिए दृढ़ता से नियमित है
नैश-विलियम्स की एक प्रमेय कहती है कि 2k + 1 शीर्षों पर प्रत्येक k-नियमित ग्राफ़ में हैमिल्टनियन चक्र होता है।
अस्तित्व
यह सर्वविदित है कि ए के लिए आवश्यक और पर्याप्त शर्तें आदेश का नियमित ग्राफ मौजूद हैं ओर वो सम है।
प्रमाण: जैसा कि हम जानते हैं कि एक पूर्ण ग्राफ में अलग-अलग शीर्षों की प्रत्येक जोड़ी एक अद्वितीय किनारे से एक दूसरे से जुड़ी होती है। इसलिए पूरे ग्राफ में किनारे अधिकतम होते हैं और किनारों की संख्या होती है और डिग्री यहाँ है . इसलिए . यह न्यूनतम है एक विशेष के लिए . यह भी ध्यान दें कि यदि किसी नियमित ग्राफ में क्रम है तो किनारों की संख्या है इसलिए सम होना चाहिए। ऐसे मामले में परिसंचारी ग्राफ के लिए उपयुक्त मापदंडों पर विचार करके नियमित ग्राफ बनाना आसान है।
बीजगणितीय गुण
A को एक ग्राफ का आसन्न मैट्रिक्स होने दें। फिर ग्राफ नियमित है अगर और केवल अगर A का आइजन्वेक्टर है।[2] इसका eigenvalue ग्राफ की निरंतर डिग्री होगी। अन्य eigenvalues के अनुरूप eigenvectors ओर्थोगोनल हैं , इसलिए ऐसे ईजेनवेक्टरों के लिए , अपने पास .
डिग्री k का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर eigenvalue k में बहुलता है। केवल अगर दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।[2]
नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ , ग्राफ के आसन्न बीजगणित में है (अर्थात् यह ए की शक्तियों का एक रैखिक संयोजन है)।[3] G को व्यास D और आसन्न मैट्रिक्स के eigenvalues के साथ एक k-नियमित ग्राफ होने दें . यदि जी द्विपक्षीय नहीं है, तो
पीढ़ी
आइसोमॉर्फिज्म तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम मौजूद हैं।[5]
यह भी देखें
- यादृच्छिक नियमित ग्राफ
- मजबूत नियमित ग्राफ
- मूर ग्राफ
- केज ग्राफ
- अत्यधिक अनियमित ग्राफ
संदर्भ
- ↑ Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
- ↑ 2.0 2.1 Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.
- ↑ Curtin, Brian (2005), "Algebraic characterizations of graph regularity conditions", Designs, Codes and Cryptography, 34 (2–3): 241–248, doi:10.1007/s10623-004-4857-4, MR 2128333.
- ↑ [1][citation needed]
- ↑ Meringer, Markus (1999). "नियमित रेखांकन का तेजी से निर्माण और पिंजरों का निर्माण" (PDF). Journal of Graph Theory. 30 (2): 137–146. doi:10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.
बाहरी संबंध
- 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