त्रिकोण मुक्त ग्राफ

ग्राफ सिद्धांत के गणित क्षेत्र में त्रिकोण मुक्त ग्राफ ऐसा अप्रत्यक्ष ग्राफ है जिसमें तीन कोने से घिरे किनारों के त्रिभुज ग्राफ नहीं बना पाते हैं। त्रिभुज मुक्त ग्राफ को क्लिक के साथ ग्राफ (ग्राफ सिद्धांत) ≤ 2, परिधि के साथ ग्राफ (ग्राफ सिद्धांत) ≥ 4 तथा इसके अतिरिक्त प्रेरित पथ वाले ग्राफ या प्रेरित 3-चक्र या समीपस्थ (ग्राफ सिद्धांत) ग्राफ के रूप में समान रूप से परिभाषित किया जाता हैं।

त्रिभुज-मुक्त ग्राफ उनके शीर्षों के लिए सबसे अधिक किनारों के साथ संतुलित पूर्ण द्विदलीय ग्राफ हैं। कई त्रिभुज-मुक्त ग्राफ द्विदलीय नहीं होते हैं, उदाहरण के लिए कोई चक्र ग्राफ C_n विषम n> 3 के लिए किया जाता हैं।

टुरान की प्रमेय के अनुसार किनारों की अधिकतम संख्याओं के साथ एन-अक्ष वाले त्रिकोण-मुक्त ग्राफ पूर्णतयः द्विदलीय ग्राफ को प्रकट करते हैं जिसमें द्विदलीय ग्राफ के प्रत्येक कोने की संख्या यथासंभव बराबर रहती है।

त्रिभुज ढूँढने की समस्या

त्रिभुज ढूँढने की समस्या यह निर्धारित करने की समस्या को प्रदर्शित करती है कि ग्राफ त्रिभुज-मुक्त है या नहीं हैं। जब ग्राफ में त्रिभुज होता है, तो एल्गोरिदम को अधिकांशतः तीन शीर्षों से आउटपुट प्राप्त करने की आवश्यकता होती है जो ग्राफ में त्रिभुज का निर्माण करते हैं।

यह परीक्षण करना संभव है कि क्या ग्राफ के साथ m किनारे पर O(m^1.41) समय में त्रिभुज-मुक्त हैं। इसके अतिरिक्त अन्य दृष्टिकोणों का ट्रेस (रैखिक बीजगणित) A³ ढूँढने के लिए है, जहाँ A ग्राफ का आसन्न आव्यूह है। इस प्रकार यहाँ पर ट्रेस का मान शून्य रहता है, इस प्रकार यदि ग्राफ त्रिभुज मुक्त है। इस प्रकार घने रेखांकन के लिए, इस सरल एल्गोरिथ्म का उपयोग करना अधिक कुशल है जो आव्यूह के गुणन पर निर्भर करता है, क्योंकि इससे समय O(n^2.373) की जटिलता कम हो जाती है, जहाँ n शीर्षों की संख्या है।

जैसा इमरिच, क्लाज़र & मुल्डर (1999) द्वारा दिखाया गया है, इस प्रकार त्रिभुज-मुक्त ग्राफ की पहचान माध्यिका के ग्राफ की पहचान की जटिलता के बराबर है, चूंकि औसत ग्राफ पहचान के लिए वर्तमान सर्वोत्तम एल्गोरिदम त्रिभुज पहचान का उपयोग इसके विपरीत के अतिरिक्त उपनेमका के रूप में करते हैं।

इन निर्णयों के आधार पर पेड़ की जटिलता या समस्या की क्वेरी जटिलता के लिए की जाती हैं, जहाँ यह प्रश्न ऑरैकल के लिए हैं जो ग्राफ के आसन्न आव्यूह Θ(n²) को संग्रहित करता है, चूंकि क्वांटम एल्गोरिथ्म के लिए, सबसे अच्छी ज्ञात निचली सीमा Ω(n) है, किन्तु सबसे अच्छी ज्ञात एल्गोरिथम O(n^5/4) है।

