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

From Vigyanwiki
No edit summary
No edit summary
Line 95: Line 95:


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


यादृच्छिक ग्राफ़ के एर्दोस-रेनी मॉडल में, ए <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 108: 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 118: 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 138: 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.
Line 158: 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
Line 169: Line 172:
  | year = 1983| doi-access = free
  | year = 1983| doi-access = free
  }}.</ref>
  }}.</ref>




Revision as of 04:57, 12 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=107822’