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

From Vigyanwiki
No edit summary
No edit summary
 
(16 intermediate revisions by 4 users not shown)
Line 2: Line 2:
{{Graph families defined by their automorphisms}}
{{Graph families defined by their automorphisms}}


ग्राफ़ सिद्धांत में, एक '''नियमित ग्राफ़''' एक ऐसा ग्राफ़ होता है जहाँ प्रत्येक शीर्ष पर निकटतम संख्या समान होती है; यानी हर शीर्ष में एक ही [[डिग्री]] ([[ग्राफ सिद्धांत]]) या वैलेंसी होती है। एक नियमित रूप से [[निर्देशित ग्राफ]] को मजबूत स्थिति को भी पूरा करना चाहिए क्योंकि प्रत्येक आंतरिक शीर्ष की डिग्री और बाहरी डिग्री एक दूसरे के बराबर होती है। <ref>
ग्राफ़ सिद्धांत में, एक '''नियमित ग्राफ़''' एक ऐसा ग्राफ़ होता है जहाँ प्रत्येक शीर्ष पर निकटतम संख्या समान होती है; अर्थात हर शीर्ष में एक ही [[डिग्री]] ([[ग्राफ सिद्धांत]]) या वैलेंसी होती है। एक नियमित रूप से [[निर्देशित ग्राफ]] को मजबूत स्थिति को भी पूरा करना चाहिए क्योंकि प्रत्येक आंतरिक शीर्ष की डिग्री और बाहरी डिग्री एक दूसरे के बराबर होती है। <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-नियमित ग्राफ़ में चक्रों और अनंत श्रृंखलाओं का एक अलग संयोजन होता है।
अधिक से अधिक 2 डिग्री के नियमित ग्राफ़ को वर्गीकृत करना आसान है: 0-नियमित ग्राफ़ में असंगत वर्टिकल होते हैं, 1-नियमित ग्राफ़ में वियोजित किए गए किनारे होते हैं, और 2-नियमित ग्राफ़ में चक्रों और अनंत श्रृंखलाओं का एक अलग संयोजन होता है।


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


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


[[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी के लिए दृढ़ता से नियमित है {{mvar|m}}.
[[पूरा ग्राफ]] {{mvar|K{{sub|m}}}} किसी {{mvar|m}} के लिए निरन्तर प्रयत्न/ से नियमित होते है


क्रिस्पिन सेंट जेए नैश-विलियम्स द्वारा एक प्रमेय | नैश-विलियम्स का कहना है कि हर {{nowrap|{{mvar|k}}‑regular}} ग्राफ पर {{math|2''k'' + 1}} शीर्षों में [[हैमिल्टनियन चक्र]] होता है।
नैश-विलियम्स की एक प्रमेय कहती है कि {{math|2''k'' + 1}} शीर्षों पर प्रत्येक k-नियमित ग्राफ़ में [[हैमिल्टनियन चक्र]] होता है।


<gallery>
<gallery>
Line 25: Line 25:
== अस्तित्व ==
== अस्तित्व ==


यह सर्वविदित है कि ए के लिए आवश्यक और पर्याप्त शर्तें <math>k</math> आदेश का नियमित ग्राफ <math>n</math> मौजूद हैं <math> n \geq k+1 </math> ओर वो <math> nk </math> सम है।
यह सर्वविदित है कि ए के लिए आवश्यक और पर्याप्त शर्तें <math>k</math> आदेश का नियमित ग्राफ <math>n</math> में सम्मलित होता हैं <math> n \geq k+1 </math> ओर वो <math> nk </math> सम है।


प्रमाण: जैसा कि हम जानते हैं कि एक पूर्ण ग्राफ में अलग-अलग शीर्षों की प्रत्येक जोड़ी एक अद्वितीय किनारे से एक दूसरे से जुड़ी होती है। इसलिए पूरे ग्राफ में किनारे अधिकतम होते हैं और किनारों की संख्या होती है <math>\binom{n}{2} = \dfrac{n(n-1)}{2}</math> और डिग्री यहाँ है <math>n-1</math>. इसलिए <math>k=n-1,n=k+1</math>. यह न्यूनतम है <math>n</math> एक विशेष के लिए <math>k</math>. यह भी ध्यान दें कि यदि किसी नियमित ग्राफ में क्रम है <math>n</math> तो किनारों की संख्या है <math>\dfrac{nk}{2}</math> इसलिए <math>nk</math> सम होना चाहिए।
प्रमाण: जैसा कि हम जानते हैं कि एक पूर्ण ग्राफ में अलग-अलग शीर्षों की प्रत्येक युग्म एक अद्वितीय कोर से एक दूसरे से जुड़ी होती है। इसलिए पूरे ग्राफ में किनारे अधिकतम होते हैं और किनारों की संख्या होती है <math>\binom{n}{2} = \dfrac{n(n-1)}{2}</math> और यहाँ डिग्री है <math>n-1</math>. इसलिए <math>k=n-1,n=k+1</math>. यह न्यूनतम है <math>n</math> एक विशेष के लिए <math>k</math>. यह भी ध्यान दें कि यदि किसी नियमित ग्राफ में क्रम है <math>n</math> तो किनारों की संख्या है <math>\dfrac{nk}{2}</math> इसलिए <math>nk</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]] ग्राफ की निरंतर डिग्री होगी। अन्य eigenvalues ​​​​के अनुरूप eigenvectors ओर्थोगोनल हैं <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 का एक नियमित ग्राफ जुड़ा हुआ है अगर और केवल अगर eigenvalue k में बहुलता है। केवल अगर दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।<ref name="Cvetkovic"/>
डिग्री k का एक नियमित ग्राफ युग्म हुआ है अगर और केवल अगर इगेनवलुए k में बहुलता है। "ओनली इफ" दिशा पेरोन-फ्रोबेनियस प्रमेय का परिणाम है।<ref name="Cvetkovic"/>


