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>
== यह भी देखें ==
* [[क्यूबिक ग्राफ]] के रूप में दर्शाया जाता है

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


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

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



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