View source for क्वार्टिक ग्राफ

गणितीय क्षेत्र में [[ग्राफ सिद्धांत]] एक क्वार्टिक [[ग्राफ (असतत गणित)]] के रूप में होता है, जहां सभी वर्टेक्स के ग्राफ सिद्धांत में [[डिग्री (ग्राफ सिद्धांत)|घात]] 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-[[नियमित ग्राफ]] सिद्धांत के रूप में है।<ref>{{citation
 | last = Toida | first = S.
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0347693
 | pages = 124–133
 | series = Series B
 | title = Construction of quartic graphs
 | volume = 16
 | year = 1974
 | doi=10.1016/0095-8956(74)90054-9| doi-access = free
 }}.</ref>

== उदाहरण ==
[[File:Chvatal Lombardi.svg|thumb|द ग्रैब ग्राफ]]कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में होते है और इस प्रकार वे सम्मिलित होते है
*[[पूरा ग्राफ]] K<sub>5</sub>, 5 शीर्षों वाला एक चतुर्थांश ग्राफ के रूप में होता है और जो सबसे छोटा चतुर्थक ग्राफ होता है।
* च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ के रूप में होता है जो सबसे छोटा क्वार्टिक ग्राफ होता है और जिसमें कोई त्रिभुज नहीं होता है और ये तीन रंगों से रंगने वाला ग्राफ नहीं हो सकता।<ref>{{citation
 | last = Chvátal | first = V. | author-link = Václav Chvátal
 | doi = 10.1016/S0021-9800(70)80057-6
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | pages = 93–94
 | title = The smallest triangle-free 4-chromatic 4-regular graph
 | volume = 9
 | year = 1970| doi-access = free
 }}.</ref>
*[[ फोकमैन ग्राफ | फॉल्कमैन ग्राफ]], 20 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो सबसे छोटा अर्ध-सममितीय ग्राफ होता है।<ref>{{citation
 | last = Folkman | first = Jon
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0224498
 | pages = 215–232
 | title = Regular line-symmetric graphs
 | volume = 3
 | year = 1967
 | doi=10.1016/s0021-9800(67)80069-3| doi-access = free
 }}.</ref>
*[[मेरेडिथ ग्राफ]], 70 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो [[के-वर्टेक्स-कनेक्टेड ग्राफ|4 वर्टेक्स से जुड़ा ग्राफ]] होता है लेकिन कोई [[हैमिल्टनियन पथ|हैमिल्टनियन चक्र]] नहीं होता है और [[क्रिस्पिन नैश-विलियम्स]] के एक अनुमान को रद्द करता है।<ref>{{citation
 | last = Meredith | first = G. H. J.
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0311503
 | pages = 55–60
 | series = Series B
 | title = Regular ''n''-valent ''n''-connected nonHamiltonian non-''n''-edge-colorable graphs
 | volume = 14
 | year = 1973
 | doi=10.1016/s0095-8956(73)80006-1| doi-access = free
 }}.</ref>
प्रत्येक  [[औसत दर्जे का ग्राफ|मध्यवर्ती का ग्राफ]] एक क्वार्टिक [[प्लेनर ग्राफ]] के रूप में होता है और प्रत्येक क्वार्टिक समतल ग्राफ दोहरे प्लेन ग्राफ या मल्टीग्राफ की एक जोड़ी का औसत अंकित ग्राफ होता है।<ref>{{citation
 | last1 = Bondy | first1 = J. A.
 | last2 = Häggkvist | first2 = R.
 | doi = 10.1007/BF02190157
 | issue = 1
 | journal = [[Aequationes Mathematicae]]
 | mr = 623315
 | pages = 42–45
 | title = Edge-disjoint Hamilton cycles in 4-regular planar graphs
 | volume = 22
 | year = 1981}}.</ref> [[गाँठ आरेख|नॉट आरेखण]]  और लिंक आरेख भी क्वार्टिक प्लेन [[मल्टीग्राफ]] के रूप में होता है, जिसमें शीर्ष आरेखण के प्रतिच्छेद का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में नॉट की दो शाखाएँ उस बिंदु पर दूसरी  रेखन को पार करती हैं।<ref>{{citation
 | last = Welsh | first = Dominic J. A. | authorlink = Dominic Welsh
 | contribution = The complexity of knots
 | doi = 10.1016/S0167-5060(08)70385-6
 | location = Amsterdam
 | mr = 1217989
 | pages = 159–171
 | publisher = North-Holland
 | series = Annals of Discrete Mathematics
 | title = Quo vadis, graph theory?
 | volume = 55
 | year = 1993}}.</ref>
