सर्किल ग्राफ

For the chart, see Pie chart.

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

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

कलन विधि जटिलता

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

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

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

रंगीन संख्या

File:Ageev 5X circle graph.svg

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).