नियमित ग्राफ: Difference between revisions
(→पीढ़ी) |
(→पीढ़ी) |
||
Line 33: | Line 33: | ||
== बीजगणितीय गुण == | == बीजगणितीय गुण == | ||
A को एक ग्राफ का आसन्न मैट्रिक्स होने दें। फिर ग्राफ नियमित है [[अगर और केवल अगर|कि और केवल अगर]] <math>\textbf{j}=(1, \dots ,1)</math> A का [[आइजन्वेक्टर]] है।<ref name="Cvetkovic">Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> इसका [[eigenvalue]] ग्राफ की निरंतर डिग्री होगी। अन्य इगेनवलुए के अनुरूप आइजन्वेक्टर ओर्थोगोनल हैं <math>\textbf{j}</math>, इसलिए ऐसे आइजन्वेक्टरों के लिए <math>v=(v_1,\dots,v_n)</math>, हमारे पास है<math>\sum_{i=1}^n v_i = 0</math>. | A को एक ग्राफ का आसन्न मैट्रिक्स होने दें। फिर ग्राफ नियमित है [[अगर और केवल अगर|कि और केवल अगर]] <math>\textbf{j}=(1, \dots ,1)</math> A का [[आइजन्वेक्टर]] है।<ref name="Cvetkovic">Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.</ref> इसका [[eigenvalue|इगेनवलुए]] ग्राफ की निरंतर डिग्री होगी। अन्य इगेनवलुए के अनुरूप आइजन्वेक्टर ओर्थोगोनल हैं <math>\textbf{j}</math>, इसलिए ऐसे आइजन्वेक्टरों के लिए <math>v=(v_1,\dots,v_n)</math>, हमारे पास है<math>\sum_{i=1}^n v_i = 0</math>. | ||
डिग्री k का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर | डिग्री k का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर इगेनवलुए k में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।<ref name="Cvetkovic"/> | ||
नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ <math>J_{ij}=1</math>, ग्राफ के [[आसन्न बीजगणित]] में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।<ref>{{citation | नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ <math>J_{ij}=1</math>, ग्राफ के [[आसन्न बीजगणित]] में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।<ref>{{citation |
Revision as of 15:24, 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] इसका इगेनवलुए ग्राफ की निरंतर डिग्री होगी। अन्य इगेनवलुए के अनुरूप आइजन्वेक्टर ओर्थोगोनल हैं , इसलिए ऐसे आइजन्वेक्टरों के लिए , हमारे पास है.
डिग्री k का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर इगेनवलुए k में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।[2]
नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ , ग्राफ के आसन्न बीजगणित में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।[3]
G को व्यास D और आसन्न मैट्रिक्स के इगेनवलुए के साथ एक 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