सर्किल ग्राफ

For the chart, see Pie chart.

पाँच जीवाओं वाला एक वृत्त और संगत वृत्त ग्राफ़।

ग्राफ सिद्धांत में, एक घेरा ग्राफ एक कॉर्ड आरेख (गणित) का प्रतिच्छेदन ग्राफ है। यही है, यह एक अप्रत्यक्ष ग्राफ है, जिसके कोने एक वृत्त की जीवा (ज्यामिति) की एक परिमित प्रणाली से जुड़े हो सकते हैं जैसे कि दो कोने आसन्न होते हैं यदि और केवल यदि संबंधित तार एक दूसरे को पार करते हैं।

एल्गोरिथम जटिलता

Spinrad (1994) एक O(n²)-समय एल्गोरिद्म जो परीक्षण करता है कि क्या दिया गया n-वर्टेक्स अप्रत्यक्ष ग्राफ़ एक वृत्त ग्राफ़ है और, यदि ऐसा है, तो इसका प्रतिनिधित्व करने वाले जीवाओं का एक सेट बनाता है।

कई अन्य समस्याएं जो सामान्य ग्राफ़ पर एनपी-पूर्ण हैं, सर्कल ग्राफ़ तक सीमित होने पर बहुपद समय एल्गोरिदम हैं। उदाहरण के लिए, Kloks (1996) ने दिखाया कि एक सर्कल ग्राफ की पेड़ की चौड़ाई निर्धारित की जा सकती है, और O(n) में एक इष्टतम पेड़ अपघटन का निर्माण किया गया है³) समय। इसके अतिरिक्त, एक न्यूनतम फिल-इन (अर्थात, संभव के रूप में कुछ किनारों के साथ एक कॉर्डल ग्राफ़ जिसमें दिए गए वृत्त ग्राफ़ को सबग्राफ के रूप में सम्मलित किया गया है) O(n) में पाया जा सकता है³) समय। Tiskin (2010) ने दिखाया है कि O(n log² n) समय, जबकि Nash & Gregg (2010) ने दिखाया है कि एक अनवेटेड सर्कल ग्राफ का अधिकतम स्वतंत्र सेट O(n min{d, α}) समय में पाया जा सकता है, जहां d ग्राफ का एक पैरामीटर है जिसे इसके घनत्व के रूप में जाना जाता है, और α इसकी स्वतंत्रता संख्या है सर्कल ग्राफ।

चूँकि , ऐसी भी समस्याएँ हैं जो वृत्त रेखांकन तक सीमित होने पर NP-पूर्ण रहती हैं। इनमें न्यूनतम हावी सेट, न्यूनतम जुड़ा हुआ हावी सेट और न्यूनतम कुल हावी सेट समस्याएं सम्मलित हैं।

रंगीन संख्या

220-वर्टेक्स 5-क्रोमैटिक त्रिकोण-मुक्त सर्कल ग्राफ बनाने वाले जीवा Ageev (1996), में रेखाओं की व्यवस्था के रूप में तैयार किया गया अतिशयोक्तिपूर्ण स्थान।

एक सर्कल ग्राफ की रंगीन संख्या रंगों की न्यूनतम संख्या होती है जिसका उपयोग इसके तारों को रंगने के लिए किया जा सकता है जिससे कि दो क्रॉसिंग जीवाओं का रंग समान न हो। चूँकि सर्कल ग्राफ़ बनाना संभव है जिसमें मनमाने ढंग से जीवाओं के बड़े सेट सभी एक दूसरे को पार करते हैं, सर्कल ग्राफ़ की रंगीन संख्या मनमाने ढंग से बड़ी हो सकती है, और सर्कल ग्राफ़ की रंगीन संख्या का निर्धारण एनपी-पूर्ण है। यह जांचने के लिए एनपी-पूर्ण रहता है कि क्या एक वृत्त ग्राफ को चार रंगों से रंगा जा सकता है। Unger (1992) ने प्रमाणित किया कि बहुपद समय में तीन रंगों के साथ एक रंग का पता लगाया जा सकता है लेकिन इस परिणाम का उनका लेखन कई विवरणों को छोड़ देता है।