== गुण ==
क्योंकि क्वार्टिक ग्राफ सिद्धांत में प्रत्येक शीर्ष की घात सम होती है, और यह प्रत्येक क्वार्टिक ग्राफ से [[ जुड़ा हुआ ग्राफ |जुड़ा हुआ]] एक  [[ यूलर टॉवर |यूलर ग्राफ]] के रूप में होता है। और जैसा कि नियमित द्विदलीय रेखांकन के साथ होता है और सामान्यतः प्रत्येक द्विदलीय चतुर्थक ग्राफ और क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति  में, यूलर ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ [[कलन विधि]] के रूप में संभव है: यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके अनियमित [[ग्राफ गुणनखंडन]] 2-फ़ैक्टर के रूप में मिल जाता है, जो इस स्थिति में समान लंबाई के प्रत्येक चक्र का एक संग्रह के रूप में होता है और ग्राफ के प्रत्येक शीर्ष के ठीक एक चक्र में प्रदर्शित होने के साथ.इन चक्रों में अगली कौन सी धार फिर से चुनी जाती है, जबकि इन चक्रों में फिर से प्रत्येक दूसरे किनारे का चयन करके बिल्कुल ठीक  [[रैखिक समय]] में में मिलती है और इसी रैखिक समय में चार रंगों वाले ग्राफ में रंग भरने के लिए भी इसी विधि का उपयोग किया जाता है।<ref>{{citation
 | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
 | issue = 4
 | journal = International Journal of Computer and Information Sciences
 | mr = 0422081
 | pages = 345–355
 | title = Using Euler partitions to edge color bipartite multigraphs
 | volume = 5
 | year = 1976
 | doi=10.1007/bf00998632}}.</ref>

क्वार्टिक ग्राफ़ में [[हैमिल्टनियन अपघटन]] की एक समान संख्या होती है।<ref>{{citation
 | last = Thomason | first = A. G.
 | journal = Annals of Discrete Mathematics
 | mr = 499124
 | pages = 259–268
 | title = Hamiltonian cycles and uniquely edge colourable graphs
 | volume = 3
 | year = 1978
 | doi=10.1016/s0167-5060(08)70511-9}}.</ref>
== खुली समस्याएं ==
यह एक खुला अनुमान है कि क्या सभी क्वार्टिक हैमिल्टनियन ग्राफ में [[हैमिल्टनियन सर्किट]] की संख्या भी है, या एक से अधिक हैमिल्टनियन सर्किट हैं। उत्तर क्वार्टिक मल्टीग्राफ के लिए गलत माना जाता है।<ref>{{citation
 | last = Fleischner | first = Herbert
 | doi = 10.1002/jgt.3190180503
 | issue = 5
 | journal = Journal of Graph Theory
 | mr = 1283310
 | pages = 449–459
 | title = Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs
 | volume = 18
 | year = 1994}}.</ref>


== यह भी देखें ==
{{commons category|4-regular graphs}}
* [[क्यूबिक ग्राफ]]

== संदर्भ ==
{{reflist}}


==बाहरी संबंध==
*{{mathworld|id=QuarticGraph|title=Quartic Graph}}

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



[[Category: Machine Translated Page]]
[[Category:Created On 17/04/2023]]