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

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

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