नियमित ग्राफ: Difference between revisions

Latest revision as of 16:04, 17 April 2023

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

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

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

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

पूरा ग्राफ $K m$ किसी $m$ के लिए निरन्तर प्रयत्न/ से नियमित होते है

नैश-विलियम्स की एक प्रमेय कहती है कि $2 k + 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 का आइजन्वेक्टर है।^[2] इसका इगेनवलुए ग्राफ की निरंतर डिग्री होगी। अन्य इगेनवलुए के अनुरूप आइजन्वेक्टर ओर्थोगोनल हैं ${\textbf {j}}$ , इसलिए ऐसे आइजन्वेक्टरों के लिए $v=(v_{1},\dots ,v_{n})$ , हमारे पास है $\sum _{i=1}^{n}v_{i}=0$ .

डिग्री k का एक नियमित ग्राफ युग्म हुआ है अगर और केवल अगर इगेनवलुए k में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।^[2]

नियमित और युग्म हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ युग्म हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ $J_{ij}=1$ , ग्राफ के आसन्न बीजगणित में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।^[3]

G को व्यास D और आसन्न मैट्रिक्स के इगेनवलुए के साथ एक k-नियमित ग्राफ होने दें $k=\lambda _{0}>\lambda _{1}\geq \cdots \geq \lambda _{n-1}$ . यदि जी द्विपक्षीय नहीं है, तो

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

^[4]

पीढ़ी

समरूपता तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम सम्मलित हैं।^[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

[1] Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.

[Cvetkovic-2] 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.

[3] 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.

[4] [1]^{[citation needed]}

[5] 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.

[1]

[2]

[3]

[4]

[5]

@@ Line 3: / Line 3: @@
 ग्राफ़ सिद्धांत में, एक '''नियमित ग्राफ़''' एक ऐसा ग्राफ़ होता है जहाँ प्रत्येक शीर्ष पर निकटतम संख्या समान होती है; अर्थात हर शीर्ष में एक ही [[डिग्री]] ([[ग्राफ सिद्धांत]]) या वैलेंसी होती है। एक नियमित रूप से [[निर्देशित ग्राफ]] को मजबूत स्थिति को भी पूरा करना चाहिए क्योंकि प्रत्येक आंतरिक शीर्ष की डिग्री और बाहरी डिग्री एक दूसरे के बराबर होती है। <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}}‑नियामक}} ग्राफ या डिग्री {{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}}‑नियामक}} ग्राफ या डिग्री {{mvar|k}} का नियमित ग्राफ कहा जाता है। साथ ही, [[ हाथ मिलाना लेम्मा |हैंडशेकिंग लेम्मा]] से, एक नियमित ग्राफ़ में विषम डिग्री वाले शीर्षों की सम संख्या होती है।
 अधिक से अधिक 2 डिग्री के नियमित ग्राफ़ को वर्गीकृत करना आसान है: 0-नियमित ग्राफ़ में असंगत वर्टिकल होते हैं, 1-नियमित ग्राफ़ में वियोजित किए गए किनारे होते हैं, और 2-नियमित ग्राफ़ में चक्रों और अनंत श्रृंखलाओं का एक अलग संयोजन होता है।
@@ Line 9: / Line 9: @@
 एक 3-नियमित ग्राफ को क्यूबिक ग्राफ के रूप में जाना जाता है।
