सर्किल ग्राफ: Difference between revisions

Latest revision as of 10:57, 7 March 2023

Error creating thumbnail:

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

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

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

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

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

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

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

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

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

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

अनुप्रयोग

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

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

↑ Kloks, Kratsch & Wong (1998).
↑ Keil (1993)
↑ Garey et al. (1980).
↑ ^4.0 ^4.1 Unger (1988).
↑ Unger (1992).
↑ Davies & McCarty (2021). For earlier bounds see Černý (2007), Gyárfás (1985), Kostochka (1988), and Kostochka & Kratochvíl (1997).
↑ See Kostochka (1988) for the upper bound, and Ageev (1996) for the matching lower bound. Karapetyan (1984) and Gyárfás & Lehel (1985) give earlier weaker bounds on the same problem.
↑ Ageev (1999).
↑ Bandelt, Chepoi & Eppstein (2010).
↑ Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"
↑ Wessel & Pöschel (1985); Unger (1988).
↑ "Circle graph", Information System on Graph Classes and their Inclusions

संदर्भ

Ageev, A. A. (1996), "A triangle-free circle graph with chrom

[1] Kloks, Kratsch & Wong (1998).

[2] Keil (1993)

[FOOTNOTEGareyJohnsonMillerPapadimitriou1980-3] Garey et al. (1980).

[FOOTNOTEUnger1988-4] 4.0 ^4.1 Unger (1988).

[FOOTNOTEUnger1992-5] Unger (1992).

[6] Davies & McCarty (2021). For earlier bounds see Černý (2007), Gyárfás (1985), Kostochka (1988), and Kostochka & Kratochvíl (1997).

[7] See Kostochka (1988) for the upper bound, and Ageev (1996) for the matching lower bound. Karapetyan (1984) and Gyárfás & Lehel (1985) give earlier weaker bounds on the same problem.

[8] Ageev (1999).

[FOOTNOTEBandeltChepoiEppstein2010-9] Bandelt, Chepoi & Eppstein (2010).

[10] Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"

[11] Wessel & Pöschel (1985); Unger (1988).

