तटस्थता ग्राफ: Difference between revisions

From Vigyanwiki
No edit summary
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[File:Indifference graph.svg|thumb|300px|एक उदासीनता ग्राफ, बिंदुओं के जोड़े को जोड़कर वास्तविक रेखा पर बिंदुओं के एक सेट से बनता है, जिनकी दूरी अधिकतम एक होती है]][[ग्राफ सिद्धांत]] में, गणित की एक शाखा, एक उदासीनता ग्राफ एक [[अप्रत्यक्ष ग्राफ]] है जो प्रत्येक शीर्ष पर एक [[वास्तविक संख्या]] निर्दिष्ट करके और दो कोने को एक किनारे से जोड़कर बनाया जाता है जब उनकी संख्या एक दूसरे की एक इकाई के भीतर होती है।<ref name="roberts">{{citation
[[File:Indifference graph.svg|thumb|300px|तटस्थता ग्राफ, बिंदुओं के जोड़े को जोड़कर वास्तविक रेखा पर बिंदुओं के समुच्चय से बनता है, जिनकी दूरी अधिकतम होती है]][[ग्राफ सिद्धांत]] में, गणित की एक शाखा, तटस्थता ग्राफ एक [[अप्रत्यक्ष ग्राफ]] है जो प्रत्येक शीर्ष पर [[वास्तविक संख्या]] निर्दिष्ट करके और दो शीर्षों को एक किनारे से जोड़कर बनाया जाता है जब उनकी संख्या एक दूसरे की एक इकाई के अन्दर होती है।<ref name="roberts">{{citation
  | last = Roberts | first = Fred S. | authorlink = Fred S. Roberts
  | last = Roberts | first = Fred S. | authorlink = Fred S. Roberts
  | contribution = Indifference graphs
  | contribution = Indifference graphs
Line 6: Line 6:
  | publisher = Academic Press, New York
  | publisher = Academic Press, New York
  | title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
  | title = Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968)
  | year = 1969}}.</ref> उदासीनता ग्राफ़ भी [[इकाई अंतराल]] के सेट, या उचित रूप से नेस्टेड अंतराल के चौराहे के ग्राफ़ हैं (अंतराल जिनमें से कोई भी अन्य एक नहीं है)। इन दो प्रकार के अंतराल निरूपणों के आधार पर, इन ग्राफ़ों को इकाई [[अंतराल ग्राफ]]़ या उचित अंतराल ग्राफ़ भी कहा जाता है; वे अंतराल ग्राफ का एक उपवर्ग बनाते हैं।
  | year = 1969}}.</ref> तटस्थता ग्राफ़ भी [[इकाई अंतराल]] के समुच्चय, या उचित रूप से स्थिर अंतरालों के प्रतिच्छेदन ग्राफ़ (अंतराल जिनमें से कोई भी अन्य नहीं है) हैं। इन दो प्रकार के अंतराल निरूपणों के आधार पर, इन ग्राफ़ों को इकाई [[अंतराल ग्राफ|अंतराल ग्राफ़]] या उचित अंतराल ग्राफ़ भी कहा जाता है; वे अंतराल ग्राफ का उपवर्ग बनाते हैं।


== समतुल्य लक्षण ==
== समतुल्य लक्षण ==
[[File:Forbidden indifference subgraphs.svg|thumb|240px|उदासीनता ग्राफ के लिए [[निषिद्ध ग्राफ लक्षण वर्णन]]: पंजा, सूरज, और जाल (ऊपर, बाएं-दाएं) और चार या अधिक लंबाई के चक्र (नीचे)]]परिमित उदासीनता रेखांकन को समान रूप से चित्रित किया जा सकता है
[[File:Forbidden indifference subgraphs.svg|thumb|240px|तटस्थता ग्राफ के लिए [[निषिद्ध ग्राफ लक्षण वर्णन]]: पंजा, सूरज, और जाल (ऊपर, बाएं-दाएं) और चार या अधिक लंबाई के चक्र (नीचे)]]परिमित तटस्थता ग्राफ़ को समान रूप से चित्रित किया जा सकता है
*इकाई अंतरालों का प्रतिच्छेदन रेखांकन,<ref name="roberts"/>*अंतरालों के समुच्चयों का प्रतिच्छेदन ग्राफ जिनमें से दो नेस्टेड नहीं हैं (एक में दूसरा शामिल है),<ref name="roberts"/><ref name="bogart-west">{{citation
*इकाई अंतरालों का प्रतिच्छेदन ग्राफ़,<ref name="roberts"/>
*अंतरालों के समुच्चयों का प्रतिच्छेदन ग्राफ जिनमें से दो स्थिर नहीं हैं (एक में दूसरा सम्मिलित है),<ref name="roberts" /><ref name="bogart-west">{{citation
  | last1 = Bogart | first1 = Kenneth P.
  | last1 = Bogart | first1 = Kenneth P.
  | last2 = West | first2 = Douglas B. | author2-link = Douglas West (mathematician)
  | last2 = West | first2 = Douglas B. | author2-link = Douglas West (mathematician)
Line 22: Line 23:
  | year = 1999| arxiv = math/9811036
  | year = 1999| arxiv = math/9811036
  }}.</ref>
  }}.</ref>