-एक [[दृढ़ता से नियमित ग्राफ]] एक नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न युग्म के कोने में समान संख्या {{mvar|l}} होती है उभयनिष्ठ निकटतम की संख्या, और शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म में उभयनिष्ठ निकटतम की समान संख्या ''n'' है। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, [[चक्र ग्राफ]] और 6 वर्टिकल पर [[ गोलाकार ग्राफ |गोलाकार ग्राफ]] होता हैं।
+एक [[दृढ़ता से नियमित ग्राफ]] वह नियमित ग्राफ़ होता है जहां प्रत्येक आसन्न युग्म के किनारों में समान संख्या {{mvar|l}} होती है उभयनिष्ठ निकटतम की संख्या, और शीर्षों के प्रत्येक गैर-निकटवर्ती युग्म में उभयनिष्ठ निकटतम की समान संख्या ''n'' है। सबसे छोटे ग्राफ़ जो नियमित हैं लेकिन दृढ़ता से नियमित नहीं हैं, [[चक्र ग्राफ]] और 6 वर्टिकल पर [[ गोलाकार ग्राफ |गोलाकार ग्राफ]] होता हैं।
 [[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी {{mvar|m}} के लिए निरन्तर प्रयत्न/ से नियमित होते है
@@ 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 में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।<ref name="Cvetkovic"/>
+डिग्री k का एक नियमित ग्राफ युग्म हुआ है अगर और केवल अगर इगेनवलुए k में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।<ref name="Cvetkovic"/>
 नियमित और युग्म हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ युग्म हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ <math>J_{ij}=1</math>, ग्राफ के [[आसन्न बीजगणित]] में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।<ref>{{citation
@@ Line 48: / Line 48: @@
   | year = 2005}}.</ref>
-G को व्यास D और आसन्न मैट्रिक्स के इगेनवलुए के साथ एक  k-नियमित ग्राफ होने दें <math>k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math>. यदि जी द्विपक्षीय नहीं है, तो
+G को व्यास D और आसन्न मैट्रिक्स के इगेनवलुए के साथ एक k-नियमित ग्राफ होने दें <math>k=\lambda_0 >\lambda_1\geq \cdots\geq\lambda_{n-1}</math>. यदि जी द्विपक्षीय नहीं है, तो
 : <math>D\leq \frac{\log{(n-1)}}{\log(\lambda_0/\lambda_1)}+1. </math><ref>[http://personal.plattsburgh.edu/quenelgt/pubpdf/diamest.pdf]{{citation needed|date=March 2020}}</ref>
@@ Line 75: / Line 75: @@
 {{Graph classes}}
-{{DEFAULTSORT:Regular Graph}}[[Category: ग्राफ परिवार]] [[Category: नियमित रेखांकन|*]]
+{{DEFAULTSORT:Regular Graph}}
+[[Category:All articles with unsourced statements]]
+[[Category:Articles with unsourced statements from March 2020]]
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates|Regular Graph]]
-[[Category:Created On 20/03/2023]]
+[[Category:Commons category link is locally defined|Regular Graph]]
+[[Category:Created On 20/03/2023|Regular Graph]]
+[[Category:Lua-based templates|Regular Graph]]
+[[Category:Machine Translated Page|Regular Graph]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Regular Graph]]
+[[Category:Pages with script errors|Regular Graph]]
+[[Category:Sidebars with styles needing conversion|Regular Graph]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Regular Graph]]
+[[Category:Templates generating microformats|Regular Graph]]
+[[Category:Templates that add a tracking category|Regular Graph]]
+[[Category:Templates that are not mobile friendly|Regular Graph]]
+[[Category:Templates that generate short descriptions|Regular Graph]]
+[[Category:Templates using TemplateData|Regular Graph]]
+[[Category:Wikipedia metatemplates|Regular Graph]]
+[[Category:ग्राफ परिवार|Regular Graph]]
+[[Category:नियमित रेखांकन|*]]

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	[[symmetric graph\|t-transitive, $t \geq 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

v t e Graph classes
Classes	Aperiodic Apex Biased Dense Moore Overfull Quartic Simplex Regular
(Temporary) Specific graphs	Bull Butterfly Diamond McGee Path Planar Null
Graph properties

Anonymous

Search

नियमित ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:04, 17 April 2023

Contents

अस्तित्व

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

पीढ़ी

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

नियमित ग्राफ: Difference between revisions

Latest revision as of 16:04, 17 April 2023

अस्तित्व

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

पीढ़ी

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories