View source for तुलनीयता ग्राफ

{{Short description|Graph linking pairs of comparable elements in a partial order}}
ग्राफ़ सिद्धांत में, '''तुलनीयता ग्राफ़''' एक [[अप्रत्यक्ष ग्राफ]] है जो आंशिक क्रम में एक दूसरे से तुलनीय तत्वों के जोड़े को जोड़ता है। '''तुलनीयता ग्राफ़''' को '''संक्रमणीय रूप से उन्मुख ग्राफ़,''' '''आंशिक रूप से क्रमबद्ध ग्राफ़,''' '''रोकथाम ग्राफ़''' और '''भाजक ग्राफ़'''{{sfnp|Chartrand|Muntean|Saenpholphat|Zhang|2001}} भी कहा जाता है।<ref>{{harvtxt|Golumbic|1980}}, p. 105; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 94.</ref> 

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

==परिभाषाएँ और लक्षण वर्णन==
[[File:Poset et graphe de comparabilité.svg|thumb|300px|एक पोसेट का हैस आरेख (बाएं) और उसका तुलनीयता ग्राफ (दाएं)]]
[[Image:Forbidden interval subgraph.svg|thumb|तुलनीयता ग्राफ़ के निषिद्ध प्रेरित उपग्राफों में से एक। सामान्यीकृत चक्र {{mvar|a–b–d–f–d–c–e–c–b–a}}इस ग्राफ़ में विषम लंबाई (नौ) है किन्तु कोई त्रिकोणीय जीवा नहीं है।]]किसी भी [[सख्त आंशिक आदेश|सख्त आंशिक रूप से]] आदेशित के लिए, (एस, <) का '''तुलनीयता ग्राफ''' ग्राफ (एस, ⊥) है जिसके शीर्ष {{mvar|S}} तत्व हैं  और किनारे वे जोड़े हैं {{math|{''u'', ''v''} }}हैं ऐसे तत्वों का {{math|''u'' < ''v''}}. अर्थात्, आंशिक रूप से ऑर्डर किए गए सेट के लिए, निर्देशित एसाइक्लिक ग्राफ़ लें, [[ सकर्मक समापन ]] लागू करें, और अभिविन्यास हटा दें।