*[[पंजा मुक्त ग्राफ]]|क्लॉ-फ्री इंटरवल ग्राफ,<ref name="roberts"/><ref name="bogart-west"/>* वे ग्राफ़ जिनमें क्लॉ (ग्राफ़ थ्योरी) K के लिए एक [[प्रेरित सबग्राफ]]़ आइसोमॉर्फिक नहीं है<sub>1,3</sub>, नेट (त्रिभुज के प्रत्येक कोने के निकट एक डिग्री-एक शीर्ष वाला त्रिभुज), सूर्य (तीन अन्य त्रिभुजों से घिरा एक त्रिभुज जो प्रत्येक केंद्रीय त्रिभुज के साथ एक किनारा साझा करता है), या छेद (लंबाई चार या अधिक का चक्र) ,<ref>{{citation
*[[पंजा मुक्त ग्राफ|क्लॉ मुक्त अंतराल ग्राफ]],<ref name="roberts" /><ref name="bogart-west" />
*वे ग्राफ़ जिनमें क्लॉ (ग्राफ़ सिद्धांत) K<sub>1,3</sub>, नेट (त्रिभुज के प्रत्येक कोने के निकट डिग्री-शीर्ष वाला त्रिभुज), सूर्य (तीन अन्य त्रिभुजों से घिरा त्रिभुज जो प्रत्येक केंद्रीय त्रिभुज के साथ किनारा साझा करता है), या छेद (लंबाई चार या अधिक का चक्र) के लिए [[प्रेरित सबग्राफ|प्रेरित उपग्राफ]] आइसोमॉर्फिक नहीं है ,<ref>{{citation
  | last = Wegner | first = G.
  | last = Wegner | first = G.
  | location = Göttingen, Germany
  | location = Göttingen, Germany
Line 29: Line 31:
  | title = Eigenschaften der Nerven homologisch-einfacher Familien im '''R'''<sup>n</sup>
  | title = Eigenschaften der Nerven homologisch-einfacher Familien im '''R'''<sup>n</sup>
  | year = 1967}}. As cited by {{harvtxt|Hell|Huang|2004}}.</ref>
  | year = 1967}}. As cited by {{harvtxt|Hell|Huang|2004}}.</ref>
*सेमीऑर्डर्स का तुलनात्मक ग्राफ,<ref name="roberts"/>*अप्रत्यक्ष रेखांकन जिनका एक रेखीय क्रम ऐसा है कि, प्रत्येक तीन शीर्षों के लिए आदेश दिया गया है <math>u</math>–<math>v</math>–<math>w</math>, अगर <math>uw</math> एक किनारा है तो हैं <math>uv</math> और <math>vw</math><ref name="greedy">{{citation
*अर्धक्रमों का तुलनात्मक ग्राफ,<ref name="roberts" />
*अप्रत्यक्ष ग्राफ़ जिनका रेखीय क्रम ऐसा है कि, जैसे कि प्रत्येक तीन शीर्षों के लिए <math>u</math>–<math>v</math>–<math>w</math>, का क्रम दिया जाता है, यदि <math>uw</math> किनारा है तो हैं <math>uv</math> और <math>vw</math> हैं।<ref name="greedy">{{citation
  | last1 = Looges | first1 = Peter J.
  | last1 = Looges | first1 = Peter J.
  | last2 = Olariu | first2 = Stephan
  | last2 = Olariu | first2 = Stephan
Line 41: Line 44:
  | year = 1993| doi-access = free
  | year = 1993| doi-access = free
  }}.</ref>
  }}.</ref>
*ऐस्ट्रल ट्रिपल के बिना ग्राफ़, तीन वर्टिकल जोड़े में उन रास्तों से जुड़े होते हैं जो तीसरे वर्टेक्स से बचते हैं और तीसरे वर्टेक्स के लगातार दो पड़ोसियों को भी शामिल नहीं करते हैं,<ref>{{citation
*ऐस्ट्रल ट्रिपल के बिना ग्राफ़, तीन वर्टिकल जोड़े में उन रास्तों से जुड़े होते हैं जो तीसरे शीर्ष् से बचते हैं और तीसरे शीर्ष् के लगातार दो पड़ोसियों को भी सम्मिलित नहीं करते हैं,<ref>{{citation
  | last = Jackowski | first = Zygmunt
  | last = Jackowski | first = Zygmunt
  | doi = 10.1016/0012-365X(92)90135-3
  | doi = 10.1016/0012-365X(92)90135-3
Line 52: Line 55:
  | year = 1992| doi-access = free
  | year = 1992| doi-access = free
  }}.</ref>
  }}.</ref>
* वह ग्राफ़ जिसमें प्रत्येक जुड़े हुए घटक में एक पथ होता है जिसमें घटक का प्रत्येक अधिकतम समूह एक सन्निहित उप-पथ बनाता है,<ref name="metric">{{citation
* वह ग्राफ़ जिसमें प्रत्येक जुड़े हुए घटक में पथ होता है जिसमें घटक का प्रत्येक अधिकतम समूह सन्निहित उप-पथ बनाता है,<ref name="metric">{{citation
  | last1 = Gutierrez | first1 = M.
  | last1 = Gutierrez | first1 = M.
  | last2 = Oubiña | first2 = L.
  | last2 = Oubiña | first2 = L.
Line 63: Line 66:
  | volume = 21
  | volume = 21
  | year = 1996}}.</ref>
  | year = 1996}}.</ref>
*ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता एक [[मोनोटोनिक अनुक्रम]] बनाता है,<ref name="metric"/>  
*ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता [[मोनोटोनिक अनुक्रम]] बनाता है,<ref name="metric"/>  
*ऐसे ग्राफ़ जिनके आसन्न मैट्रिक्स को इस प्रकार क्रमबद्ध किया जा सकता है कि, प्रत्येक पंक्ति और प्रत्येक स्तंभ में, मैट्रिक्स के गैर शून्य मैट्रिक्स के मुख्य विकर्ण के निकट एक सन्निहित अंतराल बनाते हैं।<ref>{{citation
*ऐसे ग्राफ़ जिनके आसन्न आव्यूह को इस प्रकार क्रमबद्ध किया जा सकता है कि, प्रत्येक पंक्ति और प्रत्येक स्तंभ में, आव्यूह के गैर शून्य आव्यूह के मुख्य विकर्ण के निकट सन्निहित अंतराल बनाते हैं।<ref>{{citation
  | last = Mertzios | first = George B.
  | last = Mertzios | first = George B.
  | doi = 10.1016/j.aml.2007.04.001
  | doi = 10.1016/j.aml.2007.04.001
Line 75: Line 78:
  | year = 2008| doi-access = free
  | year = 2008| doi-access = free
  }}.</ref>
  }}.</ref>
