तुलनीयता ग्राफ

From Vigyanwiki

ग्राफ़ सिद्धांत में, तुलनीयता ग्राफ़ एक अप्रत्यक्ष ग्राफ है जो आंशिक क्रम में एक दूसरे से तुलनीय तत्वों के जोड़े को जोड़ता है। तुलनीयता ग्राफ़ को संक्रमणीय रूप से उन्मुख ग्राफ़, आंशिक रूप से क्रमबद्ध ग्राफ़, रोकथाम ग्राफ़ और भाजक ग्राफ़[1] भी कहा जाता है।[2]

इस प्रकार अतुलनीयता ग्राफ़ एक अप्रत्यक्ष ग्राफ़ है जो उन तत्वों के जोड़े को आंशिक क्रम में जोड़ता है जो एक दूसरे से तुलनीय नहीं हैं।

परिभाषाएँ और लक्षण वर्णन

एक पोसेट का हैस आरेख (बाएं) और उसका तुलनीयता ग्राफ (दाएं)
तुलनीयता ग्राफ़ के निषिद्ध प्रेरित उपग्राफों में से एक। सामान्यीकृत चक्र a–b–d–f–d–c–e–c–b–aइस ग्राफ़ में विषम लंबाई (नौ) है किन्तु कोई त्रिकोणीय जीवा नहीं है।

किसी भी सख्त आंशिक रूप से आदेशित के लिए, (एस, <) का तुलनीयता ग्राफ ग्राफ (एस, ⊥) है जिसके शीर्ष S तत्व हैं और किनारे वे जोड़े हैं {u, v} हैं ऐसे तत्वों का u < v. अर्थात्, आंशिक रूप से ऑर्डर किए गए सेट के लिए, निर्देशित एसाइक्लिक ग्राफ़ लें, सकर्मक समापन लागू करें, और अभिविन्यास हटा दें।

समान रूप से, एक तुलनीयता ग्राफ़ एक ऐसा ग्राफ़ है जिसमें एक संक्रमणीय अभिविन्यास होता है,[3] ग्राफ़ के किनारों पर दिशाओं का एक असाइनमेंट (अर्थात ग्राफ़ का एक अभिविन्यास ) जैसे कि परिणामी निर्देशित ग्राफ का आसन्न संबंध सकर्मक संबंध है: जब भी निर्देशित किनारे उपस्तिथ होते हैं (x,y) और (y,z) उपस्तिथ हैं‚ वहाँ एक किनारा (x,z) उपस्तिथ होना चाहिए।

कोई किसी भी परिमित आंशिक क्रम को समुच्चयों के एक परिवार के रूप में प्रस्तुत कर सकता है, जैसे कि x < y आंशिक क्रम में जब भी x के अनुरूप समुच्चय‚ y के संगत समुच्चय का उपसमुच्चय है। इस तरह, तुलनीयता ग्राफ़ को सेट परिवारों के रोकथाम ग्राफ़ के बराबर दिखाया जा सकता है; अर्थात, परिवार में प्रत्येक सेट के लिए एक शीर्ष के साथ एक ग्राफ और दो सेटों के बीच एक किनारा जब भी एक दूसरे का उपसमुच्चय होता है।[4]

वैकल्पिक रूप से, कोई पूर्णांकों के परिवार द्वारा आंशिक क्रम का प्रतिनिधित्व कर सकता है, जैसे कि x < y जब भी x के अनुरूप पूर्णांक, y के अनुरूप पूर्णांक का विभाजक होता है। इस प्रकार निर्माण के कारण, तुलनीयता ग्राफ़ को विभाजक ग्राफ़ भी कहा जाता है।[1]

तुलनीयता ग्राफ़ को ऐसे ग्राफ़ के रूप में वर्णित किया जा सकता है, जो विषम लंबाई के प्रत्येक सामान्यीकृत चक्र (नीचे देखें) के लिए, चक्र में दूरी दो पर स्थित दो शीर्षों को जोड़ने वाला एक किनारा (x,y) पा सकता है। इस प्रकार ऐसे किनारे को त्रिकोणीय राग कहते हैं। इस संदर्भ में, एक सामान्यीकृत चक्र को ग्राफ़ सिद्धांत वॉक की शब्दावली के रूप में परिभाषित किया गया है जो प्रत्येक दिशा में ग्राफ़ के प्रत्येक किनारे का अधिकतम एक बार उपयोग करता है।[5] इस प्रकार तुलनीयता ग्राफ़ को निषिद्ध प्रेरित उपग्राफ़ों की सूची द्वारा भी चित्रित किया जा सकता है।[6]