स्वतंत्रता संख्या और रैमसे सिद्धांत

n-शीर्ष वाले त्रिभुज-मुक्त ग्राफ में √n शीर्षों का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) द्वारा ढूंढना सरल है: इसका कारण या तो √n समीपस्थ होने से अधिक के साथ शीर्ष के कारण है (जिस स्थिति में वे समीपस्थ स्वतंत्र समुच्चय हैं) या सभी कोने √n समीपस्थ मान से कम है (जिस स्थिति में किसी भी अधिकतम स्वतंत्र समुच्चय में कम से कम √n कोने होने चाहिए)। इस बाउंड को थोड़ा कठोर किया जाता है: प्रत्येक त्रिभुज-मुक्त ग्राफ में स्वतंत्र समुच्चय सम्मिलित होता है। इस कारण $\Omega ({\sqrt {n\log n}})$ कोने, और कुछ त्रिभुज-मुक्त ग्राफ में प्रत्येक स्वतंत्र समुच्चय $O({\sqrt {n\log n}})$ इसके शीर्ष में होता है। इस प्रकार त्रिभुज-मुक्त ग्राफ उत्पन्न करने की विधि जिसमें सभी स्वतंत्र समुच्चय कम होते हैं, इस प्रकार यह त्रिभुज-मुक्त प्रक्रिया कहलाती हैं जिसमें बार-बार विचित्र ढंग से चुने गए किनारों को जोड़कर अधिकतम त्रिभुज-मुक्त ग्राफ उत्पन्न होते हैं जो त्रिभुज को पूरा नहीं करता है। इसकी उच्च संभावनाओं के साथ यह प्रक्रिया स्वतंत्रता संख्या के साथ $O({\sqrt {n\log n}})$ ग्राफ बनाती है। जिसके समान गुणों वाले नियमित ग्राफको ढूंढना भी संभव है।

इन परिणामों की व्याख्या फॉर्म के रैमसे संख्या R(3,t) पर स्पर्शोन्मुख सीमा $\Theta ({\tfrac {t^{2}}{\log t}})$ देने के रूप में भी की जा सकती है: यदि पूर्ण ग्राफ के किनारों पर $\Omega ({\tfrac {t^{2}}{\log t}})$ कोने लाल और नीले रंग के होते हैं, तो या तो लाल ग्राफ में त्रिभुज होता है, इस प्रकार यदि यह त्रिभुज-मुक्त होता है, तो इसमें नीले ग्राफ में समान आकार के समूह के अनुरूप आकार t का स्वतंत्र समुच्चय होने चाहिए।

रंग त्रिकोण मुक्त रेखांकन

Grötzsch ग्राफ त्रिभुज-मुक्त ग्राफ है जिसे चार से कम रंगों से रंगा नहीं जा सकता है

त्रिकोण-मुक्त ग्राफ के बारे में अधिक शोध ने ग्राफ रंग पर ध्यान केंद्रित किया जाता है। प्रत्येक द्विदलीय ग्राफ (अर्थात्, प्रत्येक 2-रंगीय ग्राफ) त्रिभुज-मुक्त है, और ग्रॉट्ज़स्च के प्रमेय में कहा गया है कि प्रत्येक त्रिभुज-मुक्त समतलीय ग्राफ 3-रंग के होते हैं। चूंकि, गैर-प्लानर त्रिभुज-मुक्त ग्राफ को तीन से अधिक रंगों की आवश्यकता हो सकती है।