*ताररहित पथों की शक्तियों का प्रेरित उप-अनुच्छेद।<ref name="leafroot">{{citation
*कॉर्डलेस पथों की शक्तियों के प्रेरित उपग्राफ।<ref name="leafroot">{{citation
  | last1 = Brandstädt | first1 = Andreas
  | last1 = Brandstädt | first1 = Andreas
  | last2 = Hundt | first2 = Christian
  | last2 = Hundt | first2 = Christian
Line 87: Line 90:
  | year = 2010| doi-access = free
  | year = 2010| doi-access = free
  }}.</ref>
  }}.</ref>
*पत्ती की शक्ति में एक पत्ती की जड़ होती है जो एक कैटरपिलर है।<ref name="leafroot"/>
*पत्ती की शक्ति में पत्ती की जड़ होती है जो कैटरपिलर है।<ref name="leafroot"/>


अनंत रेखांकन के लिए, इनमें से कुछ परिभाषाएँ भिन्न हो सकती हैं।
अनंत ग्राफ़ के लिए, इनमें से कुछ परिभाषाएँ भिन्न हो सकती हैं।


== गुण ==
== गुण ==
क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, उदासीनता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे [[कॉर्डल ग्राफ]]़ और पूर्ण ग्राफ़ के विशेष मामले हैं। वे [[सर्कल ग्राफ]]़ का एक विशेष मामला भी हैं, कुछ ऐसा जो अंतराल ग्राफ़ के बारे में अधिक सामान्य रूप से सही नहीं है।
क्योंकि वे अंतराल ग्राफ़ के विशेष स्थिति हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे [[कॉर्डल ग्राफ|कॉर्डल ग्राफ़]] और पूर्ण ग्राफ़ के विशेष स्थिति हैं। वे [[सर्कल ग्राफ|वृत ग्राफ]] का विशेष स्थिति भी हैं, जो अंतराल ग्राफ़ के अधिक सामान्य रूप से सत्य नहीं है।


यादृच्छिक रेखांकन के एर्दोस-रेनी मॉडल में, ए <math>n</math>-वरटेक्स ग्राफ जिसके किनारों की संख्या की तुलना में काफी कम है <math>n^{2/3}</math> उच्च संभावना वाला एक उदासीनता ग्राफ होगा, जबकि एक ग्राफ जिसके किनारों की संख्या काफी अधिक है <math>n^{2/3}</math> उच्च संभावना वाला एक उदासीनता ग्राफ नहीं होगा।<ref>{{citation
यादृच्छिक ग्राफ़ के एर्दोस-रेनी मॉडल में, <math>n</math>-वरटेक्स ग्राफ जिसके किनारों की संख्या <math>n^{2/3}</math> की तुलना में काफी कम है, उच्च संभावना वाला तटस्थता ग्राफ होगा, जबकि एक ग्राफ जिसके किनारों की संख्या <math>n^{2/3}</math> काफी अधिक है, वह उच्च संभावना वाला तटस्थता ग्राफ नहीं होगा।<ref>{{citation
  | last = Cohen | first = Joel E.
  | last = Cohen | first = Joel E.
  | doi = 10.1016/0012-365X(82)90184-4
  | doi = 10.1016/0012-365X(82)90184-4
Line 105: Line 108:
  | year = 1982| doi-access = free
  | year = 1982| doi-access = free
  }}.</ref>
  }}.</ref>
एक मनमाना ग्राफ का [[ग्राफ बैंडविड्थ]] <math>G</math> एक उदासीनता ग्राफ में अधिकतम क्लिक के आकार से एक कम है जिसमें शामिल है <math>G</math> एक सबग्राफ के रूप में और अधिकतम क्लिक के आकार को कम करने के लिए चुना जाता है।<ref>{{citation
 
एक स्वैच्छिक ग्राफ का [[ग्राफ बैंडविड्थ]] <math>G</math> तटस्थता ग्राफ में अधिकतम क्लिक के आकार से कम है जिसमें <math>G</math> उपग्राफ के रूप में और अधिकतम क्लिक के आकार को कम करने के लिए चुना जाता है।<ref>{{citation
  | last1 = Kaplan | first1 = Haim
  | last1 = Kaplan | first1 = Haim
  | last2 = Shamir | first2 = Ron
  | last2 = Shamir | first2 = Ron
Line 115: Line 119:
  | title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques
  | title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques
  | volume = 25
  | volume = 25
  | year = 1996}}.</ref> यह संपत्ति [[ पथचौड़ाई ]] और इंटरवल ग्राफ़ के बीच और [[पेड़ की चौड़ाई]] और कॉर्डल ग्राफ़ के बीच समान संबंधों को समानांतर करती है। चौड़ाई की कमजोर धारणा, क्लिक-चौड़ाई, उदासीनता ग्राफ पर मनमाने ढंग से बड़ी हो सकती है।<ref>{{citation
  | year = 1996}}.</ref> यह गुण [[ पथचौड़ाई | पथचौड़ाई]] और इंटरवल ग्राफ़ के बीच और [[पेड़ की चौड़ाई]] और कॉर्डल ग्राफ़ के बीच समान संबंधों को समानांतर करती है। चौड़ाई की कमजोर धारणा, क्लिक-चौड़ाई, तटस्थता ग्राफ पर स्वैच्छिक विधि से बड़ी हो सकती है।<ref>{{citation
  | last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
  | last1 = Golumbic | first1 = Martin Charles | author1-link = Martin Charles Golumbic
  | last2 = Rotics | first2 = Udi
  | last2 = Rotics | first2 = Udi
Line 124: Line 128:
  | title = Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999)
  | title = Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999)
  | volume = 140
  | volume = 140
  | year = 1999}}.</ref> हालांकि, प्रेरित सबग्राफ के तहत बंद किए गए उदासीनता ग्राफ के प्रत्येक उचित उपवर्ग ने क्लिक-चौड़ाई को सीमित कर दिया है।<ref name="lozin">{{citation
  | year = 1999}}.</ref> चूंकि, प्रेरित उपग्राफ के अनुसार बंद किए गए तटस्थता ग्राफ के प्रत्येक उचित उपवर्ग ने क्लिक-चौड़ाई को सीमित कर दिया है।<ref name="lozin">{{citation
  | last = Lozin | first = Vadim V.
  | last = Lozin | first = Vadim V.
  | contribution = From tree-width to clique-width: excluding a unit interval graph
  | contribution = From tree-width to clique-width: excluding a unit interval graph
Line 135: Line 139:
  | volume = 5369
  | volume = 5369
  | year = 2008}}.</ref>
  | year = 2008}}.</ref>