नियमित और जुड़े हुए रेखांकन के लिए भी एक मानदंड है:
नियमित और युग्म हुए रेखांकन के लिए भी एक मानदंड है: एक ग्राफ युग्म हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ <math>J_{ij}=1</math>, ग्राफ के [[आसन्न बीजगणित]] में है (अर्थात् यह A की शक्तियों का एक रैखिक संयोजन है)।<ref>{{citation
एक ग्राफ जुड़ा हुआ है और नियमित है अगर और केवल अगर जे के मैट्रिक्स के साथ <math>J_{ij}=1</math>, ग्राफ के [[आसन्न बीजगणित]] में है (अर्थात् यह की शक्तियों का एक रैखिक संयोजन है)।<ref>{{citation
  | last = Curtin | first = Brian
  | last = Curtin | first = Brian
  | doi = 10.1007/s10623-004-4857-4
  | doi = 10.1007/s10623-004-4857-4
Line 47: Line 47:
  | volume = 34
  | volume = 34
  | year = 2005}}.</ref>
  | year = 2005}}.</ref>
G को व्यास D और आसन्न मैट्रिक्स के eigenvalues ​​​​के साथ एक 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>
: <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>
== पीढ़ी ==
== पीढ़ी ==
आइसोमॉर्फिज्म तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम मौजूद हैं।<ref>{{cite journal| last=Meringer | first=Markus | year=1999 | title=नियमित रेखांकन का तेजी से निर्माण और पिंजरों का निर्माण| journal=[[Journal of Graph Theory]] | volume=30 | issue=2 | pages=137&ndash;146 | doi= 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G| url=http://www.mathe2.uni-bayreuth.de/markus/pdf/pub/FastGenRegGraphJGT.pdf}}</ref>
समरूपता तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम सम्मलित हैं।<ref>{{cite journal| last=Meringer | first=Markus | year=1999 | title=नियमित रेखांकन का तेजी से निर्माण और पिंजरों का निर्माण| journal=[[Journal of Graph Theory]] | volume=30 | issue=2 | pages=137&ndash;146 | doi= 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G| url=http://www.mathe2.uni-bayreuth.de/markus/pdf/pub/FastGenRegGraphJGT.pdf}}</ref>
 
 
== यह भी देखें ==
== यह भी देखें ==
* [[यादृच्छिक नियमित ग्राफ]]
* [[यादृच्छिक नियमित ग्राफ]]
Line 78: Line 75:


{{Graph classes}}
{{Graph classes}}
{{DEFAULTSORT:Regular Graph}}[[Category: ग्राफ परिवार]] [[Category: नियमित रेखांकन|*]]
{{DEFAULTSORT:Regular Graph}}
 
 


[[Category: Machine Translated Page]]
[[Category:All articles with unsourced statements]]
[[Category:Created On 20/03/2023]]
[[Category:Articles with unsourced statements from March 2020]]
[[Category:Collapse templates|Regular Graph]]
[[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:नियमित रेखांकन|*]]

Latest revision as of 16:04, 17 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-नियमित ग्राफ होने दें . यदि जी द्विपक्षीय नहीं है, तो

[4]

पीढ़ी

समरूपता तक, दी गई डिग्री और शीर्षों की संख्या के साथ सभी नियमित रेखांकन की गणना करने के लिए फास्ट एल्गोरिदम सम्मलित हैं।[5]

यह भी देखें

संदर्भ

  1. Chen, Wai-Kai (1997). Graph Theory and its Engineering Applications. World Scientific. pp. 29. ISBN 978-981-02-1859-1.
  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.


बाहरी संबंध