अन्य ग्राफ़ परिवारों से संबंध

प्रत्येक पूर्ण ग्राफ़ एक तुलनीयता ग्राफ़ है, कुल क्रम का तुलनीयता ग्राफ़ है, प्रत्येक पूर्ण ग्राफ़ के सभी चक्रीय अभिविन्यास सकर्मक होते हैं। प्रत्येक द्विदलीय ग्राफ एक तुलनीयता ग्राफ भी है। इस प्रकार द्विदलीय ग्राफ के किनारों को द्विविभाजन के एक तरफ से दूसरी ओर उन्मुख करने से ऊंचाई दो के आंशिक क्रम के अनुरूप एक संक्रमणीय अभिविन्यास प्राप्त होता है। इस प्रकार जैसा सेमुर (2006) देखता है, प्रत्येक तुलनीयता ग्राफ जो न तो पूर्ण है और न ही द्विदलीय है, उसमें तिरछा विभाजन होता है।

किसी भी अंतराल ग्राफ का पूरक (ग्राफ सिद्धांत) एक तुलनीयता ग्राफ है। इस प्रकार तुलनीयता संबंध को अंतराल क्रम कहा जाता है। अंतराल ग्राफ़ वास्तव में वे ग्राफ़ होते हैं जो कॉर्डल होते हैं और जिनमें तुलनीयता ग्राफ़ पूरक होते हैं।[7]

क्रमपरिवर्तन ग्राफ अंतरालों के एक सेट पर एक रोकथाम ग्राफ़ है।[8] इसलिए, क्रमपरिवर्तन ग्राफ़ तुलनीयता ग्राफ़ का एक और उपवर्ग हैं।

तुच्छ रूप से परिपूर्ण ग्राफ़ जड़ वाले पेड़ों की तुलनीयता के ग्राफ़ हैं।[9]

कोग्राफ़ को श्रृंखला-समानांतर आंशिक आदेशों के तुलनीयता ग्राफ़ के रूप में चित्रित किया जा सकता है; इस प्रकार, कोग्राफ़ भी तुलनीयता ग्राफ़ हैं।[10]

सीमा ग्राफ एक अन्य विशेष प्रकार का तुलनीयता ग्राफ़ है।

प्रत्येक तुलनीयता ग्राफ़ पूर्ण ग्राफ़ है। तुलनीयता ग्राफ़ की पूर्णता मिर्स्की की प्रमेय है और उनके पूरकों की पूर्णता दिलवर्थ की प्रमेय है; इन तथ्यों को, सही ग्राफ़ प्रमेय के साथ मिलकर, दिलवर्थ के प्रमेय को मिर्स्की के प्रमेय से या इसके विपरीत सिद्ध करने के लिए उपयोग किया जा सकता है।[11] इस प्रकार अधिक विशेष रूप से, तुलनीयता ग्राफ़ पूरी तरह से क्रमबद्ध ग्राफ़ हैं, सही ग्राफ़ का एक उपवर्ग: ग्राफ़ के एक संक्रमणीय अभिविन्यास के टोपोलॉजिकल ऑर्डरिंग के लिए एक लालची रंग एल्गोरिदम उन्हें इष्टतम रूप से रंग देगा।[12]

प्रत्येक तुलनीयता ग्राफ का पूरक ग्राफ एक स्ट्रिंग ग्राफ़ है।[13]

एल्गोरिदम

किसी ग्राफ़ का सकर्मक अभिविन्यास, यदि वह उपस्तिथ है, रैखिक समय में पाया जा सकता है।[14] इस प्रकार चूँकि, ऐसा करने के लिए एल्गोरिदम किसी भी ग्राफ़ के किनारों पर अभिविन्यास निर्दिष्ट करेगा, इसलिए यह परीक्षण करने के कार्य को पूरा करने के लिए कि क्या ग्राफ़ एक तुलनीयता ग्राफ़ है, किसी को यह परीक्षण करना होगा कि क्या परिणामी अभिविन्यास सकर्मक है, एक समस्या जो मैट्रिक्स गुणन की जटिलता के बराबर है।

क्योंकि तुलनीयता ग्राफ एकदम सही हैं, कई समस्याएं जो ग्राफ के अधिक सामान्य वर्गों पर कठिन हैं, जिनमें ग्राफ़ रंग और स्वतंत्र सेट समस्या सम्मिलित है, तुलनीयता ग्राफ के लिए बहुपद समय में हल किया जा सकता है।

