क्वार्टिक ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
गणितीय क्षेत्र में [[ग्राफ सिद्धांत]] एक क्वार्टिक [[ग्राफ (असतत गणित)]] के रूप में होता है, जहां सभी वर्टेक्स | गणितीय क्षेत्र में [[ग्राफ सिद्धांत]] एक क्वार्टिक [[ग्राफ (असतत गणित)]] के रूप में होता है, जहां सभी वर्टेक्स के ग्राफ सिद्धांत में [[डिग्री (ग्राफ सिद्धांत)|घात]] 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-[[नियमित ग्राफ]] सिद्धांत के रूप में है।<ref>{{citation | ||
| last = Toida | first = S. | | last = Toida | first = S. | ||
| journal = [[Journal of Combinatorial Theory]] | | journal = [[Journal of Combinatorial Theory]] | ||
| Line 10: | Line 10: | ||
| doi=10.1016/0095-8956(74)90054-9| doi-access = free | | doi=10.1016/0095-8956(74)90054-9| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
== उदाहरण == | == उदाहरण == | ||
[[File:Chvatal Lombardi.svg|thumb|द ग्रैब ग्राफ]]कई प्रसिद्ध ग्राफ क्वार्टिक | [[File:Chvatal Lombardi.svg|thumb|द ग्रैब ग्राफ]]कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में होते है और इस प्रकार वे सम्मिलित होते है | ||
*[[पूरा ग्राफ]] | *[[पूरा ग्राफ]] K<sub>5</sub>, 5 शीर्षों वाला एक चतुर्थांश ग्राफ के रूप में होता है और जो सबसे छोटा चतुर्थक ग्राफ होता है। | ||
* च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ | * च्वाटल ग्राफ, 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 25: | Line 24: | ||
| year = 1970| doi-access = free | | year = 1970| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
*[[ फोकमैन ग्राफ ]], 20 शीर्षों वाला एक क्वार्टिक ग्राफ, सबसे छोटा अर्ध-सममितीय | *[[ फोकमैन ग्राफ | फॉल्कमैन ग्राफ]], 20 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो सबसे छोटा अर्ध-सममितीय ग्राफ होता है।<ref>{{citation | ||
| last = Folkman | first = Jon | | last = Folkman | first = Jon | ||
| journal = [[Journal of Combinatorial Theory]] | | journal = [[Journal of Combinatorial Theory]] | ||
| Line 35: | Line 34: | ||
| doi=10.1016/s0021-9800(67)80069-3| doi-access = free | | doi=10.1016/s0021-9800(67)80069-3| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
*[[मेरेडिथ ग्राफ]], 70 शीर्षों वाला एक क्वार्टिक ग्राफ जो [[के-वर्टेक्स-कनेक्टेड ग्राफ]] | *[[मेरेडिथ ग्राफ]], 70 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो [[के-वर्टेक्स-कनेक्टेड ग्राफ|4 वर्टेक्स से जुड़ा ग्राफ]] होता है लेकिन कोई [[हैमिल्टनियन पथ|हैमिल्टनियन चक्र]] नहीं होता है और [[क्रिस्पिन नैश-विलियम्स]] के एक अनुमान को रद्द करता है।<ref>{{citation | ||
| last = Meredith | first = G. H. J. | | last = Meredith | first = G. H. J. | ||
| journal = [[Journal of Combinatorial Theory]] | | journal = [[Journal of Combinatorial Theory]] | ||
| Line 46: | 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 | |||
| last1 = Bondy | first1 = J. A. | | last1 = Bondy | first1 = J. A. | ||
| last2 = Häggkvist | first2 = R. | | last2 = Häggkvist | first2 = R. | ||
| Line 56: | 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> [[गाँठ आरेख]] और लिंक | | 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 67: | ||
| volume = 55 | | volume = 55 | ||
| year = 1993}}.</ref> | | year = 1993}}.</ref> | ||
== गुण == | == गुण == | ||
क्योंकि क्वार्टिक ग्राफ में प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) सम है, प्रत्येक [[ जुड़ा हुआ ग्राफ ]] क्वार्टिक ग्राफ में एक [[ यूलर टॉवर ]] होता है। | क्योंकि क्वार्टिक ग्राफ में प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) सम है, प्रत्येक [[ जुड़ा हुआ ग्राफ ]] क्वार्टिक ग्राफ में एक [[ यूलर टॉवर ]] होता है। | ||
और जैसा कि सामान्यतः नियमित द्विदलीय रेखांकन के साथ होता है, प्रत्येक द्विदलीय ग्राफ क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति में, अनियमित ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ [[कलन विधि]] संभव है: यूलर टूर के | और जैसा कि सामान्यतः नियमित द्विदलीय रेखांकन के साथ होता है, प्रत्येक द्विदलीय ग्राफ क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति में, अनियमित ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ [[कलन विधि]] संभव है: यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके, एक [[ग्राफ गुणनखंडन]]|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 | ||
Revision as of 10:19, 23 April 2023
गणितीय क्षेत्र में ग्राफ सिद्धांत एक क्वार्टिक ग्राफ (असतत गणित) के रूप में होता है, जहां सभी वर्टेक्स के ग्राफ सिद्धांत में घात 4 होती है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-नियमित ग्राफ सिद्धांत के रूप में है।[1]
उदाहरण
कई प्रसिद्ध ग्राफ क्वार्टिक के रूप में होते है और इस प्रकार वे सम्मिलित होते है
- पूरा ग्राफ K5, 5 शीर्षों वाला एक चतुर्थांश ग्राफ के रूप में होता है और जो सबसे छोटा चतुर्थक ग्राफ होता है।
- च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ के रूप में होता है जो सबसे छोटा क्वार्टिक ग्राफ होता है और जिसमें कोई त्रिभुज नहीं होता है और ये तीन रंगों से रंगने वाला ग्राफ नहीं हो सकता।[2]
- फॉल्कमैन ग्राफ, 20 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो सबसे छोटा अर्ध-सममितीय ग्राफ होता है।[3]
- मेरेडिथ ग्राफ, 70 शीर्षों वाला एक क्वार्टिक ग्राफ के रूप में होता है, जो 4 वर्टेक्स से जुड़ा ग्राफ होता है लेकिन कोई हैमिल्टनियन चक्र नहीं होता है और क्रिस्पिन नैश-विलियम्स के एक अनुमान को रद्द करता है।[4]
प्रत्येक मध्यवर्ती का ग्राफ एक क्वार्टिक प्लेनर ग्राफ के रूप में होता है और प्रत्येक क्वार्टिक समतल ग्राफ दोहरे प्लेन ग्राफ या मल्टीग्राफ की एक जोड़ी का औसत अंकित ग्राफ होता है।[5] नॉट आरेखण और लिंक आरेख भी क्वार्टिक प्लेन मल्टीग्राफ के रूप में होता है, जिसमें शीर्ष आरेखण के प्रतिच्छेद का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में नॉट की दो शाखाएँ उस बिंदु पर दूसरी रेखन को पार करती हैं।[6]
गुण
क्योंकि क्वार्टिक ग्राफ में प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) सम है, प्रत्येक जुड़ा हुआ ग्राफ क्वार्टिक ग्राफ में एक यूलर टॉवर होता है। और जैसा कि सामान्यतः नियमित द्विदलीय रेखांकन के साथ होता है, प्रत्येक द्विदलीय ग्राफ क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति में, अनियमित ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ कलन विधि संभव है: यूलर टूर के प्रत्येक दूसरे किनारे का चयन करके, एक ग्राफ गुणनखंडन|2-फ़ैक्टर मिल सकता है, जो इस स्थिति में एक होना चाहिए चक्रों का संग्रह, प्रत्येक समान लंबाई का, ग्राफ के प्रत्येक शीर्ष के साथ बिल्कुल एक चक्र में दिखाई देता है। इन चक्रों में फिर से प्रत्येक दूसरे किनारे का चयन करके, रैखिक समय में एक पूर्ण मिलान प्राप्त होता है। रैखिक समय में चार रंगों के साथ रंग भरने के लिए भी इसी विधि का उपयोग किया जा सकता है।[7] क्वार्टिक ग्राफ़ में हैमिल्टनियन अपघटन की एक समान संख्या होती है।[8]
खुली समस्याएं
यह एक खुला अनुमान है कि क्या सभी क्वार्टिक हैमिल्टनियन ग्राफ में हैमिल्टनियन सर्किट की संख्या भी है, या एक से अधिक हैमिल्टनियन सर्किट हैं। उत्तर क्वार्टिक मल्टीग्राफ के लिए गलत माना जाता है।[9]
यह भी देखें
Wikimedia Commons has media related to 4-regular graphs.
संदर्भ
- ↑ 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.
- ↑ 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.
- ↑ Folkman, Jon (1967), "Regular line-symmetric graphs", Journal of Combinatorial Theory, 3: 215–232, doi:10.1016/s0021-9800(67)80069-3, MR 0224498.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