[12] "Circle graph", Information System on Graph Classes and their Inclusions

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
-{{Short description|Intersection graph of a chord diagram}}
+{{Short description|Intersection graph of a chord diagram}}[[Image:Circle graph and circle model.svg|thumb|175px|पाँच जीवाओं वाला एक वृत्त और संगत वृत्त ग्राफ़।]][[ ग्राफ सिद्धांत |ग्राफ सिद्धांत]] में, एक [[घेरा|वृत्त]] ग्राफ एक कॉर्ड आरेख (गणित) का प्रतिच्छेदन ग्राफ के रूप में होता है। अर्थात, यह एक [[अप्रत्यक्ष ग्राफ]] होता है, जिसके शीर्ष एक वृत्त की जीवा (ज्यामिति) की एक परिमित प्रणाली से संबद्ध होते हैं जैसे कि दो शीर्ष आसन्न होते हैं यदि और केवल यदि संबंधित जीवा एक दूसरे को पार करते हैं।
-{{For|the chart|Pie chart}}
-[[Image:Circle graph and circle model.svg|thumb|175px|पाँच जीवाओं वाला एक वृत्त और संगत वृत्त ग्राफ़।]][[ ग्राफ सिद्धांत ]] में, एक [[घेरा]] ग्राफ एक कॉर्ड आरेख (गणित) का प्रतिच्छेदन ग्राफ है। यही है, यह एक [[अप्रत्यक्ष ग्राफ]] है, जिसके कोने एक वृत्त की जीवा (ज्यामिति) की एक परिमित प्रणाली से जुड़े हो सकते हैं जैसे कि दो कोने आसन्न होते हैं यदि और केवल अगर संबंधित तार एक दूसरे को पार करते हैं।
+== कलन विधि जटिलता ==
+{{harvtxt|स्पिनराड|1994}} में एक o(n<sup>2</sup>) समय कलनविधि का विवरण दिया गया है जो यह परीक्षण करता है कि दिया गया एन-वर्टेक्स अनिर्दिष्ट ग्राफ़ एक वृत्त ग्राफ़ के रूप में होता है और यदि ऐसा है, तो इसका प्रतिनिधित्व करने वाले जीवाओं का एक समुच्चय का निर्माण करता है।
-== एल्गोरिथम जटिलता ==
+सामान्य ग्राफ़ पर एनपी पूर्ण रूप में होते है, अन्य समस्याओं की एक संख्या बहुपद समय कलनविधि जब वृत्त रेखांकन के लिए प्रतिबंधित होती है। उदाहरण के लिए, {{harvtxt|क्लोक्स|1996}} ने दिखाया कि एक वृत्त ग्राफ की [[पेड़ की चौड़ाई|ट्री की चौड़ाई]] निर्धारित की जा सकती है और O(n<sup>3</sup>) में एक ऑप्टीमल ट्री अपघटन का निर्माण किया जाता है। इसके अतिरिक्त, एक न्यूनतम फिल इन अर्थात, जितना संभव हो सके उतना किनारों के साथ एक [[कॉर्डल ग्राफ]] O(n<sup>3</sup>) समय में पाया जा सकता है। जिसमें दिए गए वृत्त ग्राफ़ को सबग्राफ के रूप में सम्मलित किया जाता है।<ref>{{harvtxt|Kloks|Kratsch|Wong|1998}}.</ref> {{harvtxt|टीस्कन|2010}} ने दिखाया है कि एक वृत्तीय ग्राफ का [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र]] समुच्चय O(n log2 n) समय में पाया जाता है, जबकि {{harvtxt|नैश|एंड ग्रेग|2010}} ने दिखाया है कि एक अत्यंत स्वतंत्र समूह ग्राफ का [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र]] समुच्चय O(''n'' min{''d'', ''α''}) समय में पाया जा सकता है, जहां d ग्राफ का एक पैरामीटर के रूप में होता है जिसे इसके घनत्व के रूप में जाना जाता है और α वृत्त ग्राफ की स्वतंत्रता संख्या है।
-{{harvtxt|Spinrad|1994}} एक O(n<sup>2</sup>)-समय एल्गोरिद्म जो परीक्षण करता है कि क्या दिया गया n-वर्टेक्स अप्रत्यक्ष ग्राफ़ एक वृत्त ग्राफ़ है और, यदि ऐसा है, तो इसका प्रतिनिधित्व करने वाले जीवाओं का एक सेट बनाता है।
-कई अन्य समस्याएं जो सामान्य ग्राफ़ पर एनपी-पूर्ण हैं, सर्कल ग्राफ़ तक सीमित होने पर बहुपद समय एल्गोरिदम हैं। उदाहरण के लिए, {{harvtxt|Kloks|1996}} ने दिखाया कि एक सर्कल ग्राफ की [[पेड़ की चौड़ाई]] निर्धारित की जा सकती है, और O(n) में एक इष्टतम पेड़ अपघटन का निर्माण किया गया है<sup>3</sup>) समय। इसके अतिरिक्त, एक न्यूनतम फिल-इन (अर्थात, संभव के रूप में कुछ किनारों के साथ एक [[कॉर्डल ग्राफ]]़ जिसमें दिए गए वृत्त ग्राफ़ को सबग्राफ के रूप में शामिल किया गया है) O(n) में पाया जा सकता है<sup>3</sup>) समय।<ref>{{harvtxt|Kloks|Kratsch|Wong|1998}}.</ref>
+चूँकि, ऐसी भी समस्याएँ हैं जो वृत्त रेखांकन तक सीमित होने पर एनपी-पूर्ण रहती हैं। इनमें [[न्यूनतम हावी सेट]], न्यूनतम जुड़ा हुआ प्रभुत्व समुच्चय और न्यूनतम कुल प्रभुत्व समुच्चय समस्याएं के रूप में सम्मलित होती है।<ref>{{harvtxt|Keil|1993}}</ref>
-{{harvtxt|Tiskin|2010}} ने दिखाया है कि O(n log<sup>2</sup> n) समय, जबकि
+== क्रोमैटिक संख्या ==
-{{harvtxt|Nash|Gregg|2010}} ने दिखाया है कि एक अनवेटेड सर्कल ग्राफ का [[अधिकतम स्वतंत्र सेट]] O(n min{d, α}) समय में पाया जा सकता है, जहां d ग्राफ का एक पैरामीटर है जिसे इसके घनत्व के रूप में जाना जाता है, और α इसकी स्वतंत्रता संख्या है सर्कल ग्राफ।
+[[File:Ageev 5X circle graph.svg|thumb|left|300px|220-वर्टेक्स 5-क्रोमैटिक त्रिकोण-मुक्त वृत्त ग्राफ बनाने वाले जीवा {{harvtxt|Ageev|1996}}, में [[रेखाओं की व्यवस्था]] के रूप में तैयार किया गया
+[[अतिशयोक्तिपूर्ण स्थान]]।]]एक वृत्त ग्राफ की [[रंगीन संख्या|क्रोमैटिक संख्या]] रंगों की न्यूनतम संख्या होती है जिसका उपयोग इसके जीवा को रंगने के लिए किया जा सकता है जिससे कि दो प्रतिच्छेद जीवाओं का रंग समान न हो। चूँकि, वृत्त ग्राफ़ बनाना संभव होता है जिसमें यादृच्छिक ढंग से जीवाओं के बड़े समुच्चय सभी एक दूसरे को पार करते हैं, वृत्त ग्राफ़ की क्रोमैटिक संख्या यादृच्छिक ढंग से बड़ी हो सकती है और वृत्त ग्राफ़ की क्रोमैटिक संख्या का निर्धारण एनपी-पूर्ण के रूप में होता है।{{sfnp|Garey|Johnson|Miller|Papadimitriou|1980}} यह जांचने के लिए एनपी-पूर्ण रहता है कि क्या एक वृत्त ग्राफ को चार रंगों से रंगा जा सकता है।{{sfnp|Unger|1988}} {{harvtxt|अनगर|1992}} ने प्रमाणित किया कि बहुपद समय में तीन रंगों के साथ एक रंग का पता लगाया जा सकता है लेकिन इस परिणाम का उनका लेखन कई विवरणों को छोड़ देता है।{{sfnp|Unger|1992}}
-हालाँकि, ऐसी भी समस्याएँ हैं जो वृत्त रेखांकन तक सीमित होने पर NP-पूर्ण रहती हैं। इनमें [[न्यूनतम हावी सेट]], न्यूनतम जुड़ा हुआ हावी सेट और न्यूनतम कुल हावी सेट समस्याएं शामिल हैं।<ref>{{harvtxt|Keil|1993}}</ref>
+कई लेखकों ने कुछ रंगों के साथ वृत्त ग्राफ़ के प्रतिबंधित उपवर्गों को रंगने की समस्याओं की जांच की है। विशेष रूप से, वृत्त ग्राफ़ के लिए जिसमें k या अधिक जीवाओं का कोई समूह एक दूसरे को पार नहीं करता है, किसी भी ग्राफ को <math>7k^2</math> से अधिक रंग देना संभव होता है। यह बताने की एक विधि यह है कि वृत्त ग्राफ χ-बाउंडेड रूप में होते है।<ref>{{harvtxt|Davies|McCarty|2021}}. For earlier bounds see {{harvtxt|Černý|2007}}, {{harvtxt|Gyárfás|1985}}, {{harvtxt|Kostochka|1988}}, and {{harvtxt|Kostochka|Kratochvíl|1997}}.</ref> विशेष स्थिति में जब k = 3 अर्थात, त्रिभुज-मुक्त ग्राफ़ के लिए रंगीन संख्या अधिक से अधिक पाँच होती है और यह कसे होते है सभी त्रिकोण-मुक्त वृत्त के रेखांकन में पांच रंगों की आवश्यकता होती है, और यहां पर त्रिकोणों-मुक्त वृत्त के ग्राफ दिए गए हैं।<ref>See {{harvtxt|Kostochka|1988}} for the upper bound, and {{harvtxt|Ageev|1996}} for the matching lower bound. {{harvtxt|Karapetyan|1984}} and {{harvtxt|Gyárfás|Lehel|1985}} give earlier weaker bounds on the same problem.</ref> यदि किसी वृत्त ग्राफ़ में परिधि कम से कम पाँच होती है, अर्थात यह त्रिभुज-मुक्त रूप में होता है और इसमें चार-शीर्ष चक्र नहीं होते है, तो इसे अधिकतम तीन रंगों से रंगा जा सकता है।<ref>{{harvtxt|Ageev|1999}}.</ref> त्रिभुज-मुक्त [[वर्गग्राफ]] को रंगने की समस्या स्क्वायरग्राफ को ट्री के ग्राफ सिद्धांत के कार्टेशियन उत्पाद के आइसोमेट्रिक सबग्राफ के रूप में प्रस्तुत करने की समस्या के बराबर है, इस पत्राचार में रंगों की संख्या उत्पाद प्रतिनिधित्व में ट्री की संख्या से मेल खाती है।{{sfnp|Bandelt|Chepoi|Eppstein|2010}}
-== रंगीन संख्या ==
-[[File:Ageev 5X circle graph.svg|thumb|left|300px|220-वर्टेक्स 5-क्रोमैटिक त्रिकोण-मुक्त सर्कल ग्राफ बनाने वाले जीवा {{harvtxt|Ageev|1996}}, में [[रेखाओं की व्यवस्था]] के रूप में तैयार किया गया
-[[अतिशयोक्तिपूर्ण स्थान]]।]]एक सर्कल ग्राफ की [[रंगीन संख्या]] रंगों की न्यूनतम संख्या होती है जिसका उपयोग इसके तारों को रंगने के लिए किया जा सकता है ताकि दो क्रॉसिंग जीवाओं का रंग समान न हो। चूँकि सर्कल ग्राफ़ बनाना संभव है जिसमें मनमाने ढंग से जीवाओं के बड़े सेट सभी एक दूसरे को पार करते हैं, सर्कल ग्राफ़ की रंगीन संख्या मनमाने ढंग से बड़ी हो सकती है, और सर्कल ग्राफ़ की रंगीन संख्या का निर्धारण एनपी-पूर्ण है।{{sfnp|Garey|Johnson|Miller|Papadimitriou|1980}} यह जांचने के लिए एनपी-पूर्ण रहता है कि क्या एक वृत्त ग्राफ को चार रंगों से रंगा जा सकता है।{{sfnp|Unger|1988}} {{harvtxt|Unger|1992}} ने दावा किया कि बहुपद समय में तीन रंगों के साथ एक रंग का पता लगाया जा सकता है लेकिन इस परिणाम का उनका लेखन कई विवरणों को छोड़ देता है।{{sfnp|Unger|1992}}
-कई लेखकों ने कुछ रंगों के साथ सर्कल ग्राफ़ के प्रतिबंधित उपवर्गों को रंगने की समस्याओं की जांच की है। विशेष रूप से, सर्कल ग्राफ़ के लिए जिसमें k या अधिक जीवाओं का कोई सेट एक दूसरे को पार नहीं करता है, ग्राफ़ को कम से कम रंगना संभव है <math>7k^2</math> रंग की। इसे बताने का एक तरीका यह है कि सर्कल ग्राफ χ-बाउंडेड | हैं<math>\chi</math>-बाध्य।<ref>{{harvtxt|Davies|McCarty|2021}}. For earlier bounds see {{harvtxt|Černý|2007}}, {{harvtxt|Gyárfás|1985}}, {{harvtxt|Kostochka|1988}}, and {{harvtxt|Kostochka|Kratochvíl|1997}}.</ref> विशेष मामले में जब k = 3 (अर्थात, त्रिभुज-मुक्त ग्राफ़|त्रिकोण-मुक्त वृत्त ग्राफ़ के लिए) वर्णिक संख्या अधिक से अधिक पाँच होती है, और यह तंग है: सभी त्रिभुज-मुक्त वृत्त ग्राफ़ पाँच रंगों से रंगे जा सकते हैं, और वहाँ त्रिभुज-मुक्त वृत्त ग्राफ़ मौजूद हैं जिनके लिए पाँच रंगों की आवश्यकता होती है।<ref>See {{harvtxt|Kostochka|1988}} for the upper bound, and {{harvtxt|Ageev|1996}} for the matching lower bound. {{harvtxt|Karapetyan|1984}} and {{harvtxt|Gyárfás|Lehel|1985}} give earlier weaker bounds on the same problem.</ref> यदि किसी वृत्त ग्राफ़ में परिधि (ग्राफ़ सिद्धांत) कम से कम पाँच हैं (अर्थात, यह त्रिभुज-मुक्त है और इसमें चार-शीर्ष चक्र नहीं हैं) तो इसे अधिकतम तीन रंगों से रंगा जा सकता है।<ref>{{harvtxt|Ageev|1999}}.</ref> त्रिभुज-मुक्त [[वर्गग्राफ]] को रंगने की समस्या स्क्वायरग्राफ को पेड़ के ग्राफ (ग्राफ सिद्धांत) के कार्टेशियन उत्पाद के आइसोमेट्रिक सबग्राफ के रूप में प्रस्तुत करने की समस्या के बराबर है; इस पत्राचार में, रंग में रंगों की संख्या उत्पाद प्रतिनिधित्व में पेड़ों की संख्या से मेल खाती है।{{sfnp|Bandelt|Chepoi|Eppstein|2010}}
 == अनुप्रयोग ==
