तटस्थता ग्राफ: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[File:Indifference graph.svg|thumb|300px| | [[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. | ||
| Line 92: | Line 92: | ||
== गुण == | == गुण == | ||
क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, | क्योंकि वे अंतराल ग्राफ़ के विशेष मामले हैं, तटस्थता ग्राफ़ में अंतराल ग्राफ़ के सभी गुण होते हैं; विशेष रूप से वे [[कॉर्डल ग्राफ]]़ और पूर्ण ग्राफ़ के विशेष मामले हैं। वे [[सर्कल ग्राफ]]़ का विशेष मामला भी हैं, कुछ ऐसा जो अंतराल ग्राफ़ के बारे में अधिक सामान्य रूप से सही नहीं है। | ||
यादृच्छिक रेखांकन के एर्दोस-रेनी मॉडल में, ए <math>n</math>-वरटेक्स ग्राफ जिसके किनारों की संख्या की तुलना में काफी कम है <math>n^{2/3}</math> उच्च संभावना वाला | यादृच्छिक रेखांकन के एर्दोस-रेनी मॉडल में, ए <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 105: | ||
| year = 1982| doi-access = free | | year = 1982| doi-access = free | ||
}}.</ref> | }}.</ref> | ||
मनमाना ग्राफ का [[ग्राफ बैंडविड्थ]] <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 115: | Line 115: | ||
| 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> यह संपत्ति [[ पथचौड़ाई ]] और इंटरवल ग्राफ़ के बीच और [[पेड़ की चौड़ाई]] और कॉर्डल ग्राफ़ के बीच समान संबंधों को समानांतर करती है। चौड़ाई की कमजोर धारणा, क्लिक-चौड़ाई, | | 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 124: | ||
| 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 135: | Line 135: | ||
| volume = 5369 | | volume = 5369 | ||
| year = 2008}}.</ref> | | year = 2008}}.</ref> | ||
प्रत्येक जुड़े हुए ग्राफ | प्रत्येक जुड़े हुए ग्राफ तटस्थता ग्राफ में [[हैमिल्टनियन पथ]] होता है।<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 144: | ||
| title = Finding Hamiltonian circuits in proper interval graphs | | title = Finding Hamiltonian circuits in proper interval graphs | ||
| volume = 17 | | volume = 17 | ||
| year = 1983}}.</ref> | | 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 155: | ||
| 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 169: | Line 169: | ||
== एल्गोरिदम == | == एल्गोरिदम == | ||
उच्च आयामी इकाई डिस्क ग्राफ़ के साथ, आउटपुट ग्राफ़ के आकार के संदर्भ में मापे गए [[रैखिक समय]] में बिंदुओं के समुच्चय को उनके | उच्च आयामी इकाई डिस्क ग्राफ़ के साथ, आउटपुट ग्राफ़ के आकार के संदर्भ में मापे गए [[रैखिक समय]] में बिंदुओं के समुच्चय को उनके तटस्थता ग्राफ़ में, या यूनिट अंतराल के समुच्चय को उनके यूनिट अंतराल ग्राफ़ में बदलना संभव है। एल्गोरिथ्म बिंदुओं (या अंतराल केंद्रों) को निकटतम छोटे पूर्णांक तक नीचे ले जाता है, [[हैश तालिका]] का उपयोग उन सभी बिंदुओं के जोड़े को खोजने के लिए करता है जिनके गोल पूर्णांक दूसरे के अन्दर होते हैं (पड़ोसी समस्या के पास निश्चित-त्रिज्या), और परिणामी को फ़िल्टर करता है उन युग्मों की सूची जिनके असंबद्ध मान भी दूसरे के अन्दर हैं।<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 181: | ||
| volume = 6 | | volume = 6 | ||
| year = 1977}}.</ref> | | year = 1977}}.</ref> | ||
ग्राफ के अंतराल प्रतिनिधित्व के निर्माण के लिए PQ पेड़ों का उपयोग करके और फिर परीक्षण करना संभव है कि क्या दिया गया ग्राफ रैखिक समय में | ग्राफ के अंतराल प्रतिनिधित्व के निर्माण के लिए 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 226: | ||
| 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 245: | Line 245: | ||
| volume = 109 | | volume = 109 | ||
| year = 2009}}.</ref> | | year = 2009}}.</ref> | ||
तटस्थता ग्राफ तक सीमित होने पर भी सूची रंग एनपी-पूर्ण रहता है।<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 259: | Line 259: | ||
== अनुप्रयोग == | == अनुप्रयोग == | ||
[[गणितीय मनोविज्ञान]] में, [[उपयोगिता]] कार्यों से | [[गणितीय मनोविज्ञान]] में, [[उपयोगिता]] कार्यों से तटस्थता ग्राफ उत्पन्न होते हैं, फ़ंक्शन को स्केल करके ताकि इकाई उपयोगिताओं में अंतर को इतना छोटा दर्शाती है कि व्यक्तियों को इसके प्रति उदासीन माना जा सकता है। | ||
इस एप्लिकेशन में, उन वस्तुओं के जोड़े जिनकी उपयोगिताओं में बड़ा अंतर है, आंशिक रूप से उनकी उपयोगिताओं के सापेक्ष क्रम द्वारा निर्धारित किया जा सकता है, अर्ध-क्रम दे रहा है।<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 | ||
| Line 286: | Line 286: | ||
*[[दहलीज ग्राफ]], ग्राफ जिसके किनारों को लेबल के अंतर के बजाय वर्टेक्स लेबल के योग द्वारा निर्धारित किया जाता है | *[[दहलीज ग्राफ]], ग्राफ जिसके किनारों को लेबल के अंतर के बजाय वर्टेक्स लेबल के योग द्वारा निर्धारित किया जाता है | ||
*त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के बजाय नेस्टेड या अलग हो जाती है | *त्रुटिपूर्ण रूप से सही ग्राफ, अंतराल ग्राफ जिसके लिए अंतराल की हर जोड़ी ठीक से प्रतिच्छेद करने के बजाय नेस्टेड या अलग हो जाती है | ||
*यूनिट डिस्क ग्राफ, | *यूनिट डिस्क ग्राफ, तटस्थता ग्राफ का द्वि-आयामी एनालॉग | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 04:19, 12 March 2023
ग्राफ सिद्धांत में, गणित की एक शाखा, तटस्थता ग्राफ अप्रत्यक्ष ग्राफ है जो प्रत्येक शीर्ष पर वास्तविक संख्या निर्दिष्ट करके और दो शीर्षों को एक किनारे से जोड़कर बनाया जाता है जब उनकी संख्या एक दूसरे की एक इकाई के अन्दर होती है।[1] तटस्थता ग्राफ़ भी इकाई अंतराल के समुच्चय, या उचित रूप से नेस्टेड अंतरालों के प्रतिच्छेदन ग्राफ़ (अंतराल जिनमें से कोई भी अन्य नहीं है) हैं। इन दो प्रकार के अंतराल निरूपणों के आधार पर, इन ग्राफ़ों को इकाई अंतराल ग्राफ़ या उचित अंतराल ग्राफ़ भी कहा जाता है; वे अंतराल ग्राफ का उपवर्ग बनाते हैं।
समतुल्य लक्षण
तटस्थता ग्राफ के लिए निषिद्ध ग्राफ लक्षण वर्णन: पंजा, सूरज, और जाल (ऊपर, बाएं-दाएं) और चार या अधिक लंबाई के चक्र (नीचे)
परिमित तटस्थता रेखांकन को समान रूप से चित्रित किया जा सकता है
- इकाई अंतरालों का प्रतिच्छेदन रेखांकन,[1]*अंतरालों के समुच्चयों का प्रतिच्छेदन ग्राफ जिनमें से दो नेस्टेड नहीं हैं (में दूसरा शामिल है),[1][2]
- पंजा मुक्त ग्राफ|क्लॉ-फ्री इंटरवल ग्राफ,[1][2]* वे ग्राफ़ जिनमें क्लॉ (ग्राफ़ सिद्धांत) K के लिए प्रेरित सबग्राफ़ आइसोमॉर्फिक नहीं है1,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.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.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.
- ↑ 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.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.
- ↑ 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.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.
- ↑ 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.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.
- ↑ 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.
- ↑ 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.
- ↑ 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.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.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.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.
- ↑ 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.
- ↑ 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). - ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Roberts, Fred S. (1970), "On nontransitive indifference", Journal of Mathematical Psychology, 7: 243–258, doi:10.1016/0022-2496(70)90047-7, MR 0258486.
- ↑ 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.