प्रत्येक जुड़े हुए ग्राफ उदासीनता ग्राफ में एक [[हैमिल्टनियन पथ]] होता है।<ref name="bertossi">{{citation
 
प्रत्येक जुड़े हुए ग्राफ तटस्थता ग्राफ में [[हैमिल्टनियन पथ]] होता है।<ref name="bertossi">{{citation
  | last = Bertossi | first = Alan A.
  | last = Bertossi | first = Alan A.
  | doi = 10.1016/0020-0190(83)90078-9
  | doi = 10.1016/0020-0190(83)90078-9
Line 144: Line 149:
  | title = Finding Hamiltonian circuits in proper interval graphs
  | title = Finding Hamiltonian circuits in proper interval graphs
  | volume = 17
  | volume = 17
  | year = 1983}}.</ref> एक उदासीनता ग्राफ में [[हैमिल्टनियन चक्र]] होता है यदि और केवल यदि यह [[के-वर्टेक्स-कनेक्टेड ग्राफ]] है।<ref name="pandas">{{citation
  | year = 1983}}.</ref> तटस्थता ग्राफ में [[हैमिल्टनियन चक्र]] होता है यदि और केवल यदि यह [[के-वर्टेक्स-कनेक्टेड ग्राफ|के-शीर्ष्-कनेक्टेड ग्राफ]] है।<ref name="pandas">{{citation
  | last1 = Panda | first1 = B. S.
  | last1 = Panda | first1 = B. S.
  | last2 = Das | first2 = Sajal K.
  | last2 = Das | first2 = Sajal K.
Line 155: Line 160:
  | volume = 87
  | volume = 87
  | year = 2003}}.</ref>
  | year = 2003}}.</ref>
उदासीनता ग्राफ [[पुनर्निर्माण अनुमान]] का पालन करते हैं: वे विशिष्ट रूप से उनके शीर्ष-हटाए गए सबग्राफ द्वारा निर्धारित किए जाते हैं।<ref>{{citation
 
तटस्थता ग्राफ [[पुनर्निर्माण अनुमान]] का पालन करते हैं: वे विशिष्ट रूप से उनके शीर्ष-हटाए गए उपग्राफ द्वारा निर्धारित किए जाते हैं।<ref>{{citation
  | last = von Rimscha | first = Michael
  | last = von Rimscha | first = Michael
  | doi = 10.1016/0012-365X(83)90099-7
  | doi = 10.1016/0012-365X(83)90099-7
Line 166: Line 172:
  | year = 1983| doi-access = free
  | year = 1983| doi-access = free
  }}.</ref>
  }}.</ref>




== एल्गोरिदम ==
== एल्गोरिदम ==
उच्च आयामी इकाई डिस्क ग्राफ़ के साथ, आउटपुट ग्राफ़ के आकार के संदर्भ में मापे गए [[रैखिक समय]] में बिंदुओं के एक सेट को उनके उदासीनता ग्राफ़ में, या यूनिट अंतराल के एक सेट को उनके यूनिट अंतराल ग्राफ़ में बदलना संभव है। एल्गोरिथ्म बिंदुओं (या अंतराल केंद्रों) को निकटतम छोटे पूर्णांक तक नीचे ले जाता है, [[हैश तालिका]] का उपयोग उन सभी बिंदुओं के जोड़े को खोजने के लिए करता है जिनके गोल पूर्णांक एक दूसरे के भीतर होते हैं (पड़ोसी समस्या के पास निश्चित-त्रिज्या), और परिणामी को फ़िल्टर करता है उन युग्मों की सूची जिनके असंबद्ध मान भी एक दूसरे के भीतर हैं।<ref>{{citation
उच्च आयामी इकाई डिस्क ग्राफ़ के साथ, आउटपुट ग्राफ़ के आकार के संदर्भ में मापे गए [[रैखिक समय]] में बिंदुओं के समुच्चय को उनके तटस्थता ग्राफ़ में, या इकाई अंतराल के समुच्चय को उनके इकाई अंतराल ग्राफ़ में बदलना संभव है। एल्गोरिथ्म बिंदुओं (या अंतराल केंद्रों) को निकटतम छोटे पूर्णांक तक नीचे ले जाता है, [[हैश तालिका]] का उपयोग उन सभी बिंदुओं के जोड़े को खोजने के लिए करता है जिनके गोल पूर्णांक दूसरे के अन्दर होते हैं (निकटतम समस्या के पास निश्चित-त्रिज्या), और परिणामी सूची को फ़िल्टर करता है उन युग्मों के लिए जिनके असंबद्ध मान भी एक दूसरे के अन्दर हैं।<ref>{{citation
  | last1 = Bentley | first1 = Jon L. | author1-link = Jon Bentley (computer scientist)
  | last1 = Bentley | first1 = Jon L. | author1-link = Jon Bentley (computer scientist)
  | last2 = Stanat | first2 = Donald F.
  | last2 = Stanat | first2 = Donald F.
Line 181: Line 188:
  | volume = 6
  | volume = 6
  | year = 1977}}.</ref>
  | year = 1977}}.</ref>
ग्राफ के अंतराल प्रतिनिधित्व के निर्माण के लिए PQ पेड़ों का उपयोग करके और फिर परीक्षण करना संभव है कि क्या दिया गया ग्राफ रैखिक समय में एक उदासीनता ग्राफ है, और फिर परीक्षण करता है कि क्या इस प्रतिनिधित्व से प्राप्त शीर्ष क्रम एक उदासीनता ग्राफ के गुणों को संतुष्ट करता है।<ref name="greedy"/>कॉर्डल ग्राफ़ पहचान एल्गोरिदम पर उदासीनता ग्राफ़ के लिए एक मान्यता एल्गोरिदम को आधार बनाना भी संभव है।<ref name="pandas"/>कई वैकल्पिक रैखिक समय पहचान एल्गोरिदम उदासीनता ग्राफ और अंतराल ग्राफ के बीच संबंध के बजाय चौड़ाई-पहली खोज या [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज]] पर आधारित हैं।<ref>{{citation
 
ग्राफ के अंतराल प्रतिनिधित्व के निर्माण के लिए PQ पेड़ों का उपयोग करके और फिर परीक्षण करना संभव है कि क्या दिया गया ग्राफ रैखिक समय में तटस्थता ग्राफ है, और फिर परीक्षण करता है कि क्या इस प्रतिनिधित्व से प्राप्त शीर्ष क्रम तटस्थता ग्राफ के गुणों को संतुष्ट करता है।<ref name="greedy" /> कॉर्डल ग्राफ़ पहचान एल्गोरिदम पर तटस्थता ग्राफ़ के लिए मान्यता एल्गोरिदम को आधार बनाना भी संभव है।<ref name="pandas" /> कई वैकल्पिक रैखिक समय पहचान एल्गोरिदम तटस्थता ग्राफ और अंतराल ग्राफ के बीच संबंध के अतिरिक्त चौड़ाई-पहली खोज या [[लेक्सिकोग्राफिक चौड़ाई-पहली खोज]] पर आधारित हैं।<ref>{{citation
  | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil
  | last1 = Corneil | first1 = Derek G. | author1-link = Derek Corneil
  | last2 = Kim | first2 = Hiryoung
  | last2 = Kim | first2 = Hiryoung
Line 226: Line 234:
  | title = Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs
  | title = Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs
  | volume = 18}}.</ref>
  | volume = 18}}.</ref>
एक बार एक उदासीनता ग्राफ (या एक अंतराल प्रतिनिधित्व में इकाई अंतराल के अनुक्रम द्वारा) का वर्णन करने वाले संख्यात्मक मानों द्वारा कोने को क्रमबद्ध किया गया है, उसी क्रम का उपयोग इन रेखांकन के लिए एक इष्टतम [[ग्राफ रंग]] खोजने के लिए किया जा सकता है, [[सबसे छोटी पथ समस्या]] को हल करने के लिए , और हैमिल्टनियन पथ और [[अधिकतम मिलान]] बनाने के लिए, सभी रैखिक समय में।<ref name="greedy"/>समय में ग्राफ के एक उचित अंतराल प्रतिनिधित्व से एक हैमिल्टनियन चक्र पाया जा सकता है <math>O(n\log n)</math>,<ref name="bertossi"/>लेकिन जब ग्राफ़ को इनपुट के रूप में दिया जाता है, तो वही समस्या रैखिक-समय के समाधान को स्वीकार करती है जिसे अंतराल ग्राफ़ के लिए सामान्यीकृत किया जा सकता है।<ref>{{citation
 
एक बार तटस्थता ग्राफ (या अंतराल प्रतिनिधित्व में इकाई अंतराल के अनुक्रम द्वारा) का वर्णन करने वाले संख्यात्मक मानों द्वारा कोने को क्रमबद्ध किया गया है, उसी क्रम का उपयोग [[सबसे छोटी पथ समस्या]] को हल करने के लिए इन ग्राफ़ के लिए इष्टतम [[ग्राफ रंग]] खोजने, और रैखिक समय में हैमिल्टनियन पथ और [[अधिकतम मिलान]] मिलान बनाने के लिए किया जा सकता है।<ref name="greedy" /> समय <math>O(n\log n)</math> में ग्राफ के उचित अंतराल प्रतिनिधित्व से हैमिल्टनियन चक्र पाया जा सकता है,<ref name="bertossi" /> किन्तु जब ग्राफ़ को इनपुट के रूप में दिया जाता है, तो वही समस्या रैखिक-समय के समाधान को स्वीकार करती है जिसे अंतराल ग्राफ़ के लिए सामान्यीकृत किया जा सकता है।<ref>{{citation
  | last = Keil | first = J. Mark
  | last = Keil | first = J. Mark
  | doi = 10.1016/0020-0190(85)90050-X
  | doi = 10.1016/0020-0190(85)90050-X
Line 245: Line 254:
  | volume = 109
  | volume = 109
  | year = 2009}}.</ref>
  | year = 2009}}.</ref>
उदासीनता ग्राफ तक सीमित होने पर भी सूची रंग एनपी-पूर्ण रहता है।<ref>{{citation
 
तटस्थता ग्राफ तक सीमित होने पर भी सूची रंग एनपी-पूर्ण रहता है।<ref>{{citation
  | last = Marx | first = Dániel
  | last = Marx | first = Dániel
  | doi = 10.1016/j.dam.2005.10.008
  | doi = 10.1016/j.dam.2005.10.008
Line 255: Line 265:
  | volume = 154
  | volume = 154
  | year = 2006| doi-access = free
  | year = 2006| doi-access = free
  }}.</ref> हालांकि, इनपुट में रंगों की कुल संख्या के आधार पर पैरामिट्रीकृत होने पर यह [[पैरामीटरयुक्त जटिलता]] है। निश्चित-पैरामीटर ट्रैक्टेबल है।<ref name="lozin"/>
  }}.</ref> चूंकि, इनपुट में रंगों की कुल संख्या के आधार पर पैरामिट्रीकृत होने पर यह [[पैरामीटरयुक्त जटिलता]] है। निश्चित-पैरामीटर सुविधाजनक है।<ref name="lozin" />
 




== अनुप्रयोग ==
== अनुप्रयोग ==
[[गणितीय मनोविज्ञान]] में, [[उपयोगिता]] कार्यों से उदासीनता ग्राफ उत्पन्न होते हैं, फ़ंक्शन को स्केल करके ताकि एक इकाई उपयोगिताओं में अंतर को इतना छोटा दर्शाती है कि व्यक्तियों को इसके प्रति उदासीन माना जा सकता है।
[[गणितीय मनोविज्ञान]] में, [[उपयोगिता]] कार्यों से तटस्थता ग्राफ उत्पन्न होते हैं, फलन को स्केल करके जिससे इकाई उपयोगिताओं में अंतर को इतना छोटा दर्शाती है कि व्यक्तियों को इसके प्रति उदासीन माना जा सकता है।
इस एप्लिकेशन में, उन वस्तुओं के जोड़े जिनकी उपयोगिताओं में बड़ा अंतर है, आंशिक रूप से उनकी उपयोगिताओं के सापेक्ष क्रम द्वारा निर्धारित किया जा सकता है, एक अर्ध-क्रम दे रहा है।<ref name="roberts"/><ref>{{citation
 
इस एप्लिकेशन में, उन वस्तुओं के जोड़े जिनकी उपयोगिताओं में बड़ा अंतर है, आंशिक रूप से उनकी उपयोगिताओं के सापेक्ष क्रम द्वारा एक अर्ध-क्रम देने का आदेश दिया जा सकता है।<ref name="roberts" /><ref>{{citation
  | last = Roberts | first = Fred S. | authorlink = Fred S. Roberts
  | last = Roberts | first = Fred S. | authorlink = Fred S. Roberts
  | journal = Journal of Mathematical Psychology
  | journal = Journal of Mathematical Psychology
Line 269: Line 281:
  | year = 1970
  | year = 1970
  | doi=10.1016/0022-2496(70)90047-7}}.</ref>
  | doi=10.1016/0022-2496(70)90047-7}}.</ref>
[[बायोइनफॉरमैटिक्स]] में, एक रंगीन ग्राफ को ठीक से रंगीन यूनिट अंतराल ग्राफ में बढ़ाने की समस्या का उपयोग पूर्ण [[प्रतिबंध डाइजेस्ट]] से [[डीएनए]] अनुक्रम असेंबली में झूठी नकारात्मकता का पता लगाने के लिए किया जा सकता है।<ref>{{citation
 
[[बायोइनफॉरमैटिक्स|जैव सूचना विज्ञान]] में, रंगीन ग्राफ को ठीक से रंगीन इकाई अंतराल ग्राफ में बढ़ाने की समस्या का उपयोग पूर्ण [[प्रतिबंध डाइजेस्ट]] से [[डीएनए]] अनुक्रम असेंबली में झूठी नकारात्मकता का पता लगाने के लिए किया जा सकता है।<ref>{{citation
  | last1 = Goldberg | first1 = Paul W.
  | last1 = Goldberg | first1 = Paul W.
  | last2 = Golumbic | first2 = Martin C.
  | last2 = Golumbic | first2 = Martin C.
Line 281: Line 294:
  | volume = 2
  | volume = 2
  | year = 2009}}.</ref>
  | year = 2009}}.</ref>




== यह भी देखें ==
== यह भी देखें ==
*[[दहलीज ग्राफ]], एक ग्राफ जिसके किनारों को लेबल के अंतर के बजाय वर्टेक्स लेबल के योग द्वारा निर्धारित किया जाता है
*[[दहलीज ग्राफ|सीमा ग्राफ]], ग्राफ जिसके किनारों को लेबल के अंतर के अतिरिक्त शीर्ष् लेबल के योग द्वारा निर्धारित किया जाता है
*त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के बजाय नेस्टेड या अलग हो जाती है
*त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के अतिरिक्त स्थिर या अलग हो जाती है
*यूनिट डिस्क ग्राफ, उदासीनता ग्राफ का द्वि-आयामी एनालॉग
*इकाई डिस्क ग्राफ, तटस्थता ग्राफ का द्वि-आयामी एनालॉग


