क्वार्टिक ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
गणितीय क्षेत्र में [[ग्राफ सिद्धांत]] एक क्वार्टिक [[ग्राफ (असतत गणित)]] के रूप में होता है, जहां सभी वर्टेक्स के ग्राफ सिद्धांत में [[डिग्री (ग्राफ सिद्धांत)|घात]] 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-[[नियमित ग्राफ]] सिद्धांत के रूप में है।<ref>{{citation
गणितीय [[ग्राफ सिद्धांत]] के क्षेत्र में क्वार्टिक [[ग्राफ]] एक असतत गणित ग्राफ के रूप में है, जहां सभी शीर्षों की [[डिग्री (ग्राफ सिद्धांत)|घात]] 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-[[नियमित ग्राफ]] सिद्धांत के रूप में है।<ref>{{citation
  | last = Toida | first = S.
  | last = Toida | first = S.
  | journal = [[Journal of Combinatorial Theory]]
  | journal = [[Journal of Combinatorial Theory]]
Line 12: Line 12:


== उदाहरण ==
== उदाहरण ==
[[File:Chvatal Lombardi.svg|thumb|द ग्रैब ग्राफ]]कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में होते है और इस प्रकार वे सम्मिलित होते है
[[File:Chvatal Lombardi.svg|thumb|च्वाताल ग्राफ के रूप में होते है ]]कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में सम्मिलित होते है।
*[[पूरा ग्राफ]] K<sub>5</sub>, 5 शीर्षों वाला एक चतुर्थांश ग्राफ के रूप में होता है और जो सबसे छोटा चतुर्थक ग्राफ होता है।
*[[पूरा ग्राफ]] K<sub>5</sub>,एक क्वार्टिक ग्राफ है जिसमें 5 शीर्षों वाला एक चतुर्थांश ग्राफ होता है और जो सबसे छोटा क्वार्टिक ग्राफ होता है।
* च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ के रूप में होता है जो सबसे छोटा क्वार्टिक ग्राफ होता है और जिसमें कोई त्रिभुज नहीं होता है और ये तीन रंगों से रंगने वाला ग्राफ नहीं हो सकता।<ref>{{citation
* च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ के रूप में है जो सबसे छोटा क्वार्टिक ग्राफ होता है और जिसमें कोई त्रिभुज नहीं होता है और ये तीन रंगों से रंगने वाला ग्राफ के रूप में नहीं होता है।<ref>{{citation
  | last = Chvátal | first = V. | author-link = Václav Chvátal
  | last = Chvátal | first = V. | author-link = Václav Chvátal
  | doi = 10.1016/S0021-9800(70)80057-6
  | doi = 10.1016/S0021-9800(70)80057-6
Line 45: Line 45:
  | doi=10.1016/s0095-8956(73)80006-1| doi-access = free
  | doi=10.1016/s0095-8956(73)80006-1| doi-access = free
  }}.</ref>
  }}.</ref>
प्रत्येक [[औसत दर्जे का ग्राफ|मध्यवर्ती का ग्राफ]] एक क्वार्टिक [[प्लेनर ग्राफ]] के रूप में होता है और प्रत्येक क्वार्टिक समतल ग्राफ दोहरे प्लेन ग्राफ या मल्टीग्राफ की एक जोड़ी का औसत अंकित ग्राफ होता है।<ref>{{citation
प्रत्येक [[औसत दर्जे का ग्राफ|मध्यवर्ती का ग्राफ]] एक क्वार्टिक [[प्लेनर ग्राफ|समतल ग्राफ]] होता है और प्रत्येक क्वार्टिक समतल ग्राफ दोहरे समतल ग्राफ या मल्टीग्राफ के युग्म का माध्य ग्राफ के रूप में है।<ref>{{citation
  | last1 = Bondy | first1 = J. A.
  | last1 = Bondy | first1 = J. A.
  | last2 = Häggkvist | first2 = R.
  | last2 = Häggkvist | first2 = R.
Line 55: Line 55:
  | title = Edge-disjoint Hamilton cycles in 4-regular planar graphs
  | title = Edge-disjoint Hamilton cycles in 4-regular planar graphs
  | volume = 22
  | volume = 22
  | year = 1981}}.</ref> [[गाँठ आरेख|नॉट आरेखण]] और लिंक आरेख भी क्वार्टिक प्लेन [[मल्टीग्राफ]] के रूप में होता है, जिसमें शीर्ष आरेखण के प्रतिच्छेद का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में नॉट की दो शाखाएँ उस बिंदु पर दूसरी रेखन को पार करती हैं।<ref>{{citation
  | year = 1981}}.</ref> [[गाँठ आरेख|नॉट आरेखण]] और लिंक आरेख भी क्वार्टिक समतल [[मल्टीग्राफ]] के रूप में होता है, जिसमें शीर्ष आरेखण के प्रतिच्छेद का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में नॉट की दो शाखाएँ उस बिंदु पर दूसरी रेखन को पार करती हैं।<ref>{{citation
  | last = Welsh | first = Dominic J. A. | authorlink = Dominic Welsh
  | last = Welsh | first = Dominic J. A. | authorlink = Dominic Welsh
  | contribution = The complexity of knots
  | contribution = The complexity of knots
Line 68: Line 68:
  | year = 1993}}.</ref>
  | year = 1993}}.</ref>
== गुण ==
== गुण ==
क्योंकि क्वार्टिक ग्राफ सिद्धांत में प्रत्येक शीर्ष की घात सम होती है, और यह प्रत्येक क्वार्टिक ग्राफ से [[ जुड़ा हुआ ग्राफ |जुड़ा हुआ]] एक [[ यूलर टॉवर |यूलर ग्राफ]] के रूप में होता है। और जैसा कि नियमित द्विदलीय रेखांकन के साथ होता है और सामान्यतः प्रत्येक द्विदलीय चतुर्थक ग्राफ और क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति में, यूलर ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ [[कलन विधि]] के रूप में संभव है: यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके अनियमित [[ग्राफ गुणनखंडन]] 2-फ़ैक्टर के रूप में मिल जाता है, जो इस स्थिति में समान लंबाई के प्रत्येक चक्र का एक संग्रह के रूप में होता है और ग्राफ के प्रत्येक शीर्ष के ठीक एक चक्र में प्रदर्शित होने के साथ.इन चक्रों में अगली कौन सी धार फिर से चुनी जाती है, जबकि इन चक्रों में फिर से प्रत्येक दूसरे किनारे का चयन करके बिल्कुल ठीक [[रैखिक समय]] में में मिलती है और इसी रैखिक समय में चार रंगों वाले ग्राफ में रंग भरने के लिए भी इसी विधि का उपयोग किया जाता है।<ref>{{citation
क्योंकि क्वार्टिक ग्राफ सिद्धांत में प्रत्येक शीर्ष की घात धनात्मक होती है और यह प्रत्येक क्वार्टिक ग्राफ से जुड़ा होता है और यह एक [[ यूलर टॉवर |यूलर ग्राफ]] के रूप में होता है जैसा कि नियमित द्विदलीय रेखांकन के साथ होता है और सामान्यतः प्रत्येक द्विदलीय चतुर्थक ग्राफ और क्वार्टिक ग्राफ में एक परिपूर्ण मेल होता है। इस स्थिति में यूलर ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ [[कलन विधि]] के रूप में संभव है यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके अनियमित [[ग्राफ गुणनखंडन]] 2-फ़ैक्टर के रूप में मिल जाता है, जो इस स्थिति में समान लंबाई के प्रत्येक चक्र का एक संग्रह के रूप में होता है और ग्राफ के प्रत्येक शीर्ष के ठीक एक चक्र में प्रदर्शित होने के साथ.इन चक्रों में अगली कौन सी धार फिर से चुनी जाती है, जबकि इन चक्रों में फिर से प्रत्येक दूसरे किनारे का चयन करके बिल्कुल ठीक [[रैखिक समय]] में में मिलती है और इस विधि का उपयोग करके आप रेखीय समय में चार रंगों वाले ग्राफ के किनारों को भी रंगीन कर सकते हैं।<ref>{{citation
  | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
  | last = Gabow | first = Harold N. | author-link = Harold N. Gabow
  | issue = 4
  | issue = 4
Line 88: Line 88:
  | year = 1978
  | year = 1978
  | doi=10.1016/s0167-5060(08)70511-9}}.</ref>
  | doi=10.1016/s0167-5060(08)70511-9}}.</ref>
== खुली समस्याएं ==
== विवृत  समस्याएं ==
यह एक खुला अनुमान है कि क्या सभी क्वार्टिक हैमिल्टनियन ग्राफ में [[हैमिल्टनियन सर्किट]] की संख्या भी है, या एक से अधिक हैमिल्टनियन सर्किट हैं। उत्तर क्वार्टिक मल्टीग्राफ के लिए गलत माना जाता है।<ref>{{citation
यह एक अनुमान है कि सभी क्वार्टिक हैमिल्टनियन ग्राफ के आलेख के समान संख्या में [[हैमिल्टनियन परिपथ]] होते हैं और यह एक से अधिक हैमिल्टनियन परिपथ के रूप मेंहोते हैं और क्वार्टिक मल्टीग्राफ के लिए इसका जवाब गलत माना जाता है।<ref>{{citation
  | last = Fleischner | first = Herbert
  | last = Fleischner | first = Herbert
  | doi = 10.1002/jgt.3190180503
  | doi = 10.1002/jgt.3190180503
Line 99: Line 99:
  | volume = 18
  | volume = 18
  | year = 1994}}.</ref>
  | year = 1994}}.</ref>
== यह भी देखें ==
== यह भी देखें ==
{{commons category|4-regular graphs}}
* [[क्यूबिक ग्राफ]] के रूप में दर्शाया जाता है
* [[क्यूबिक ग्राफ]]


== संदर्भ ==
== संदर्भ ==
Line 113: Line 110:


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


[[Category: Machine Translated Page]]
[[Category:Created On 17/04/2023|Quartic Graph]]
[[Category:Created On 17/04/2023]]
[[Category:Machine Translated Page|Quartic Graph]]
[[Category:Pages with script errors|Quartic Graph]]
[[Category:Templates Vigyan Ready|Quartic Graph]]
[[Category:ग्राफ परिवार|Quartic Graph]]
[[Category:नियमित रेखांकन|Quartic Graph]]

Latest revision as of 13:54, 1 May 2023

गणितीय ग्राफ सिद्धांत के क्षेत्र में क्वार्टिक ग्राफ एक असतत गणित ग्राफ के रूप में है, जहां सभी शीर्षों की घात 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-नियमित ग्राफ सिद्धांत के रूप में है।[1]

उदाहरण

च्वाताल ग्राफ के रूप में होते है

कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में सम्मिलित होते है।

  • पूरा ग्राफ K5,एक क्वार्टिक ग्राफ है जिसमें 5 शीर्षों वाला एक चतुर्थांश ग्राफ होता है और जो सबसे छोटा क्वार्टिक ग्राफ होता है।
  • च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ के रूप में है जो सबसे छोटा क्वार्टिक ग्राफ होता है और जिसमें कोई त्रिभुज नहीं होता है और ये तीन रंगों से रंगने वाला ग्राफ के रूप में नहीं होता है।[2]
  • फॉल्कमैन ग्राफ, 20 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो सबसे छोटा अर्ध-सममितीय ग्राफ होता है।[3]
  • मेरेडिथ ग्राफ, 70 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो 4 वर्टेक्स से जुड़ा ग्राफ होता है लेकिन कोई हैमिल्टनियन चक्र नहीं होता है और क्रिस्पिन नैश-विलियम्स के एक अनुमान को रद्द करता है।[4]

प्रत्येक मध्यवर्ती का ग्राफ एक क्वार्टिक समतल ग्राफ होता है और प्रत्येक क्वार्टिक समतल ग्राफ दोहरे समतल ग्राफ या मल्टीग्राफ के युग्म का माध्य ग्राफ के रूप में है।[5] नॉट आरेखण और लिंक आरेख भी क्वार्टिक समतल मल्टीग्राफ के रूप में होता है, जिसमें शीर्ष आरेखण के प्रतिच्छेद का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में नॉट की दो शाखाएँ उस बिंदु पर दूसरी रेखन को पार करती हैं।[6]

गुण

क्योंकि क्वार्टिक ग्राफ सिद्धांत में प्रत्येक शीर्ष की घात धनात्मक होती है और यह प्रत्येक क्वार्टिक ग्राफ से जुड़ा होता है और यह एक यूलर ग्राफ के रूप में होता है जैसा कि नियमित द्विदलीय रेखांकन के साथ होता है और सामान्यतः प्रत्येक द्विदलीय चतुर्थक ग्राफ और क्वार्टिक ग्राफ में एक परिपूर्ण मेल होता है। इस स्थिति में यूलर ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ कलन विधि के रूप में संभव है यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके अनियमित ग्राफ गुणनखंडन 2-फ़ैक्टर के रूप में मिल जाता है, जो इस स्थिति में समान लंबाई के प्रत्येक चक्र का एक संग्रह के रूप में होता है और ग्राफ के प्रत्येक शीर्ष के ठीक एक चक्र में प्रदर्शित होने के साथ.इन चक्रों में अगली कौन सी धार फिर से चुनी जाती है, जबकि इन चक्रों में फिर से प्रत्येक दूसरे किनारे का चयन करके बिल्कुल ठीक रैखिक समय में में मिलती है और इस विधि का उपयोग करके आप रेखीय समय में चार रंगों वाले ग्राफ के किनारों को भी रंगीन कर सकते हैं।[7]

क्वार्टिक ग्राफ़ में हैमिल्टनियन अपघटन की एक समान संख्या होती है।[8]

विवृत समस्याएं

यह एक अनुमान है कि सभी क्वार्टिक हैमिल्टनियन ग्राफ के आलेख के समान संख्या में हैमिल्टनियन परिपथ होते हैं और यह एक से अधिक हैमिल्टनियन परिपथ के रूप मेंहोते हैं और क्वार्टिक मल्टीग्राफ के लिए इसका जवाब गलत माना जाता है।[9]

यह भी देखें

संदर्भ

  1. Toida, S. (1974), "Construction of quartic graphs", Journal of Combinatorial Theory, Series B, 16: 124–133, doi:10.1016/0095-8956(74)90054-9, MR 0347693.
  2. Chvátal, V. (1970), "The smallest triangle-free 4-chromatic 4-regular graph", Journal of Combinatorial Theory, 9 (1): 93–94, doi:10.1016/S0021-9800(70)80057-6.
  3. Folkman, Jon (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3: 215–232, doi:10.1016/s0021-9800(67)80069-3, MR 0224498.
  4. Meredith, G. H. J. (1973), "Regular n-valent n-connected nonHamiltonian non-n-edge-colorable graphs", Journal of Combinatorial Theory, Series B, 14: 55–60, doi:10.1016/s0095-8956(73)80006-1, MR 0311503.
  5. Bondy, J. A.; Häggkvist, R. (1981), "Edge-disjoint Hamilton cycles in 4-regular planar graphs", Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007/BF02190157, MR 0623315.
  6. Welsh, Dominic J. A. (1993), "The complexity of knots", Quo vadis, graph theory?, Annals of Discrete Mathematics, vol. 55, Amsterdam: North-Holland, pp. 159–171, doi:10.1016/S0167-5060(08)70385-6, MR 1217989.
  7. Gabow, Harold N. (1976), "Using Euler partitions to edge color bipartite multigraphs", International Journal of Computer and Information Sciences, 5 (4): 345–355, doi:10.1007/bf00998632, MR 0422081.
  8. Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Annals of Discrete Mathematics, 3: 259–268, doi:10.1016/s0167-5060(08)70511-9, MR 0499124.
  9. Fleischner, Herbert (1994), "Uniqueness of maximal dominating cycles in 3-regular graphs and of Hamiltonian cycles in 4-regular graphs", Journal of Graph Theory, 18 (5): 449–459, doi:10.1002/jgt.3190180503, MR 1283310.


बाहरी संबंध