इस प्रकार इन तरीकों से उच्च रंगीन संख्याओं के साथ त्रिभुज मुक्त ग्राफ का पहला निर्माण सभी (ब्लैंच डेसकार्टेस के रूप में लेखन) के कारण किया जाता है)। यह निर्माण ग्राफ से एकल शीर्ष मान $G_{1}$ के साथ प्रारंभ होता हैं और आगमनात्मक रूप से $G_{k+1}$ से $G_{k}$ द्वारा निर्मित होता हैं। जो इस प्रकार है: यहाँ पर $G_{k}$ के समीप $n$ शीर्ष के कारण पुनः समुच्चय $Y$ का मान $k(n-1)+1$ शीर्ष और प्रत्येक उपसमुच्चय के लिए $X$ का $Y$ आकार का $n$ की असंबद्ध $G_{k}$ की प्रति जोड़ते हैं और इसमें सम्मिलित $X$ के संयोजन के साथ उपयोग किए जाते हैं। इस प्रकार पीजन के सिद्धांत से यह आगमनात्मक रूप से अनुसरण करता है कि $G_{k+1}$ क्या नहीं है। इस प्रकार $k$ रंगीन होने पर कम से कम समुच्चय के पश्चात $X$ यदि हमें केवल k रंगों का उपयोग करने की अनुमति देता हैं, तो उन्हें मोनोक्रोमैटिक रूप से रंगा जाना चाहिए। इस प्रकार माइसिल्सकी (1955) ने अन्य त्रिभुज-मुक्त ग्राफ से नया त्रिभुज-मुक्त ग्राफ बनाने के लिए संरचना को परिभाषित किया, जिसे अब माइसिल्सकियन कहा जाता है। यदि इस प्रकार किसी ग्राफ में वर्णक्रमीय संख्या k है, तो इसके माइसिल्सकियन में वर्णक्रमीय संख्या k + 1 है, इसलिए इस निर्माण का उपयोग यह दिखाने के लिए किया जा सकता है कि गैर-प्लानर त्रिभुज-मुक्त ग्राफ को रंगने के लिए स्वयं की विधियों से बड़ी संख्या में रंगों की आवश्यकता हो सकती है। इस प्रकार विशेष रूपों के कारण ग्रॉट्ज़स्च ग्राफ, 11-वर्टेक्स ग्राफ, जो मैसिएल्स्की के निर्माण के दोहराए गए आवेदन से बनता है, ये त्रिभुज-मुक्त ग्राफ द्वारा प्रदर्शित होते है जिसे चार से कम रंगों से रंगा नहीं जा सकता है, और इससे प्राप्त मानों के साथ सबसे छोटा ग्राफ तैयार होता है। जिम्बेल & थाॅमेस्सन (2000) और निल्ली (2000) ने दिखाया कि किसी भी एम-एज त्रिकोण मुक्त ग्राफ को रंगने के लिए आवश्यक रंगों की संख्या है।

$O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)$

इस समीकरण के अनुसार त्रिभुज-मुक्त ग्राफ इसमें सम्मिलित रहता हैं जिनकी रंगीन संख्याएँ इस सीमा के समानुपाती होती हैं।

त्रिभुज-मुक्त ग्राफ में रंग को न्यूनतम डिग्री से संबंधित कई परिणाम भी मिलते हैं। एंड्रास्फाई, एरडाॅस & साॅस (1974) ने सिद्ध किया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ जिसमें प्रत्येक शीर्ष पर 2n/5 से अधिक समीप रहते हैं, इस प्रकार उक्त मान द्विदलीय होने चाहिए। यह इस प्रकार का सबसे अच्छा संभव परिणाम है, क्योंकि इस प्रकार 5-चक्र में तीन रंगों की आवश्यकता होती है, किन्तु प्रति शीर्ष 2n/5 पड़ोसी होते हैं। इस परिणाम से प्रेरित होकर, इरदौस & सिमिनोविट्स (1973) ने अनुमान लगाया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ जिसमें प्रत्येक शीर्ष के कम से कम n/3 के समीप होते हैं, इसे केवल तीन रंगों से रंगा जा सकता है, चूंकि, हैग्कविस्ट (1981) ने इस अनुमान को काउंटर करते हुए उदाहरण दिया हैं कि उक्त मान को ढूंढकर निरस्त कर दिया जाता हैं जिसमें ग्रोट्ज़स्च ग्राफ के प्रत्येक शीर्ष को सावधानी से चुने गए आकार के स्वतंत्र समुच्चय द्वारा प्रतिस्थापित किया गया है। जिन (1995) ने दिखाया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ जिसमें प्रत्येक शीर्ष में 10n/29 समीपस्थ से अधिक मान को प्रदर्शित करते है, इस प्रकार ये मुख्यतः 3-रंगों में प्रदर्शित होने चाहिए, यह इस प्रकार का सर्वोत्तम संभव परिणाम है, क्योंकि हैग्कविस्ट के ग्राफ में चार रंगों की आवश्यकता होती है और इस प्रकार प्रति शीर्ष ठीक 10n/29 के समीप होते हैं। इस प्रकार ब्रैन्डिट & थामेस्से (2006) ने सिद्ध किया कि कोई भी n-शीर्ष त्रिभुज-मुक्त ग्राफ जिसमें प्रत्येक शीर्ष के n/3 समीपस्थ से अधिक है, वह 4-रंगीय होना चाहिए। इस प्रकार हजनल के रूप में इस प्रकार के अतिरिक्त परिणाम संभव नहीं हैं। इस कारण किसी भी ε> 0 के लिए स्वयं की विधि से बड़ी रंगीन संख्या और न्यूनतम डिग्री (1/3 − ε)n के साथ त्रिभुज-मुक्त ग्राफ के उदाहरण मिलते हैं।

यह भी देखें

• आंद्रसफाई ग्राफ, दो व्यास वाले त्रिभुज-मुक्त सर्कुलेंट ग्राफ का समूह हैं।
• हेंसन ग्राफ, अनंत त्रिभुज-मुक्त ग्राफ जिसमें प्रेरित सबग्राफ के रूप में सभी परिमित त्रिभुज-मुक्त ग्राफ सम्मिलित हैं।
• शिफ्ट ग्राफ, मनमाने ढंग से उच्च रंगीन संख्या के साथ त्रिकोण-मुक्त ग्राफ का समूह हैं।
• केसर ग्राफ $KG_{3k-1,k}$ त्रिभुज मुक्त है और इसमें रंगीन संख्या $k+1$ हैं।
• मोनोक्रोमैटिक त्रिभुज समस्या, किसी दिए गए ग्राफ के किनारों को दो त्रिभुज-मुक्त ग्राफ में विभाजित करने की समस्या से प्राप्त होता हैं।
• रुज़सा-ज़ेमेरीडी समस्या, ग्राफ पर जिसमें हर किनारा ठीक त्रिकोण से संबंधित है।

संदर्भ

Notes

Sources