कई लेखकों ने कुछ रंगों के साथ सर्कल ग्राफ़ के प्रतिबंधित उपवर्गों को रंगने की समस्याओं की जांच की है। विशेष रूप से, सर्कल ग्राफ़ के लिए जिसमें k या अधिक जीवाओं का कोई सेट एक दूसरे को पार नहीं करता है, ग्राफ़ को कम से कम रंगना संभव है $7k^{2}$ रंग की। इसे बताने का एक विधि यह है कि सर्कल ग्राफ χ-बाउंडेड | हैं$\chi$-बाध्य। विशेष स्थिति में जब k = 3 (अर्थात, त्रिभुज-मुक्त ग्राफ़|त्रिकोण-मुक्त वृत्त ग्राफ़ के लिए) वर्णिक संख्या अधिक से अधिक पाँच होती है, और यह तंग है: सभी त्रिभुज-मुक्त वृत्त ग्राफ़ पाँच रंगों से रंगे जा सकते हैं, और वहाँ त्रिभुज-मुक्त वृत्त ग्राफ़ उपस्थित हैं जिनके लिए पाँच रंगों की आवश्यकता होती है। यदि किसी वृत्त ग्राफ़ में परिधि (ग्राफ़ सिद्धांत) कम से कम पाँच हैं (अर्थात, यह त्रिभुज-मुक्त है और इसमें चार-शीर्ष चक्र नहीं हैं) तो इसे अधिकतम तीन रंगों से रंगा जा सकता है। त्रिभुज-मुक्त वर्गग्राफ को रंगने की समस्या स्क्वायरग्राफ को पेड़ के ग्राफ (ग्राफ सिद्धांत) के कार्टेशियन उत्पाद के आइसोमेट्रिक सबग्राफ के रूप में प्रस्तुत करने की समस्या के बराबर है; इस पत्राचार में, रंग में रंगों की संख्या उत्पाद प्रतिनिधित्व में पेड़ों की संख्या से मेल खाती है।

अनुप्रयोग

वीएलएसआई भौतिक डिजाइन (इलेक्ट्रॉनिक्स) में वायर रूटिंग के लिए एक विशेष स्थिति के लिए सार प्रतिनिधित्व के रूप में सर्किल ग्राफ उत्पन्न होते हैं, जिसे दो-टर्मिनल स्विचबॉक्स रूटिंग के रूप में जाना जाता है। इस स्थिति में मार्ग क्षेत्र एक आयत है, सभी जाल दो-टर्मिनल हैं, और टर्मिनलों को आयत की परिधि पर रखा गया है। यह आसानी से देखा जा सकता है कि इन जालों का प्रतिच्छेदन ग्राफ एक वृत्तीय ग्राफ है। वायर रूटिंग स्टेप के लक्ष्यों में यह सुनिश्चित करना है कि विभिन्न जाल विद्युत रूप से डिस्कनेक्ट रहें, और उनके संभावित प्रतिच्छेदन भागों को अलग-अलग संवाहक परतों में एकीकृत सर्किट लेआउट होना चाहिए। इसलिए सर्कल ग्राफ़ इस रूटिंग समस्या के विभिन्न पहलुओं को कैप्चर करते हैं।

सर्कल ग्राफ़ के रंग का उपयोग मनमाना ग्राफ़ के पुस्तक एम्बेडिंग को खोजने के लिए भी किया जा सकता है: यदि किसी दिए गए ग्राफ़ जी के कोने एक सर्कल पर व्यवस्थित होते हैं, जी के किनारों के साथ सर्कल के तार बनाते हैं, तो इन जीवाओं का प्रतिच्छेदन ग्राफ एक है सर्कल ग्राफ और इस सर्कल ग्राफ के रंग पुस्तक एम्बेडिंग के समतुल्य हैं जो दिए गए परिपत्र लेआउट का सम्मान करते हैं। इस तुल्यता में, रंग में रंगों की संख्या पुस्तक एम्बेडिंग में पृष्ठों की संख्या से मेल खाती है।

संबंधित ग्राफ वर्ग

पाँच अंतरालों वाला एक अंतराल सिस्टम और संबंधित ओवरलैप ग्राफ़।

एक ग्राफ़ एक सर्कल ग्राफ़ है यदि और केवल यदि यह एक रेखा पर अंतराल के सेट का ओवरलैप ग्राफ़ है। यह एक ग्राफ़ है जिसमें कोने अंतराल के अनुरूप होते हैं, और दो कोने एक किनारे से जुड़े होते हैं यदि दो अंतराल ओवरलैप होते हैं, न तो दूसरे में सम्मलित होते हैं।

एक रेखा पर अंतरालों के एक समूह के प्रतिच्छेदन ग्राफ को अंतराल ग्राफ कहा जाता है।

स्ट्रिंग ग्राफ़, विमान में वक्रों के प्रतिच्छेदन ग्राफ़, एक विशेष स्थिति के रूप में वृत्त ग्राफ़ सम्मलित करते हैं।

हर दूरी-वंशानुगत ग्राफ एक सर्कल ग्राफ है, जैसा कि हर क्रमचय ग्राफ और हर उदासीनता ग्राफ है। हर आउटरप्लानर ग्राफ भी एक सर्कल ग्राफ है। सर्कल ग्राफ़ को बहुभुज-सर्कल ग्राफ़ द्वारा सामान्यीकृत किया जाता है, बहुभुजों के प्रतिच्छेदन ग्राफ़ सभी एक ही वृत्त में अंकित होते हैं।