-[[वीएलएसआई]] [[भौतिक डिजाइन (इलेक्ट्रॉनिक्स)]] में [[वायर रूटिंग]] के लिए एक विशेष मामले के लिए सार प्रतिनिधित्व के रूप में सर्किल ग्राफ उत्पन्न होते हैं, जिसे दो-टर्मिनल [[स्विचबॉक्स रूटिंग]] के रूप में जाना जाता है। इस मामले में मार्ग क्षेत्र एक आयत है, सभी जाल दो-टर्मिनल हैं, और टर्मिनलों को आयत की परिधि पर रखा गया है। यह आसानी से देखा जा सकता है कि इन जालों का प्रतिच्छेदन ग्राफ एक वृत्तीय ग्राफ है।<ref>Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"</ref> वायर रूटिंग स्टेप के लक्ष्यों में यह सुनिश्चित करना है कि विभिन्न जाल विद्युत रूप से डिस्कनेक्ट रहें, और उनके संभावित प्रतिच्छेदन भागों को अलग-अलग संवाहक परतों में [[एकीकृत सर्किट लेआउट]] होना चाहिए। इसलिए सर्कल ग्राफ़ इस रूटिंग समस्या के विभिन्न पहलुओं को कैप्चर करते हैं।
+[[वीएलएसआई]] [[भौतिक डिजाइन (इलेक्ट्रॉनिक्स)]] में [[वायर रूटिंग]] के लिए एक विशेष स्थिति के लिए सार प्रतिनिधित्व के रूप में सर्किल ग्राफ उत्पन्न होते हैं, जिसे दो-टर्मिनल [[स्विचबॉक्स रूटिंग]] के रूप में जाना जाता है। इस स्थिति में मार्ग क्षेत्र एक आयत के रूप में होते है तथा सभी जाल दो-टर्मिनल और टर्मिनलों को आयत की परिधि पर रखा जाता है। यह आसानी से देखा जा सकता है कि इन जालों का प्रतिच्छेदन ग्राफ एक वृत्तीय ग्राफ के रूप में होता है।<ref>Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"</ref> वायर रूटिंग चरण के लक्ष्यों में यह सुनिश्चित करना होता है कि विभिन्न जाल विद्युत रूप से डिस्कनेक्ट बने रहें और उनके संभावित प्रतिच्छेदन भागों को अलग-अलग संवाहक परतों में [[एकीकृत सर्किट लेआउट|एकीकृत परिपथ लेआउट]] में निर्धारित किया जाता है। इसलिए वृत्त ग्राफ़ इस रूटिंग समस्या के विभिन्न पहलुओं को कैप्चर करते हैं।
-सर्कल ग्राफ़ के रंग का उपयोग मनमाना ग्राफ़ के [[पुस्तक एम्बेडिंग]] को खोजने के लिए भी किया जा सकता है: यदि किसी दिए गए ग्राफ़ जी के कोने एक सर्कल पर व्यवस्थित होते हैं, जी के किनारों के साथ सर्कल के तार बनाते हैं, तो इन जीवाओं का प्रतिच्छेदन ग्राफ एक है सर्कल ग्राफ और इस सर्कल ग्राफ के रंग पुस्तक एम्बेडिंग के समतुल्य हैं जो दिए गए परिपत्र लेआउट का सम्मान करते हैं। इस तुल्यता में, रंग में रंगों की संख्या पुस्तक एम्बेडिंग में पृष्ठों की संख्या से मेल खाती है।{{sfnp|Unger|1988}}
+वृत्त ग्राफ़ के रंग का उपयोग यादृच्छिक ग्राफ़ के [[पुस्तक एम्बेडिंग]] को खोजने के लिए भी किया जाता है, यदि किसी दिए गए ग्राफ़ जी के शीर्ष एक वृत्त पर व्यवस्थित होते हैं, जी के शीर्ष के साथ वृत्त के जीवा बनाते हैं, तो इन जीवाओं का प्रतिच्छेदन ग्राफ एक गोलाकार ग्राफ होता है और इस गोलाकार ग्राफ के रंग पुस्तक एम्बेडिंग के समतुल्य होते है, जो दिए गए परिपत्र लेआउट का सम्मान करते हैं। इस तुल्यता में, रंग में रंगों की संख्या पुस्तक एम्बेडिंग में पृष्ठों की संख्या से मेल खाती है।{{sfnp|Unger|1988}}
 == संबंधित ग्राफ वर्ग ==
-[[File:Overlapgraph.svg|thumb|पाँच अंतरालों वाला एक अंतराल सिस्टम और संबंधित ओवरलैप ग्राफ़।]]एक ग्राफ़ एक सर्कल ग्राफ़ है अगर और केवल अगर यह एक रेखा पर अंतराल के सेट का [[ओवरलैप ग्राफ]]़ है। यह एक ग्राफ़ है जिसमें कोने अंतराल के अनुरूप होते हैं, और दो कोने एक किनारे से जुड़े होते हैं यदि दो अंतराल ओवरलैप होते हैं, न तो दूसरे में शामिल होते हैं।
+[[File:Overlapgraph.svg|thumb|पाँच अंतरालों वाला एक अंतराल सिस्टम और संबंधित ओवरलैप ग्राफ़।]]ग्राफ़ एक वृत्तकार ग्राफ़ के रूप में होता है, यदि जब यह एक रेखा पर अंतराल के सेट का [[ओवरलैप ग्राफ]] के रूप में होता है। यह ऐसा ग्राफ़ है जिसमें शीर्ष अंतराल के अनुरूप होते हैं और यदि दोनों अंतराल ओवरलैप होते हैं तो एक दूसरे में एक के ऊपर एक दूसरे को समाहित करते हैं तो दो शीर्षों को किनारे से जोड़ा जाता है।
 एक रेखा पर अंतरालों के एक समूह के प्रतिच्छेदन ग्राफ को [[अंतराल ग्राफ]] कहा जाता है।
