नियमित ग्राफ: Difference between revisions
(Created page with "{{short description|Graph where each vertex has the same number of neighbors}} {{Graph families defined by their automorphisms}} ग्राफ़ सिद्धांत...") |
No edit summary |
||
Line 2: | Line 2: | ||
{{Graph families defined by their automorphisms}} | {{Graph families defined by their automorphisms}} | ||
ग्राफ़ सिद्धांत में, एक नियमित ग्राफ़ एक ग्राफ़ (असतत गणित) होता है जहाँ प्रत्येक वर्टेक्स (ग्राफ़ सिद्धांत) में | ग्राफ़ सिद्धांत में, एक नियमित ग्राफ़ एक ग्राफ़ (असतत गणित) होता है जहाँ प्रत्येक वर्टेक्स (ग्राफ़ सिद्धांत) में निकटतम संख्या समान होती है; यानी हर शीर्ष में एक ही [[डिग्री]] ([[ग्राफ सिद्धांत]]) या वैलेंसी होती है। एक नियमित रूप से [[निर्देशित ग्राफ]]़ को मजबूत स्थिति को भी पूरा करना चाहिए कि प्रत्येक आंतरिक शीर्ष के इंडिग्री और [[ आगे की डिग्री ]] एक दूसरे के बराबर हैं।<ref> | ||
{{Cite book | last = Chen | first = Wai-Kai | title = Graph Theory and its Engineering Applications | publisher = World Scientific | year = 1997 | pages = [https://archive.org/details/graphtheoryitsen00chen/page/29 29] | isbn = 978-981-02-1859-1 | url-access = registration | url = https://archive.org/details/graphtheoryitsen00chen/page/29 }}</ref> डिग्री के शिखर के साथ एक नियमित ग्राफ {{mvar|k}} कहा जाता है{{nowrap|{{mvar|k}}‑regular}} ग्राफ या डिग्री का नियमित ग्राफ {{mvar|k}}. साथ ही, [[ हाथ मिलाना लेम्मा ]] से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है। | {{Cite book | last = Chen | first = Wai-Kai | title = Graph Theory and its Engineering Applications | publisher = World Scientific | year = 1997 | pages = [https://archive.org/details/graphtheoryitsen00chen/page/29 29] | isbn = 978-981-02-1859-1 | url-access = registration | url = https://archive.org/details/graphtheoryitsen00chen/page/29 }}</ref> डिग्री के शिखर के साथ एक नियमित ग्राफ {{mvar|k}} कहा जाता है{{nowrap|{{mvar|k}}‑regular}} ग्राफ या डिग्री का नियमित ग्राफ {{mvar|k}}. साथ ही, [[ हाथ मिलाना लेम्मा ]] से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है। | ||
Line 9: | Line 9: | ||
ए {{nowrap|3-regular}} ग्राफ को [[क्यूबिक ग्राफ]] के रूप में जाना जाता है। | ए {{nowrap|3-regular}} ग्राफ को [[क्यूबिक ग्राफ]] के रूप में जाना जाता है। | ||
एक [[दृढ़ता से नियमित ग्राफ]]़ एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न जोड़े के कोने में समान संख्या होती है {{mvar|l}} | एक [[दृढ़ता से नियमित ग्राफ]]़ एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न जोड़े के कोने में समान संख्या होती है {{mvar|l}} निकटतम की उभयनिष्ठता, और प्रत्येक गैर-निकटवर्ती जोड़ी के शीर्षों की संख्या समान है {{mvar|n}} आम निकटतम में से। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, [[चक्र ग्राफ]]़ और 6 वर्टिकल पर [[ गोलाकार ग्राफ ]]़ हैं। | ||
[[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी के लिए दृढ़ता से नियमित है {{mvar|m}}. | [[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी के लिए दृढ़ता से नियमित है {{mvar|m}}. |
Revision as of 12:25, 3 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‑regular ग्राफ या डिग्री का नियमित ग्राफ k. साथ ही, हाथ मिलाना लेम्मा से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है।
ज़्यादा से ज़्यादा 2 डिग्री के नियमित ग्राफ़ को वर्गीकृत करना आसान है: a 0-regular ग्राफ़ में डिस्कनेक्ट किए गए शीर्ष होते हैं, a 1-regular ग्राफ़ में डिस्कनेक्ट किए गए किनारे होते हैं, और a 2-regular ग्राफ़ में चक्र (ग्राफ़ थ्योरी) और अनंत श्रृंखलाओं के ग्राफ़ का एक असंबद्ध मिलन होता है।
ए 3-regular ग्राफ को क्यूबिक ग्राफ के रूप में जाना जाता है।
एक दृढ़ता से नियमित ग्राफ़ एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न जोड़े के कोने में समान संख्या होती है l निकटतम की उभयनिष्ठता, और प्रत्येक गैर-निकटवर्ती जोड़ी के शीर्षों की संख्या समान है n आम निकटतम में से। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, चक्र ग्राफ़ और 6 वर्टिकल पर गोलाकार ग्राफ ़ हैं।
पूरा ग्राफ Km किसी के लिए दृढ़ता से नियमित है m.
क्रिस्पिन सेंट जेए नैश-विलियम्स द्वारा एक प्रमेय | नैश-विलियम्स का कहना है कि हर k‑regular ग्राफ पर 2k + 1 शीर्षों में हैमिल्टनियन चक्र होता है।
अस्तित्व
यह सर्वविदित है कि ए के लिए आवश्यक और पर्याप्त शर्तें आदेश का नियमित ग्राफ मौजूद हैं ओर वो सम है।
प्रमाण: जैसा कि हम जानते हैं कि एक पूर्ण ग्राफ में अलग-अलग शीर्षों की प्रत्येक जोड़ी एक अद्वितीय किनारे से एक दूसरे से जुड़ी होती है। इसलिए पूरे ग्राफ में किनारे अधिकतम होते हैं और किनारों की संख्या होती है और डिग्री यहाँ है . इसलिए . यह न्यूनतम है एक विशेष के लिए . यह भी ध्यान दें कि यदि किसी नियमित ग्राफ में क्रम है तो किनारों की संख्या है इसलिए सम होना चाहिए। ऐसे मामले में परिसंचारी ग्राफ के लिए उपयुक्त मापदंडों पर विचार करके नियमित ग्राफ बनाना आसान है।
बीजगणितीय गुण
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