==संदर्भ==
==संदर्भ==
Line 294: Line 308:
==बाहरी संबंध==
==बाहरी संबंध==
*[http://www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [http://www.graphclasses.org/classes/gc_299.html unit interval graph]
*[http://www.graphclasses.org/index.html Information System on Graph Class Inclusions]: [http://www.graphclasses.org/classes/gc_299.html unit interval graph]
[[Category: बिल्कुल सही रेखांकन]] [[Category: रेखांकन के चौराहे वर्ग]] [[Category: ज्यामितीय रेखांकन]]


[[Category: Machine Translated Page]]
[[Category:Created On 28/02/2023]]
[[Category:Created On 28/02/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:ज्यामितीय रेखांकन]]
[[Category:बिल्कुल सही रेखांकन]]
[[Category:रेखांकन के चौराहे वर्ग]]

Latest revision as of 10:36, 15 March 2023

तटस्थता ग्राफ, बिंदुओं के जोड़े को जोड़कर वास्तविक रेखा पर बिंदुओं के समुच्चय से बनता है, जिनकी दूरी अधिकतम होती है

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

समतुल्य लक्षण

तटस्थता ग्राफ के लिए निषिद्ध ग्राफ लक्षण वर्णन: पंजा, सूरज, और जाल (ऊपर, बाएं-दाएं) और चार या अधिक लंबाई के चक्र (नीचे)

परिमित तटस्थता ग्राफ़ को समान रूप से चित्रित किया जा सकता है

  • इकाई अंतरालों का प्रतिच्छेदन ग्राफ़,[1]
  • अंतरालों के समुच्चयों का प्रतिच्छेदन ग्राफ जिनमें से दो स्थिर नहीं हैं (एक में दूसरा सम्मिलित है),[1][2]
  • क्लॉ मुक्त अंतराल ग्राफ,[1][2]
  • वे ग्राफ़ जिनमें क्लॉ (ग्राफ़ सिद्धांत) K1,3, नेट (त्रिभुज के प्रत्येक कोने के निकट डिग्री-शीर्ष वाला त्रिभुज), सूर्य (तीन अन्य त्रिभुजों से घिरा त्रिभुज जो प्रत्येक केंद्रीय त्रिभुज के साथ किनारा साझा करता है), या छेद (लंबाई चार या अधिक का चक्र) के लिए प्रेरित उपग्राफ आइसोमॉर्फिक नहीं है ,[3]
  • अर्धक्रमों का तुलनात्मक ग्राफ,[1]
  • अप्रत्यक्ष ग्राफ़ जिनका रेखीय क्रम ऐसा है कि, जैसे कि प्रत्येक तीन शीर्षों के लिए ––, का क्रम दिया जाता है, यदि किनारा है तो हैं और हैं।[4]
  • ऐस्ट्रल ट्रिपल के बिना ग्राफ़, तीन वर्टिकल जोड़े में उन रास्तों से जुड़े होते हैं जो तीसरे शीर्ष् से बचते हैं और तीसरे शीर्ष् के लगातार दो पड़ोसियों को भी सम्मिलित नहीं करते हैं,[5]
  • वह ग्राफ़ जिसमें प्रत्येक जुड़े हुए घटक में पथ होता है जिसमें घटक का प्रत्येक अधिकतम समूह सन्निहित उप-पथ बनाता है,[6]
  • ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता मोनोटोनिक अनुक्रम बनाता है,[6]
  • ऐसे ग्राफ़ जिनके आसन्न आव्यूह को इस प्रकार क्रमबद्ध किया जा सकता है कि, प्रत्येक पंक्ति और प्रत्येक स्तंभ में, आव्यूह के गैर शून्य आव्यूह के मुख्य विकर्ण के निकट सन्निहित अंतराल बनाते हैं।[7]
  • कॉर्डलेस पथों की शक्तियों के प्रेरित उपग्राफ।[8]
  • पत्ती की शक्ति में पत्ती की जड़ होती है जो कैटरपिलर है।[8]

अनंत ग्राफ़ के लिए, इनमें से कुछ परिभाषाएँ भिन्न हो सकती हैं।

गुण

क्योंकि वे अंतराल ग्राफ़ के विशेष स्थिति हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे कॉर्डल ग्राफ़ और पूर्ण ग्राफ़ के विशेष स्थिति हैं। वे वृत ग्राफ का विशेष स्थिति भी हैं, जो अंतराल ग्राफ़ के अधिक सामान्य रूप से सत्य नहीं है।

यादृच्छिक ग्राफ़ के एर्दोस-रेनी मॉडल में, -वरटेक्स ग्राफ जिसके किनारों की संख्या की तुलना में काफी कम है, उच्च संभावना वाला तटस्थता ग्राफ होगा, जबकि एक ग्राफ जिसके किनारों की संख्या काफी अधिक है, वह उच्च संभावना वाला तटस्थता ग्राफ नहीं होगा।[9]

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

प्रत्येक जुड़े हुए ग्राफ तटस्थता ग्राफ में हैमिल्टनियन पथ होता है।[13] तटस्थता ग्राफ में हैमिल्टनियन चक्र होता है यदि और केवल यदि यह के-शीर्ष्-कनेक्टेड ग्राफ है।[14]

तटस्थता ग्राफ पुनर्निर्माण अनुमान का पालन करते हैं: वे विशिष्ट रूप से उनके शीर्ष-हटाए गए उपग्राफ द्वारा निर्धारित किए जाते हैं।[15]


एल्गोरिदम

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

ग्राफ के अंतराल प्रतिनिधित्व के निर्माण के लिए PQ पेड़ों का उपयोग करके और फिर परीक्षण करना संभव है कि क्या दिया गया ग्राफ रैखिक समय में तटस्थता ग्राफ है, और फिर परीक्षण करता है कि क्या इस प्रतिनिधित्व से प्राप्त शीर्ष क्रम तटस्थता ग्राफ के गुणों को संतुष्ट करता है।[4] कॉर्डल ग्राफ़ पहचान एल्गोरिदम पर तटस्थता ग्राफ़ के लिए मान्यता एल्गोरिदम को आधार बनाना भी संभव है।[14] कई वैकल्पिक रैखिक समय पहचान एल्गोरिदम तटस्थता ग्राफ और अंतराल ग्राफ के बीच संबंध के अतिरिक्त चौड़ाई-पहली खोज या लेक्सिकोग्राफिक चौड़ाई-पहली खोज पर आधारित हैं।[17][18][19][20]

एक बार तटस्थता ग्राफ (या अंतराल प्रतिनिधित्व में इकाई अंतराल के अनुक्रम द्वारा) का वर्णन करने वाले संख्यात्मक मानों द्वारा कोने को क्रमबद्ध किया गया है, उसी क्रम का उपयोग सबसे छोटी पथ समस्या को हल करने के लिए इन ग्राफ़ के लिए इष्टतम ग्राफ रंग खोजने, और रैखिक समय में हैमिल्टनियन पथ और अधिकतम मिलान मिलान बनाने के लिए किया जा सकता है।[4] समय में ग्राफ के उचित अंतराल प्रतिनिधित्व से हैमिल्टनियन चक्र पाया जा सकता है,[13] किन्तु जब ग्राफ़ को इनपुट के रूप में दिया जाता है, तो वही समस्या रैखिक-समय के समाधान को स्वीकार करती है जिसे अंतराल ग्राफ़ के लिए सामान्यीकृत किया जा सकता है।[21][22]

तटस्थता ग्राफ तक सीमित होने पर भी सूची रंग एनपी-पूर्ण रहता है।[23] चूंकि, इनपुट में रंगों की कुल संख्या के आधार पर पैरामिट्रीकृत होने पर यह पैरामीटरयुक्त जटिलता है। निश्चित-पैरामीटर सुविधाजनक है।[12]


अनुप्रयोग

गणितीय मनोविज्ञान में, उपयोगिता कार्यों से तटस्थता ग्राफ उत्पन्न होते हैं, फलन को स्केल करके जिससे इकाई उपयोगिताओं में अंतर को इतना छोटा दर्शाती है कि व्यक्तियों को इसके प्रति उदासीन माना जा सकता है।

इस एप्लिकेशन में, उन वस्तुओं के जोड़े जिनकी उपयोगिताओं में बड़ा अंतर है, आंशिक रूप से उनकी उपयोगिताओं के सापेक्ष क्रम द्वारा एक अर्ध-क्रम देने का आदेश दिया जा सकता है।[1][24]

जैव सूचना विज्ञान में, रंगीन ग्राफ को ठीक से रंगीन इकाई अंतराल ग्राफ में बढ़ाने की समस्या का उपयोग पूर्ण प्रतिबंध डाइजेस्ट से डीएनए अनुक्रम असेंबली में झूठी नकारात्मकता का पता लगाने के लिए किया जा सकता है।[25]


यह भी देखें

  • सीमा ग्राफ, ग्राफ जिसके किनारों को लेबल के अंतर के अतिरिक्त शीर्ष् लेबल के योग द्वारा निर्धारित किया जाता है
  • त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के अतिरिक्त स्थिर या अलग हो जाती है
  • इकाई डिस्क ग्राफ, तटस्थता ग्राफ का द्वि-आयामी एनालॉग

संदर्भ

  1. ↑ 1.0 1.1 1.2 1.3 1.4 1.5 Roberts, Fred S. (1969), "Indifference graphs", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 139–146, MR 0252267.
  2. ↑ 2.0 2.1 Bogart, Kenneth P.; West, Douglas B. (1999), "A short proof that "proper = unit"", Discrete Mathematics, 201 (1–3): 21–23, arXiv:math/9811036, doi:10.1016/S0012-365X(98)00310-0, MR 1687858.
  3. ↑ Wegner, G. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im Rn, Ph.D. thesis, Göttingen, Germany: Göttingen University. As cited by Hell & Huang (2004).
  4. ↑ 4.0 4.1 4.2 Looges, Peter J.; Olariu, Stephan (1993), "Optimal greedy algorithms for indifference graphs", Computers & Mathematics with Applications, 25 (7): 15–25, doi:10.1016/0898-1221(93)90308-I, MR 1203643.
  5. ↑ Jackowski, Zygmunt (1992), "A new characterization of proper interval graphs", Discrete Mathematics, 105 (1–3): 103–109, doi:10.1016/0012-365X(92)90135-3, MR 1180196.
  6. ↑ 6.0 6.1 Gutierrez, M.; Oubiña, L. (1996), "Metric characterizations of proper interval graphs and tree-clique graphs", Journal of Graph Theory, 21 (2): 199–205, doi:10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M, MR 1368745.
  7. ↑ Mertzios, George B. (2008), "A matrix characterization of interval and proper interval graphs", Applied Mathematics Letters, 21 (4): 332–337, doi:10.1016/j.aml.2007.04.001, MR 2406509.
  8. ↑ 8.0 8.1 Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics, 310: 897–910, doi:10.1016/j.disc.2009.10.006.
  9. ↑ Cohen, Joel E. (1982), "The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph", Discrete Mathematics, 40 (1): 21–24, doi:10.1016/0012-365X(82)90184-4, MR 0676708.
  10. ↑ Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing, 25 (3): 540–561, doi:10.1137/S0097539793258143, MR 1390027.
  11. ↑ Golumbic, Martin Charles; Rotics, Udi (1999), "The clique-width of unit interval graphs is unbounded", Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Congressus Numerantium, vol. 140, pp. 5–17, MR 1745205.
  12. ↑ 12.0 12.1 Lozin, Vadim V. (2008), "From tree-width to clique-width: excluding a unit interval graph", Algorithms and computation, Lecture Notes in Comput. Sci., vol. 5369, Springer, Berlin, pp. 871–882, doi:10.1007/978-3-540-92182-0_76, MR 2539978.
  13. ↑ 13.0 13.1 Bertossi, Alan A. (1983), "Finding Hamiltonian circuits in proper interval graphs", Information Processing Letters, 17 (2): 97–101, doi:10.1016/0020-0190(83)90078-9, MR 0731128.
  14. ↑ 14.0 14.1 Panda, B. S.; Das, Sajal K. (2003), "A linear time recognition algorithm for proper interval graphs", Information Processing Letters, 87 (3): 153–161, doi:10.1016/S0020-0190(03)00298-9, MR 1986780.
  15. ↑ von Rimscha, Michael (1983), "Reconstructibility and perfect graphs", Discrete Mathematics, 47 (2–3): 283–291, doi:10.1016/0012-365X(83)90099-7, MR 0724667.
  16. ↑ Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212, doi:10.1016/0020-0190(77)90070-9, MR 0489084{{citation}}: CS1 maint: multiple names: authors list (link).
  17. ↑ Corneil, Derek G.; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P. (1995), "Simple linear time recognition of unit interval graphs", Information Processing Letters, 55 (2): 99–104, CiteSeerX 10.1.1.39.855, doi:10.1016/0020-0190(95)00046-F, MR 1344787.
  18. ↑ Herrera de Figueiredo, Celina M.; Meidanis, João; Picinin de Mello, Célia (1995), "A linear-time algorithm for proper interval graph recognition", Information Processing Letters, 56 (3): 179–184, doi:10.1016/0020-0190(95)00133-W, MR 1365411.
  19. ↑ Corneil, Derek G. (2004), "A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs", Discrete Applied Mathematics, 138 (3): 371–379, doi:10.1016/j.dam.2003.07.001, MR 2049655.
  20. ↑ Hell, Pavol; Huang, Jing (2004), "Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs", SIAM Journal on Discrete Mathematics, 18 (3): 554–570, doi:10.1137/S0895480103430259, MR 2134416.
  21. ↑ Keil, J. Mark (1985), "Finding Hamiltonian circuits in interval graphs", Information Processing Letters, 20 (4): 201–206, doi:10.1016/0020-0190(85)90050-X, MR 0801816.
  22. ↑ Ibarra, Louis (2009), "A simple algorithm to find Hamiltonian cycles in proper interval graphs", Information Processing Letters, 109 (18): 1105–1108, doi:10.1016/j.ipl.2009.07.010, MR 2552898.
  23. ↑ Marx, Dániel (2006), "Precoloring extension on unit interval graphs", Discrete Applied Mathematics, 154 (6): 995–1002, doi:10.1016/j.dam.2005.10.008, MR 2212549.
  24. ↑ Roberts, Fred S. (1970), "On nontransitive indifference", Journal of Mathematical Psychology, 7: 243–258, doi:10.1016/0022-2496(70)90047-7, MR 0258486.
  25. ↑ Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009), "Four strikes against physical mapping of DNA", Journal of Computational Biology, 2 (2), doi:10.1089/cmb.1995.2.139, PMID 7497116.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=तटस्थता_ग्राफ&oldid=108681’