-[[स्ट्रिंग ग्राफ]]़, विमान में वक्रों के प्रतिच्छेदन ग्राफ़, एक विशेष मामले के रूप में वृत्त ग्राफ़ शामिल करते हैं।
+[[स्ट्रिंग ग्राफ]], समतल में वक्रों के प्रतिच्छेदन ग्राफ़, एक विशेष स्थिति के रूप में वृत्त ग्राफ़ सम्मलित होते है।
-हर [[दूरी-वंशानुगत ग्राफ]] एक सर्कल ग्राफ है, जैसा कि हर क्रमचय ग्राफ और हर [[उदासीनता ग्राफ]] है। हर [[आउटरप्लानर ग्राफ]] भी एक सर्कल ग्राफ है।<ref>{{harvtxt|Wessel|Pöschel|1985}}; {{harvtxt|Unger|1988}}.</ref>
+प्रत्येक [[दूरी-वंशानुगत ग्राफ|दूरी हेरेडिटरी ग्राफ]] एक वृत्त ग्राफ है, जैसा कि हर क्रमचय ग्राफ और हर [[उदासीनता ग्राफ]] के रूप में होता है। हर [[आउटरप्लानर ग्राफ]] भी एक वृत्त ग्राफ के रूप में होता है।<ref>{{harvtxt|Wessel|Pöschel|1985}}; {{harvtxt|Unger|1988}}.</ref>
-सर्कल ग्राफ़ को बहुभुज-सर्कल ग्राफ़ द्वारा सामान्यीकृत किया जाता है, बहुभुजों के प्रतिच्छेदन ग्राफ़ सभी एक ही वृत्त में अंकित होते हैं।<ref>{{citation
+वृत्त ग्राफ़ को बहुभुज-वृत्त ग्राफ़ द्वारा सामान्यीकृत किया जाता है, बहुभुजों के प्रतिच्छेदन ग्राफ़ सभी एक ही वृत्त में अंकित होते हैं।<ref>{{citation
   | title = Circle graph
   | work = Information System on Graph Classes and their Inclusions
   | url = http://www.graphclasses.org/classes/gc_132.html}}</ref>
@@ Line 238: / Line 233: @@
   | year = 1985}}. As cited by {{harvtxt|Unger|1988}}.
 {{refend}}
-[[Category: मंडलियां]] [[Category: रेखांकन के चौराहे वर्ग]] [[Category: ज्यामितीय रेखांकन]]
-[[Category: Machine Translated Page]]
+[[Category:CS1 maint]]
 [[Category:Created On 28/02/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:ज्यामितीय रेखांकन]]
+[[Category:मंडलियां]]
+[[Category:रेखांकन के चौराहे वर्ग]]

Anonymous

Search

सर्किल ग्राफ: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:57, 7 March 2023

Contents

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

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

अनुप्रयोग

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

टिप्पणियाँ

संदर्भ