तटस्थता ग्राफ

From Vigyanwiki
Revision as of 21:07, 11 March 2023 by alpha>Shikhav
उदासीनता ग्राफ, बिंदुओं के जोड़े को जोड़कर वास्तविक रेखा पर बिंदुओं के सेट से बनता है, जिनकी दूरी अधिकतम होती है

ग्राफ सिद्धांत में, गणित की शाखा, उदासीनता ग्राफ अप्रत्यक्ष ग्राफ है जो प्रत्येक शीर्ष पर वास्तविक संख्या निर्दिष्ट करके और दो कोने को किनारे से जोड़कर बनाया जाता है जब उनकी संख्या दूसरे की इकाई के अन्दर होती है।[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. ↑ 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=107818’