संदर्भ

• Ageev, A. A. (1996), "A triangle-free circle graph with chromatic number 5", Discrete Mathematics, 152 (1–3): 295–298, doi:10.1016/0012-365X(95)00349-2.
• Ageev, A. A. (1999), "Every circle graph of girth at least 5 is 3-colourable", Discrete Mathematics, 195 (1–3): 229–233, doi:10.1016/S0012-365X(98)00192-7.
• Bandelt, H.-J.; Chepoi, V.; Eppstein, D. (2010), "Combinatorics and geometry of finite and infinite squaregraphs", SIAM Journal on Discrete Mathematics, 24 (4): 1399–1440, arXiv:0905.4537, doi:10.1137/090760301, S2CID 10788524.
• Černý, Jakub (2007), "Coloring circle graphs", Electronic Notes in Discrete Mathematics, 29: 357–361, doi:10.1016/j.endm.2007.07.072.
• Davies, James; McCarty, Rose (2021), "Circle graphs are quadratically χ-bounded", Bulletin of the London Mathematical Society, 53 (3): 673–679, arXiv:1905.11578, doi:10.1112/blms.12447, MR 4275079, S2CID 167217723.
• Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. (1980), "The complexity of coloring circular arcs and chords", SIAM Journal on Algebraic and Discrete Methods, 1 (2): 216–227, doi:10.1137/0601025.
• Gyárfás, A. (1985), "On the chromatic number of multiple interval graphs and overlap graphs", Discrete Mathematics, 55 (2): 161–166, doi:10.1016/0012-365X(85)90044-5. As cited by Ageev (1996).
• Gyárfás, A.; Lehel, J. (1985), "Covering and coloring problems for relatives of intervals", Discrete Mathematics, 55 (2): 167–180, doi:10.1016/0012-365X(85)90045-7. As cited by Ageev (1996).
• Karapetyan, A. (1984), On perfect arc and chord intersection graphs, Ph.D. thesis (in Russian), Inst. of Mathematics, Novosibirsk{{citation}}: CS1 maint: unrecognized language (link). As cited by Ageev (1996).
• Keil, J. Mark (1993), "The complexity of domination problems in circle graphs", Discrete Applied Mathematics, 42 (1): 51–63, doi:10.1016/0166-218X(93)90178-Q.
• Kloks, Ton (1996), "Treewidth of Circle Graphs", Int. J. Found. Comput. Sci., 7 (2): 111–120, doi:10.1142/S0129054196000099.
• Kloks, T.; Kratsch, D.; Wong, C. K. (1998), "Minimum fill-in on circle and circular-arc graphs", Journal of Algorithms, 28 (2): 272–289, doi:10.1006/jagm.1998.0936.
• Kostochka, A.V. (1988), "Upper bounds on the chromatic number of graphs", Trudy Instituta Mathematiki (in Russian), 10: 204–226, MR 0945704{{citation}}: CS1 maint: unrecognized language (link). As cited by Ageev (1996).
• Kostochka, A.V.; Kratochvíl, J. (1997), "Covering and coloring polygon-circle graphs", Discrete Mathematics, 163 (1–3): 299–305, doi:10.1016/S0012-365X(96)00344-5.
• Nash, Nicholas; Gregg, David (2010), "An output sensitive algorithm for computing a maximum independent set of a circle graph", Information Processing Letters, 116 (16): 630–634, doi:10.1016/j.ipl.2010.05.016, hdl:10344/2228.
• Spinrad, Jeremy (1994), "Recognition of circle graphs", Journal of Algorithms, 16 (2): 264–282, doi:10.1006/jagm.1994.1012.
• Tiskin, Alexander (2010), "Fast distance multiplication of unit-Monge matrices.", Proceedings of ACM-SIAM SODA 2010, pp. 1287–1296.
• Unger, Walter (1988), "On the k-colouring of circle-graphs", STACS 88: 5th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 11–13, 1988, Proceedings, Lecture Notes in Computer Science, vol. 294, Berlin: Springer, pp. 61–72, doi:10.1007/BFb0035832.
• Unger, Walter (1992), "The complexity of colouring circle graphs", STACS 92: 9th Annual Symposium on Theoretical Aspects of Computer Science, Cachan, France, February 13–15, 1992, Proceedings, Lecture Notes in Computer Science, vol. 577, Berlin: Springer, pp. 389–400, doi:10.1007/3-540-55210-3_199.
• Wessel, W.; Pöschel, R. (1985), "On circle graphs", in Sachs, Horst (ed.), Graphs, Hypergraphs and Applications: Proceedings of the Conference on Graph Theory Held in Eyba, October 1st to 5th, 1984, Teubner-Texte zur Mathematik, vol. 73, B.G. Teubner, pp. 207–210. As cited by Unger (1988).