क्वार्टिक ग्राफ
ग्राफ सिद्धांत के गणित क्षेत्र में, एक क्वार्टिक ग्राफ एक ग्राफ (असतत गणित) है जहां सभी वर्टेक्स (ग्राफ सिद्धांत) में डिग्री (ग्राफ सिद्धांत) 4 है। दूसरे शब्दों में, क्वार्टिक ग्राफ एक 4-नियमित ग्राफ है।[1]
उदाहरण
कई प्रसिद्ध ग्राफ क्वार्टिक हैं। वे सम्मिलित करते हैं:
- पूरा ग्राफ के5, 5 शीर्षों वाला एक चतुर्थांश ग्राफ, सबसे छोटा संभव चतुर्थक ग्राफ।
- च्वाटल ग्राफ, 12 शीर्षों वाला एक अन्य क्वार्टिक ग्राफ, सबसे छोटा क्वार्टिक ग्राफ जिसमें दोनों में कोई त्रिभुज नहीं है और तीन रंगों से रंगने वाला ग्राफ नहीं हो सकता।[2]
- फोकमैन ग्राफ , 20 शीर्षों वाला एक क्वार्टिक ग्राफ, सबसे छोटा अर्ध-सममितीय ग्राफ।[3]
- मेरेडिथ ग्राफ, 70 शीर्षों वाला एक क्वार्टिक ग्राफ जो के-वर्टेक्स-कनेक्टेड ग्राफ|4-कनेक्टेड है लेकिन कोई हैमिल्टनियन पथ नहीं है, क्रिस्पिन नैश-विलियम्स के एक अनुमान को खारिज करता है।[4]
हर औसत अंकित े का ग्राफ एक क्वार्टिक प्लेनर ग्राफ है, और हर क्वार्टिक प्लेन ग्राफ दोहरे प्लेन ग्राफ या मल्टीग्राफ की एक जोड़ी का औसत अंकित े का ग्राफ है।[5] गाँठ आरेख और लिंक डायग्राम भी क्वार्टिक प्लेन मल्टीग्राफ हैं, जिसमें कोने आरेख के क्रॉसिंग का प्रतिनिधित्व करते हैं और अतिरिक्त जानकारी के साथ चिह्नित होते हैं, जिसके बारे में गाँठ की दो शाखाएँ उस बिंदु पर दूसरी शाखा को पार करती हैं।[6]
गुण
क्योंकि क्वार्टिक ग्राफ में प्रत्येक शीर्ष की डिग्री (ग्राफ सिद्धांत) सम है, प्रत्येक जुड़ा हुआ ग्राफ क्वार्टिक ग्राफ में एक यूलर टॉवर होता है। और जैसा कि सामान्यतः नियमित द्विदलीय रेखांकन के साथ होता है, प्रत्येक द्विदलीय ग्राफ क्वार्टिक ग्राफ में एक परिपूर्ण मिलान होता है। इस स्थिति में, अनियमित ग्राफ़ की तुलना में इस तरह के मिलान को खोजने के लिए एक बहुत सरल और तेज़ कलन विधि संभव है: यूलर टूर के हर दूसरे किनारे का चयन करके, एक ग्राफ गुणनखंडन|2-फ़ैक्टर मिल सकता है, जो इस स्थिति में एक होना चाहिए चक्रों का संग्रह, प्रत्येक समान लंबाई का, ग्राफ के प्रत्येक शीर्ष के साथ बिल्कुल एक चक्र में दिखाई देता है। इन चक्रों में फिर से हर दूसरे किनारे का चयन करके, रैखिक समय में एक पूर्ण मिलान प्राप्त होता है। रैखिक समय में चार रंगों के साथ रंग भरने के लिए भी इसी विधि का उपयोग किया जा सकता है।[7] क्वार्टिक ग्राफ़ में हैमिल्टनियन अपघटन की एक समान संख्या होती है।[8]
खुली समस्याएं
यह एक खुला अनुमान है कि क्या सभी क्वार्टिक हैमिल्टनियन ग्राफ में हैमिल्टनियन सर्किट की संख्या भी है, या एक से अधिक हैमिल्टनियन सर्किट हैं। उत्तर क्वार्टिक मल्टीग्राफ के लिए गलत माना जाता है।[9]
यह भी देखें
संदर्भ
- ↑ 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.