समान रूप से, एक तुलनीयता ग्राफ़ एक ऐसा ग्राफ़ है जिसमें एक '''संक्रमणीय अभिविन्यास'''  होता है,<ref>{{harvtxt|Ghouila-Houri|1962}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 1.4.1, p. 12. Although the orientations coming from partial orders are [[directed acyclic graph|acyclic]], it is not necessary to include acyclicity as a condition of this characterization.</ref> ग्राफ़ के किनारों पर दिशाओं का एक असाइनमेंट (अर्थात ग्राफ़ का एक अभिविन्यास ) जैसे कि परिणामी [[निर्देशित ग्राफ]] का [[आसन्न संबंध]] [[सकर्मक संबंध]] है: जब भी निर्देशित किनारे उपस्तिथ होते हैं {{math|(''x'',''y'')}} और {{math|(''y'',''z'')}} उपस्तिथ हैं‚ वहाँ एक किनारा {{math|(''x'',''z'')}} उपस्तिथ होना चाहिए।

कोई किसी भी परिमित आंशिक क्रम को समुच्चयों के एक परिवार के रूप में प्रस्तुत कर सकता है, जैसे कि {{math|''x'' < ''y''}} आंशिक क्रम में जब भी {{mvar|x}} के अनुरूप समुच्चय‚ {{mvar|y}} के संगत समुच्चय का उपसमुच्चय है। इस तरह, तुलनीयता ग्राफ़ को सेट परिवारों के रोकथाम ग्राफ़ के बराबर दिखाया जा सकता है; अर्थात, परिवार में प्रत्येक सेट के लिए एक शीर्ष के साथ एक ग्राफ और दो सेटों के बीच एक किनारा जब भी एक दूसरे का उपसमुच्चय होता है।<ref>{{harvtxt|Urrutia|1989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, section 6.3, pp. 94–96.</ref>

वैकल्पिक रूप से, कोई [[पूर्णांक|पूर्णांकों]] के परिवार द्वारा आंशिक क्रम का प्रतिनिधित्व कर सकता है, जैसे कि {{math|''x'' < ''y''}} जब भी x के अनुरूप पूर्णांक, y के अनुरूप पूर्णांक का [[भाजक|विभाजक]] होता है। इस प्रकार निर्माण के कारण, तुलनीयता ग्राफ़ को विभाजक ग्राफ़ भी कहा जाता है।{{sfnp|Chartrand|Muntean|Saenpholphat|Zhang|2001}}

तुलनीयता ग्राफ़ को ऐसे ग्राफ़ के रूप में वर्णित किया जा सकता है, जो विषम लंबाई के प्रत्येक सामान्यीकृत चक्र (नीचे देखें) के लिए, चक्र में दूरी दो पर स्थित दो शीर्षों को जोड़ने वाला एक किनारा (x,y) पा सकता है। इस प्रकार ऐसे किनारे को त्रिकोणीय राग कहते हैं। इस संदर्भ में, एक सामान्यीकृत चक्र को ग्राफ़ सिद्धांत वॉक की शब्दावली के रूप में परिभाषित किया गया है जो प्रत्येक दिशा में ग्राफ़ के प्रत्येक किनारे का अधिकतम एक बार उपयोग करता है।<ref>{{harvtxt|Ghouila-Houri|1962}} and {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.1.1, p. 91.</ref> इस प्रकार तुलनीयता ग्राफ़ को निषिद्ध प्रेरित उपग्राफ़ों की सूची द्वारा भी चित्रित किया जा सकता है।<ref>{{harvtxt|Gallai|1967}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91 and p. 112.</ref>
==अन्य ग्राफ़ परिवारों से संबंध==
प्रत्येक पूर्ण ग्राफ़ एक तुलनीयता ग्राफ़ है, कुल क्रम का तुलनीयता ग्राफ़ है, प्रत्येक पूर्ण ग्राफ़ के सभी चक्रीय अभिविन्यास  सकर्मक होते हैं। प्रत्येक [[द्विदलीय ग्राफ]] एक तुलनीयता ग्राफ भी है। इस प्रकार द्विदलीय ग्राफ के किनारों को द्विविभाजन के एक तरफ से दूसरी ओर उन्मुख करने से ऊंचाई दो के आंशिक क्रम के अनुरूप एक संक्रमणीय अभिविन्यास  प्राप्त होता है। इस प्रकार जैसा {{harvtxt|सेमुर|2006}} देखता है, प्रत्येक तुलनीयता ग्राफ जो न तो पूर्ण है और न ही द्विदलीय है, उसमें [[तिरछा विभाजन]] होता है।

किसी भी [[अंतराल ग्राफ]] का [[पूरक (ग्राफ सिद्धांत)]] एक तुलनीयता ग्राफ है। इस प्रकार तुलनीयता संबंध को [[अंतराल क्रम]] कहा जाता है। अंतराल ग्राफ़ वास्तव में वे ग्राफ़ होते हैं जो कॉर्डल होते हैं और जिनमें तुलनीयता ग्राफ़ पूरक होते हैं।<ref>Transitive orientability of interval graph complements was proven by {{harvtxt|Ghouila-Houri|1962}}; the characterization of interval graphs is due to {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Golumbic|1980}}, prop. 1.3, pp. 15–16.</ref>

[[क्रमपरिवर्तन ग्राफ]] अंतरालों के एक सेट पर एक रोकथाम ग्राफ़ है।<ref>{{harvtxt|Dushnik|Miller|1941}}. {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.3.1, p. 95.</ref> इसलिए, क्रमपरिवर्तन ग्राफ़ तुलनीयता ग्राफ़ का एक और उपवर्ग हैं।

तुच्छ रूप से परिपूर्ण ग्राफ़ जड़ वाले पेड़ों की तुलनीयता के ग्राफ़ हैं।<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.1, p. 99.</ref>

[[कोग्राफ|कोग्राफ़]] को श्रृंखला-समानांतर आंशिक आदेशों के तुलनीयता ग्राफ़ के रूप में चित्रित किया जा सकता है; इस प्रकार, कोग्राफ़ भी तुलनीयता ग्राफ़ हैं।<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, corollary 6.4.1, p. 96; {{harvtxt|Jung|1978}}.</ref>

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

प्रत्येक तुलनीयता ग्राफ़ पूर्ण ग्राफ़ है। तुलनीयता ग्राफ़ की पूर्णता मिर्स्की की प्रमेय है और उनके पूरकों की पूर्णता दिलवर्थ की प्रमेय है; इन तथ्यों को, सही ग्राफ़ प्रमेय के साथ मिलकर, दिलवर्थ के प्रमेय को मिर्स्की के प्रमेय से या इसके विपरीत सिद्ध करने के लिए उपयोग किया जा सकता है।<ref>{{harvtxt|Golumbic|1980}}, theorems 5.34 and 5.35, p. 133.</ref> इस प्रकार अधिक विशेष रूप से, तुलनीयता ग्राफ़ पूरी तरह से क्रमबद्ध ग्राफ़ हैं, सही ग्राफ़ का एक उपवर्ग: ग्राफ़ के एक संक्रमणीय अभिविन्यास  के [[टोपोलॉजिकल ऑर्डरिंग]] के लिए एक [[लालची रंग]] एल्गोरिदम उन्हें इष्टतम रूप से रंग देगा।<ref>{{harvtxt|Maffray|2003}}.</ref>

प्रत्येक तुलनीयता ग्राफ का [[पूरक ग्राफ]] एक [[ स्ट्रिंग ग्राफ़ | स्ट्रिंग ग्राफ़]] है।<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2012}}.</ref>
==एल्गोरिदम==
किसी ग्राफ़ का सकर्मक अभिविन्यास, यदि वह उपस्तिथ है, रैखिक समय में पाया जा सकता है।<ref>{{harvtxt|McConnell|Spinrad|1997}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91.</ref> इस प्रकार चूँकि, ऐसा करने के लिए एल्गोरिदम किसी भी ग्राफ़ के किनारों पर अभिविन्यास निर्दिष्ट करेगा, इसलिए यह परीक्षण करने के कार्य को पूरा करने के लिए कि क्या ग्राफ़ एक तुलनीयता ग्राफ़ है, किसी को यह परीक्षण करना होगा कि क्या परिणामी अभिविन्यास सकर्मक है, एक समस्या जो मैट्रिक्स गुणन की जटिलता के बराबर है।

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

==टिप्पणियाँ==
{{reflist|30em}}

संदर्भ
{{refbegin|30em}}
*{{citation | last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Le | first2 = Van Bang | last3 = Spinrad | first3 = Jeremy | title = Graph Classes: A Survey | publisher = SIAM Monographs on Discrete Mathematics and Applications | year = 1999 | isbn = 0-89871-432-X | url-access = registration | url = https://archive.org/details/graphclassessurv0000bran }}.
*{{citation
 | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand
 | last2 = Muntean | first2 = Raluca
 | last3 = Saenpholphat | first3 = Varaporn
 | last4 = Zhang | first4 = Ping | author4-link = Ping Zhang (graph theorist)
 | department = Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001)
 | journal = Congressus Numerantium
 | mr = 1887439
 | pages = 189–200
 | title = Which graphs are divisor graphs?
 | volume = 151
 | year = 2001}}
*{{citation
 | last1 = Dushnik | first1 = Ben | last2 = Miller | first2 = E. W.
 | title = Partially ordered sets
 | journal = American Journal of Mathematics
 | volume = 63
 | year = 1941
 | pages = 600–610
 | mr = 0004862
 | doi = 10.2307/2371374
 | issue = 3
 | publisher = The Johns Hopkins University Press
 | jstor = 2371374| hdl = 10338.dmlcz/100377
 | hdl-access = free
 }}.
*{{citation
 | first1 = Jacob | last1 = Fox | first2 = Jànos | last2 = Pach | author2-link = János Pach
 | title = String graphs and incomparability graphs
 | journal = [[Advances in Mathematics]]
 | volume = 230
 | issue = 3
 | year = 2012
 | doi = 10.1016/j.aim.2012.03.011
 | doi-access = free
 | url = http://www.renyi.hu/~pach/publications/stringpartial071709.pdf
 | pages = 1381–1401
 }}.
*{{citation
 | last = Gallai | first = Tibor
 | author-link=Tibor Gallai
 | title = Transitiv orientierbare Graphen
 | journal = Acta Math. Acad. Sci. Hung.
 | volume = 18
 | year = 1967
 | issue = 1–2
 | pages = 25–66
 | mr = 0221974
 | doi = 10.1007/BF02020961| s2cid = 119485995
 }}.
*{{citation
 | last = Ghouila-Houri | first = Alain
 | title = 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
 | journal = [[Les Comptes rendus de l'Académie des sciences]]
 | volume = 254
 | year = 1962
 | pages = 1370–1371
 | mr =0172275}}.
*{{citation
 | last1 = Gilmore | first1 = P. C. | last2 = Hoffman | first2 = A. J.
 | title = A characterization of comparability graphs and of interval graphs
 | journal = Canadian Journal of Mathematics
 | volume = 16
 | year = 1964
 | pages = 539–548
 | mr = 0175811
 | doi = 10.4153/CJM-1964-055-5| doi-access = free
 }}.
*{{citation
 | last = Golumbic | first = Martin Charles | author-link = Martin Charles Golumbic
 | title = Algorithmic Graph Theory and Perfect Graphs
 | publisher = Academic Press
 | year = 1980
 | isbn = 0-12-289260-7}}.
*{{citation
 | first1 = M. | last1 = Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia
 | title = Comparability graphs and intersection graphs
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 43
 | year = 1983
 | pages = 37–46
 | issue = 1
 | doi = 10.1016/0012-365X(83)90019-5| doi-access = free}}.
*{{citation
 | last = Jung | first = H. A.
 | title = On a class of posets and the corresponding comparability graphs
 | journal = Journal of Combinatorial Theory, Series B
 | volume = 24
 | year = 1978
 | issue = 2
 | pages = 125–133
 | mr = 0491356
 | doi = 10.1016/0095-8956(78)90013-8| doi-access = free
 }}.
*{{citation
 | first = L. | last = Lovász | author-link = László Lovász
 | contribution = Perfect graphs
 | title = Selected Topics in Graph Theory
 | volume = 2
 | publisher = Academic Press
 | location = London
 | year = 1983
 | pages = 55–87}}.
*{{citation
 | last = Maffray | first = Frédéric
 | contribution = On the coloration of perfect graphs
 | doi = 10.1007/0-387-22444-0_3
 | editor1-last = Reed | editor1-first = Bruce A. | editor1-link = Bruce Reed (mathematician)
 | editor2-last = Sales | editor2-first = Cláudia L.
 | pages = 65–84
 | publisher = Springer-Verlag
 | series = CMS Books in Mathematics
 | title = Recent Advances in Algorithms and Combinatorics
 | volume = 11
 | year = 2003}}.
*{{citation
 | last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J.
 | contribution = Linear-time transitive orientation
 | title = 8th ACM-SIAM Symposium on Discrete Algorithms
 | year = 1997
 | pages = 19–25}}.
*{{citation
 | last = Seymour | first = Paul | author-link = Paul Seymour (mathematician)
 | issue = 109
 | journal = Gazette des Mathématiciens
 | mr = 2245898
 | pages = 69–83
 | title = How the proof of the strong perfect graph conjecture was found
 | url = http://users.encs.concordia.ca/~chvatal/perfect/pds.pdf
 | year = 2006}}.
*{{citation
 | last = Trotter | first = William T. | author-link = William T. Trotter
 | title = Combinatorics and Partially Ordered Sets — Dimension Theory
 | publisher = Johns Hopkins University Press
 | year = 1992}}.
*{{citation
 | last = Urrutia | first = Jorge | author-link = Jorge Urrutia Galicia
 | chapter= Partial orders and Euclidean geometry
 | title = Algorithms and Order
 | editor = [[Ivan Rival|Rival, I.]]
 | year = 1989
 | publisher = Kluwer Academic Publishers
 | pages = 327–436
 | doi=10.1007/978-94-009-2639-4}}.
{{refend}}

{{Order theory}}

[[Category:Collapse templates]]
[[Category:Created On 01/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:आदेश सिद्धांत]]
[[Category:उत्तम रेखांकन]]
[[Category:ग्राफ़ परिवार]]