• Alon, Noga; Ben-Shimon, Sonny; Krivelevich, Michael (2010), "A note on regular Ramsey graphs", Journal of Graph Theory, 64 (3): 244–249, arXiv:0812.2386, doi:10.1002/jgt.20453, MR 2674496, S2CID 1784886.
• Alon, N.; Yuster, R.; Zwick, U. (1994), "Finding and counting given length cycles", Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364.
• Andrásfai, B.; Erdős, P.; Sós, V. T. (1974), "On the connection between chromatic number, maximal clique and minimal degree of a graph" (PDF), Discrete Mathematics, 8 (3): 205–218, doi:10.1016/0012-365X(74)90133-2.
• Belovs, Aleksandrs (2012), "Span programs for functions with constant-sized 1-certificates", Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC '12), New York, NY, USA: ACM, pp. 77–84, arXiv:1105.4024, doi:10.1145/2213977.2213985, ISBN 978-1-4503-1245-5, S2CID 18771464.
• Bohman, Tom (2009), "The triangle-free process", Advances in Mathematics, 221 (5): 1653–1677, arXiv:0806.4375, doi:10.1016/j.aim.2009.02.018, MR 2522430, S2CID 17701040.
• Boppana, Ravi; Halldórsson, Magnús M. (1992), "Approximating maximum independent sets by excluding subgraphs", BIT, 32 (2): 180–196, doi:10.1007/BF01994876, MR 1172185, S2CID 123335474.
• Brandt, S.; Thomassé, S. (2006), Dense triangle-free graphs are four-colorable: a solution to the Erdős–Simonovits problem (PDF).
• Chiba, N.; Nishizeki, T. (1985), "Arboricity and subgraph listing algorithms", SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017, S2CID 207051803.
• Descartes, Blanche (April 1947), "A three colour problem", Eureka, 21.
• Descartes, Blanche (1954), "Solution to Advanced Problem no. 4526", Amer. Math. Monthly, 61: 352.
• Chvátal, Vašek (1974), "The minimality of the Mycielski graph", Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Lecture Notes in Mathematics, vol. 406, Springer-Verlag, pp. 243–246.
• Erdős, P.; Simonovits, M. (1973), "On a valence problem in extremal graph theory", Discrete Mathematics, 5 (4): 323–334, doi:10.1016/0012-365X(73)90126-X.
• Erdős, P.; Suen, S.; Winkler, P. (1995), "On the size of a random maximal graph", Random Structures and Algorithms, 6 (2–3): 309–318, doi:10.1002/rsa.3240060217.
• Gimbel, John; Thomassen, Carsten (2000), "Coloring triangle-free graphs with fixed size", Discrete Mathematics, 219 (1–3): 275–277, doi:10.1016/S0012-365X(00)00087-X.
• Grötzsch, H. (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, 8: 109–120.
• Häggkvist, R. (1981), "Odd cycles of specified length in nonbipartite graphs", Graph Theory (Cambridge, 1981), vol. 62, pp. 89–99, doi:10.1016/S0304-0208(08)73552-7.
• Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Median graphs and triangle-free graphs", SIAM Journal on Discrete Mathematics, 12 (1): 111–118, doi:10.1137/S0895480197323494, MR 1666073, S2CID 14364050.
• Itai, A.; Rodeh, M. (1978), "Finding a minimum circuit in a graph", SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033.
• Jin, G. (1995), "Triangle-free four-chromatic graphs", Discrete Mathematics, 145 (1–3): 151–170, doi:10.1016/0012-365X(94)00063-O.
• Kim, J. H. (1995), "The Ramsey number $R(3,t)$ has order of magnitude ${\tfrac {t^{2}}{\log t}}$", Random Structures and Algorithms, 7 (3): 173–207, doi:10.1002/rsa.3240070302, S2CID 16658980.
• Le Gall, François (October 2014), "Improved quantum algorithm for triangle finding via combinatorial arguments", Proceedings of the 55th Annual Symposium on Foundations of Computer Science (FOCS 2014), IEEE, pp. 216–225, arXiv:1407.0085, doi:10.1109/focs.2014.31, ISBN 978-1-4799-6517-5, S2CID 5760574.
• Lee, Troy; Magniez, Frédéric; Santha, Miklos (2013), "Improved quantum query algorithms for triangle finding and associativity testing", Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), New Orleans, Louisiana, pp. 1486–1502, ISBN 978-1-611972-51-1{{citation}}: CS1 maint: location missing publisher (link).
• Mycielski, J. (1955), "Sur le coloriage des graphes", Colloq. Math., 3 (2): 161–162, doi:10.4064/cm-3-2-161-162.
• Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics, 211 (1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.
• Shearer, J. B. (1983), "Note on the independence number of triangle-free graphs", Discrete Mathematics, 46 (1): 83–87, doi:10.1016/0012-365X(83)90273-X.
• Thomassen, C. (1994), "Grötzsch's 3-color theorem", Journal of Combinatorial Theory, Series B, 62 (2): 268–279, doi:10.1006/jctb.1994.1069.

बाहरी संबंध

• "Graphclass: triangle-free", Information System on Graph Classes and their Inclusions