टिप्पणियाँ

  1. ↑ 1.0 1.1 Chartrand et al. (2001).
  2. ↑ Golumbic (1980), p. 105; Brandstädt, Le & Spinrad (1999), p. 94.
  3. ↑ Ghouila-Houri (1962); see Brandstädt, Le & Spinrad (1999), theorem 1.4.1, p. 12. Although the orientations coming from partial orders are acyclic, it is not necessary to include acyclicity as a condition of this characterization.
  4. ↑ Urrutia (1989); Trotter (1992); Brandstädt, Le & Spinrad (1999), section 6.3, pp. 94–96.
  5. ↑ Ghouila-Houri (1962) and Gilmore & Hoffman (1964). See also Brandstädt, Le & Spinrad (1999), theorem 6.1.1, p. 91.
  6. ↑ Gallai (1967); Trotter (1992); Brandstädt, Le & Spinrad (1999), p. 91 and p. 112.
  7. ↑ Transitive orientability of interval graph complements was proven by Ghouila-Houri (1962); the characterization of interval graphs is due to Gilmore & Hoffman (1964). See also Golumbic (1980), prop. 1.3, pp. 15–16.
  8. ↑ Dushnik & Miller (1941). Brandstädt, Le & Spinrad (1999), theorem 6.3.1, p. 95.
  9. ↑ Brandstädt, Le & Spinrad (1999), theorem 6.6.1, p. 99.
  10. ↑ Brandstädt, Le & Spinrad (1999), corollary 6.4.1, p. 96; Jung (1978).
  11. ↑ Golumbic (1980), theorems 5.34 and 5.35, p. 133.
  12. ↑ Maffray (2003).
  13. ↑ Golumbic, Rotem & Urrutia (1983) and Lovász (1983). See also Fox & Pach (2012).
  14. ↑ McConnell & Spinrad (1997); see Brandstädt, Le & Spinrad (1999), p. 91.

संदर्भ

  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
  • Chartrand, Gary; Muntean, Raluca; Saenpholphat, Varaporn; Zhang, Ping (2001), "Which graphs are divisor graphs?", Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001), Congressus Numerantium, 151: 189–200, MR 1887439
  • Dushnik, Ben; Miller, E. W. (1941), "Partially ordered sets", American Journal of Mathematics, The Johns Hopkins University Press, 63 (3): 600–610, doi:10.2307/2371374, hdl:10338.dmlcz/100377, JSTOR 2371374, MR 0004862.
  • Fox, Jacob; Pach, Jànos (2012), "String graphs and incomparability graphs" (PDF), Advances in Mathematics, 230 (3): 1381–1401, doi:10.1016/j.aim.2012.03.011.
  • Gallai, Tibor (1967), "Transitiv orientierbare Graphen", Acta Math. Acad. Sci. Hung., 18 (1–2): 25–66, doi:10.1007/BF02020961, MR 0221974, S2CID 119485995.
  • Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", Les Comptes rendus de l'Académie des sciences, 254: 1370–1371, MR 0172275.
  • Gilmore, P. C.; Hoffman, A. J. (1964), "A characterization of comparability graphs and of interval graphs", Canadian Journal of Mathematics, 16: 539–548, doi:10.4153/CJM-1964-055-5, MR 0175811.
  • Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
  • Golumbic, M.; Rotem, D.; Urrutia, J. (1983), "Comparability graphs and intersection graphs", Discrete Mathematics, 43 (1): 37–46, doi:10.1016/0012-365X(83)90019-5.
  • Jung, H. A. (1978), "On a class of posets and the corresponding comparability graphs", Journal of Combinatorial Theory, Series B, 24 (2): 125–133, doi:10.1016/0095-8956(78)90013-8, MR 0491356.
  • Lovász, L. (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.
  • Maffray, Frédéric (2003), "On the coloration of perfect graphs", in Reed, Bruce A.; Sales, Cláudia L. (eds.), Recent Advances in Algorithms and Combinatorics, CMS Books in Mathematics, vol. 11, Springer-Verlag, pp. 65–84, doi:10.1007/0-387-22444-0_3.
  • McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  • Seymour, Paul (2006), "How the proof of the strong perfect graph conjecture was found" (PDF), Gazette des Mathématiciens (109): 69–83, MR 2245898.
  • Trotter, William T. (1992), Combinatorics and Partially Ordered Sets — Dimension Theory, Johns Hopkins University Press.
  • Urrutia, Jorge (1989), "Partial orders and Euclidean geometry", in Rival, I. (ed.), Algorithms and Order, Kluwer Academic Publishers, pp. 327–436, doi:10.1007/978-94-009-2639-4.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=तुलनीयता_ग्राफ&oldid=216118’