Circle graph
ग्राफ सिद्धांत में, एक वृत्त ग्राफ एक तार आरेख का प्रतिच्छेदन ग्राफ है। अर्थात्, यह एक दिशाहीन ग्राफ है जिसके शीर्षों को एक वृत्त की तारों की एक सीमित प्रणाली के साथ इस तरह से जोड़ा जा सकता है कि दो शीर्ष आसन्न हों यदि और केवल तभी जब संबंधित तार एक दूसरे को पार करते हैं। एल्गोरिदमिक जटिलता एक ओ (एन2)-समय एल्गोरिदम देती है जो यह परीक्षण करती है कि क्या दिया गया एन-वर्टेक्स अनिर्दिष्ट ग्राफ एक वृत्त ग्राफ है और, यदि ऐसा है, तो इसका प्रतिनिधित्व करने वाले कॉर्ड के एक समूह का निर्माण करता है। सामान्य ग्राफ पर एन. पी.-पूर्ण कई अन्य समस्याओं में वृत्त ग्राफ तक सीमित होने पर बहुपद समय एल्गोरिदम होते हैं। उदाहरण के लिए, दिखाया कि एक वृत्त ग्राफ की त्रि-चौड़ाई निर्धारित की जा सकती है, और ओ (एन3) समय में एक इष्टतम वृक्ष अपघटन का निर्माण किया जा सकता है। इसके अतिरिक्त, ओ (एन3) समय में एक न्यूनतम भराव (यानी, जितना संभव हो उतना कम किनारों वाला एक कॉर्डल ग्राफ जिसमें एक उपग्राफ के रूप में दिया गया वृत्त ग्राफ होता है) पाया जा सकता है। इसने दिखाया है कि एक वृत्त ग्राफ का अधिकतम समूह ओ (एन लॉग2एन) समय में पाया जा सकता है, जबकि दिखाया है कि एक भारित वृत्त ग्राफ का अधिकतम स्वतंत्र सेट ओ (एन मिनट {डी, α}) समय में पाया जा सकता है, जहां डी ग्राफ का एक पैरामीटर है जिसे इसके घनत्व के रूप में जाना जाता है, और α वृत्त ग्राफ की स्वतंत्रता संख्या है। हालांकि, ऐसी समस्याएं भी हैं जो सर्कल ग्राफ तक सीमित रहने पर एनपी-पूर्ण बनी रहती हैं। इनमें न्यूनतम हावी सेट, न्यूनतम जुड़ा हुआ हावी सेट और न्यूनतम कुल हावी सेट समस्याएं शामिल हैं। वर्णात्मक संख्या एक वृत्त ग्राफ की वर्णात्मक संख्या रंगों की न्यूनतम संख्या है जिसका उपयोग इसके तारों को रंगने के लिए किया जा सकता है ताकि किसी भी दो पार करने वाले तारों का रंग समान न हो। चूँकि वृत्त ग्राफ बनाना संभव है जिसमें मनमाने ढंग से तारों के बड़े सेट एक दूसरे को पार करते हैं, एक वृत्त ग्राफ की वर्णात्मक संख्या मनमाने ढंग से बड़ी हो सकती है, और एक वृत्त ग्राफ की वर्णात्मक संख्या का निर्धारण एन. पी.-पूर्ण होता है। यह परीक्षण करने के लिए एन. पी.-पूर्ण रहता है कि क्या एक वृत्त ग्राफ को चार रंगों से रंगा जा सकता है। दावा किया कि तीन रंगों के साथ एक रंग खोजना बहुपद समय में किया जा सकता है लेकिन इस परिणाम के उनके लेखन में कई विवरण शामिल नहीं हैं। कई लेखकों ने कुछ रंगों के साथ वृत्त ग्राफ के प्रतिबंधित उपवर्गों को रंगने की समस्याओं की जांच की है। विशेष रूप से, वृत्त ग्राफ के लिए जिसमें k या अधिक तारों का कोई सेट एक दूसरे को पार नहीं करता है, ग्राफ को कम से कम रंगों से रंगना संभव है। इसे बताने का एक तरीका यह है कि वृत्त ग्राफ-बाउंडेड हैं। विशेष मामले में जब k = 3 (यानी, त्रिभुज-मुक्त वृत्त ग्राफ के लिए) वर्णात्मक संख्या अधिकतम पाँच होती है, और यह तंग होती हैः सभी त्रिभुज-मुक्त वृत्त ग्राफ पांच रंगों से रंगीन हो सकते हैं, और त्रिभुज-मुक्त वृत्त ग्राफ मौजूद होते हैं जिनके लिए पाँच रंगों की आवश्यकता होती है। यदि एक वृत्त ग्राफ का घेर कम से कम पाँच है (यानी, यह त्रिभुज-मुक्त है और इसका कोई चार-अक्षतंतु चक्र नहीं है) तो इसे अधिकतम तीन रंगों से रंगा जा सकता है। त्रिभुज-मुक्त वर्ग ग्राफ को रंगने की समस्या वृक्षों के कार्टेशियन उत्पादों के सममितीय उपग्राफ के रूप में वर्गग्राफ को दर्शाने की समस्या के बराबर है; इस पत्राचार में, रंग में रंगों की संख्या उत्पाद प्रतिनिधित्व में पेड़ों की संख्या से मेल खाती है। अनुप्रयोग वृत्त ग्राफ वी. एल. एस. आई. भौतिक डिजाइन में वायर रूटिंग के लिए एक विशेष मामले के लिए एक अमूर्त प्रतिनिधित्व के रूप में उत्पन्न होते हैं, जिसे "दो-टर्मिनल स्विचबॉक्स रूटिंग" के रूप में जाना जाता है। इस मामले में मार्ग क्षेत्र एक आयत है, सभी जाल दो-टर्मिनल हैं, और टर्मिनलों को आयत की परिधि पर रखा जाता है। यह आसानी से देखा जा सकता है कि इन जालों का प्रतिच्छेदन ग्राफ एक वृत्त ग्राफ है। तार मार्गन चरण के लक्ष्यों में से एक यह सुनिश्चित करना है कि विभिन्न जाल विद्युत रूप से डिस्कनेक्ट रहें, और उनके संभावित प्रतिच्छेदन भागों को विभिन्न संवाहक परतों में रखा जाना चाहिए। इसलिए वृत्त ग्राफ इस रूटिंग समस्या के विभिन्न पहलुओं को पकड़ते हैं। वृत्त ग्राफ के रंगों का उपयोग मनमाने ग्राफ की पुस्तक एम्बेडिंग खोजने के लिए भी किया जा सकता हैः यदि दिए गए ग्राफ G के शीर्षों को एक वृत्त पर व्यवस्थित किया जाता है, जिसमें G के किनारों से वृत्त की कॉर्ड बनती हैं, तो इन कॉर्ड का प्रतिच्छेदन ग्राफ एक वृत्त ग्राफ होता है और इस वृत्त ग्राफ के रंग पुस्तक एम्बेडिंग के बराबर होते हैं जो दिए गए वृत्ताकार लेआउट का सम्मान करते हैं। इस समतुल्यता में, रंग में रंगों की संख्या पुस्तक एम्बेडिंग में पृष्ठों की संख्या से मेल खाती है। संबंधित ग्राफ वर्ग एक ग्राफ एक वृत्त ग्राफ है यदि और केवल तभी जब यह एक रेखा पर अंतरालों के एक समूह का अतिव्यापी ग्राफ हो। यह एक ग्राफ है जिसमें शीर्ष अंतराल के अनुरूप होते हैं, और दो शीर्ष एक किनारे से जुड़े होते हैं यदि दो अंतराल ओवरलैप होते हैं, जिसमें से किसी में भी दूसरा नहीं होता है। एक रेखा पर अंतरालों के एक समूह के प्रतिच्छेदन ग्राफ को अंतराल ग्राफ कहा जाता है। स्ट्रिंग ग्राफ, समतल में वक्रों के प्रतिच्छेदन ग्राफ, एक विशेष मामले के रूप में वृत्त ग्राफ शामिल करते हैं। प्रत्येक दूरी-वंशानुगत ग्राफ एक वृत्त ग्राफ है, जैसा कि प्रत्येक क्रमपरिवर्तन ग्राफ और प्रत्येक उदासीनता ग्राफ है। प्रत्येक बाहरी समतल ग्राफ भी एक वृत्त ग्राफ है। वृत्त ग्राफ को बहुभुज-वृत्त ग्राफ द्वारा सामान्यीकृत किया जाता है, बहुभुज के प्रतिच्छेदन ग्राफ सभी एक ही वृत्त में अंकित होते हैं। टिप्पणियाँ संदर्भ। .. .. .. .. .. .. जैसा कि उद्धृत किया गया है। .. जैसा कि उद्धृत किया गया है। .. जैसा कि उद्धृत किया गया है। .. .. .. .. जैसा कि उद्धृत किया गया है। .. .. .. .. .. .. .. जैसा कि उद्धृत किया गया है। वृत्त ग्राफ के अंतःच्छेदन वर्ग ज्यामितीय ग्राफ