तटस्थता ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| 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 | |||
| 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 | |||
| 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 | |||
| last1 = Looges | first1 = Peter J. | | last1 = Looges | first1 = Peter J. | ||
| last2 = Olariu | first2 = Stephan | | last2 = Olariu | first2 = Stephan | ||
| Line 64: | Line 67: | ||
| year = 1996}}.</ref> | | year = 1996}}.</ref> | ||
*ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता [[मोनोटोनिक अनुक्रम]] बनाता है,<ref name="metric"/> | *ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता [[मोनोटोनिक अनुक्रम]] बनाता है,<ref name="metric"/> | ||
*ऐसे ग्राफ़ जिनके आसन्न | *ऐसे ग्राफ़ जिनके आसन्न आव्यूह को इस प्रकार क्रमबद्ध किया जा सकता है कि, प्रत्येक पंक्ति और प्रत्येक स्तंभ में, आव्यूह के गैर शून्य आव्यूह के मुख्य विकर्ण के निकट सन्निहित अंतराल बनाते हैं।<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 | ||
| last1 = Brandstädt | first1 = Andreas | | last1 = Brandstädt | first1 = Andreas | ||
| last2 = Hundt | first2 = Christian | | last2 = Hundt | first2 = Christian | ||
| Line 89: | Line 92: | ||
*पत्ती की शक्ति में पत्ती की जड़ होती है जो कैटरपिलर है।<ref name="leafroot"/> | *पत्ती की शक्ति में पत्ती की जड़ होती है जो कैटरपिलर है।<ref name="leafroot"/> | ||
अनंत | अनंत ग्राफ़ के लिए, इनमें से कुछ परिभाषाएँ भिन्न हो सकती हैं। | ||
== गुण == | == गुण == | ||
क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे [[कॉर्डल ग्राफ]]़ और पूर्ण ग्राफ़ के विशेष मामले हैं। वे [[सर्कल ग्राफ]]़ का विशेष मामला भी हैं, कुछ ऐसा जो अंतराल ग्राफ़ के बारे में अधिक सामान्य रूप से सही नहीं है। | क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे [[कॉर्डल ग्राफ]]़ और पूर्ण ग्राफ़ के विशेष मामले हैं। वे [[सर्कल ग्राफ]]़ का विशेष मामला भी हैं, कुछ ऐसा जो अंतराल ग्राफ़ के बारे में अधिक सामान्य रूप से सही नहीं है। | ||
यादृच्छिक | यादृच्छिक ग्राफ़ के एर्दोस-रेनी मॉडल में, ए <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> | मनमाना ग्राफ का [[ग्राफ बैंडविड्थ]] <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 124: | Line 127: | ||
| 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> हालांकि, प्रेरित | | 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 155: | Line 158: | ||
| volume = 87 | | volume = 87 | ||
| year = 2003}}.</ref> | | year = 2003}}.</ref> | ||
तटस्थता ग्राफ [[पुनर्निर्माण अनुमान]] का पालन करते हैं: वे विशिष्ट रूप से उनके शीर्ष-हटाए गए | तटस्थता ग्राफ [[पुनर्निर्माण अनुमान]] का पालन करते हैं: वे विशिष्ट रूप से उनके शीर्ष-हटाए गए उपग्राफ द्वारा निर्धारित किए जाते हैं।<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 226: | Line 229: | ||
| 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 | ||
| 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 285: | Line 288: | ||
== यह भी देखें == | == यह भी देखें == | ||
*[[दहलीज ग्राफ]], ग्राफ जिसके किनारों को लेबल के अंतर के बजाय वर्टेक्स लेबल के योग द्वारा निर्धारित किया जाता है | *[[दहलीज ग्राफ]], ग्राफ जिसके किनारों को लेबल के अंतर के बजाय वर्टेक्स लेबल के योग द्वारा निर्धारित किया जाता है | ||
*त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के बजाय | *त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के बजाय स्थिर या अलग हो जाती है | ||
*यूनिट डिस्क ग्राफ, तटस्थता ग्राफ का द्वि-आयामी एनालॉग | *यूनिट डिस्क ग्राफ, तटस्थता ग्राफ का द्वि-आयामी एनालॉग | ||
Revision as of 04:42, 12 March 2023
ग्राफ सिद्धांत में, गणित की एक शाखा, तटस्थता ग्राफ अप्रत्यक्ष ग्राफ है जो प्रत्येक शीर्ष पर वास्तविक संख्या निर्दिष्ट करके और दो शीर्षों को एक किनारे से जोड़कर बनाया जाता है जब उनकी संख्या एक दूसरे की एक इकाई के अन्दर होती है।[1] तटस्थता ग्राफ़ भी इकाई अंतराल के समुच्चय, या उचित रूप से स्थिर अंतरालों के प्रतिच्छेदन ग्राफ़ (अंतराल जिनमें से कोई भी अन्य नहीं है) हैं। इन दो प्रकार के अंतराल निरूपणों के आधार पर, इन ग्राफ़ों को इकाई अंतराल ग्राफ़ या उचित अंतराल ग्राफ़ भी कहा जाता है; वे अंतराल ग्राफ का उपवर्ग बनाते हैं।
समतुल्य लक्षण
तटस्थता ग्राफ के लिए निषिद्ध ग्राफ लक्षण वर्णन: पंजा, सूरज, और जाल (ऊपर, बाएं-दाएं) और चार या अधिक लंबाई के चक्र (नीचे)
परिमित तटस्थता ग्राफ़ को समान रूप से चित्रित किया जा सकता है
- इकाई अंतरालों का प्रतिच्छेदन ग्राफ़,[1]
- अंतरालों के समुच्चयों का प्रतिच्छेदन ग्राफ जिनमें से दो स्थिर नहीं हैं (एक में दूसरा शामिल है),[1][2]
- क्लॉ मुक्त अंतराल ग्राफ,[1][2]
- वे ग्राफ़ जिनमें क्लॉ (ग्राफ़ सिद्धांत) K1,3, नेट (त्रिभुज के प्रत्येक कोने के निकट डिग्री-शीर्ष वाला त्रिभुज), सूर्य (तीन अन्य त्रिभुजों से घिरा त्रिभुज जो प्रत्येक केंद्रीय त्रिभुज के साथ किनारा साझा करता है), या छेद (लंबाई चार या अधिक का चक्र) के लिए प्रेरित उपग्राफ आइसोमॉर्फिक नहीं है ,[3]
- अर्धक्रमों का तुलनात्मक ग्राफ,[1]
- अप्रत्यक्ष ग्राफ़ जिनका रेखीय क्रम ऐसा है कि, जैसे कि प्रत्येक तीन शीर्षों के लिए ––, का क्रम दिया जाता है, यदि किनारा है तो हैं और हैं।[4]
- ऐस्ट्रल ट्रिपल के बिना ग्राफ़, तीन वर्टिकल जोड़े में उन रास्तों से जुड़े होते हैं जो तीसरे वर्टेक्स से बचते हैं और तीसरे वर्टेक्स के लगातार दो पड़ोसियों को भी शामिल नहीं करते हैं,[5]
- वह ग्राफ़ जिसमें प्रत्येक जुड़े हुए घटक में पथ होता है जिसमें घटक का प्रत्येक अधिकतम समूह सन्निहित उप-पथ बनाता है,[6]
- ऐसे ग्राफ़ जिनके शीर्षों को इस तरह से क्रमांकित किया जा सकता है कि हर छोटा रास्ता मोनोटोनिक अनुक्रम बनाता है,[6]
- ऐसे ग्राफ़ जिनके आसन्न आव्यूह को इस प्रकार क्रमबद्ध किया जा सकता है कि, प्रत्येक पंक्ति और प्रत्येक स्तंभ में, आव्यूह के गैर शून्य आव्यूह के मुख्य विकर्ण के निकट सन्निहित अंतराल बनाते हैं।[7]
- कॉर्डलेस पथों की शक्तियों के प्रेरित उपग्राफ।[8]
- पत्ती की शक्ति में पत्ती की जड़ होती है जो कैटरपिलर है।[8]
अनंत ग्राफ़ के लिए, इनमें से कुछ परिभाषाएँ भिन्न हो सकती हैं।
गुण
क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे कॉर्डल ग्राफ़ और पूर्ण ग्राफ़ के विशेष मामले हैं। वे सर्कल ग्राफ़ का विशेष मामला भी हैं, कुछ ऐसा जो अंतराल ग्राफ़ के बारे में अधिक सामान्य रूप से सही नहीं है।
यादृच्छिक ग्राफ़ के एर्दोस-रेनी मॉडल में, ए -वरटेक्स ग्राफ जिसके किनारों की संख्या की तुलना में काफी कम है उच्च संभावना वाला तटस्थता ग्राफ होगा, जबकि ग्राफ जिसके किनारों की संख्या काफी अधिक है