सर्किल ग्राफ

File:Circle graph and circle model.svg

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

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

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

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

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

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

क्रोमैटिक संख्या

Error creating thumbnail:

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

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

कई लेखकों ने कुछ रंगों के साथ वृत्त ग्राफ़ के प्रतिबंधित उपवर्गों को रंगने की समस्याओं की जांच की है। विशेष रूप से, वृत्त ग्राफ़ के लिए जिसमें k या अधिक जीवाओं का कोई समूह एक दूसरे को पार नहीं करता है, किसी भी ग्राफ को $7k^{2}$ से अधिक रंग देना संभव होता है। यह बताने की एक विधि यह है कि वृत्त ग्राफ χ-बाउंडेड रूप में होते है। विशेष स्थिति में जब 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).