View source for स्ट्रिंग ग्राफ

{{short description|Intersection graph for curves in the plane}}

[[ग्राफ सिद्धांत]] में, एक स्ट्रिंग ग्राफ [[समतल वक्र]] का प्रतिच्छेदन ग्राफ है; प्रत्येक वक्र को "स्ट्रिंग" कहा जाता है। दिया ग्राफ {{mvar|G}} (असतत गणित), {{mvar|G}} एक स्ट्रिंग ग्राफ़ है [[अगर और केवल अगर|यदि और केवल तभी जब]] वक्र, या स्ट्रिंग्स का एक समुच्चय उपस्थित है, जैसे कि ग्राफ़ में प्रत्येक वक्र के लिए त्रिभुज का शीर्ष (ग्राफ़ थ्योरी) है और वक्रों की प्रत्येक प्रतिच्छेदन जोड़ी के लिए एक किनारा {{mvar|G}} के लिए समरूपी है।

== पृष्ठभूमि ==
{{harvs|txt|last=बेंजर|first=सीमोर|authorlink=Seymour Benzer|year=1959}} ने स्ट्रिंग ग्राफ़ के समान एक अवधारणा का वर्णन किया, जैसा कि वे आनुवंशिक संरचनाओं पर लागू होते हैं। उस संदर्भ में, उन्होंने रेखा पर अन्तरालों को प्रतिच्छेद करने के विशिष्ट कार्य को भी प्रस्तुत किया, अर्थात् अब [[अंतराल ग्राफ|अंतराल ग्राफ़ों]] का शास्त्रीय परिवार। बाद में, {{harvtxt|सिंडेन|1966}} ने इसी विचार को विद्युत जालक्रम और मुद्रित परिपथ के लिए निर्दिष्ट किया। स्ट्रिंग ग्राफ़ का गणितीय अध्ययन पेपर {{harvtxt|एर्लिच|इवन|टारजन|1976}} और सिंडेन और [[रोनाल्ड ग्राहम]] के बीच सहयोग के माध्यम से शुरू हुआ, जहां 1976 में साहचर्य पर 5वें हंगेरियन कॉलोक्वियम में स्ट्रिंग ग्राफ के लक्षण वर्णन को अंततः एक खुले प्रश्न के रूप में प्रस्तुत किया गया।<ref>{{harvtxt|Graham|1976}}.</ref> तथापि, स्ट्रिंग ग्राफ़ की मान्यता अंततः एनपी-पूर्ण प्रमाणित हुई थी, जिसका अर्थ है कि कोई सरल विवरण उपस्थित होने की संभावना नहीं है।<ref>{{harvtxt|Kratochvil|1991b}} showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. After intermediate results by {{harvtxt|Schaefer|Štefankovič|2001}} and {{harvtxt|Pach|Tóth|2002}}, {{harvtxt|Schaefer|Sedgwick|Štefankovič|2003}} completed the proof that the problem is NP-complete.</ref>


== संबंधित ग्राफ वर्ग ==
[[File:Planar string graph.svg|thumb|300px|स्ट्रिंग ग्राफ के रूप में [[ प्लेनर ग्राफ |समतली आलेख]] का प्रतिनिधित्व।]]प्रत्येक समतली आलेख एक स्ट्रिंग ग्राफ है:<ref name="ss-s">{{harvtxt|Schaefer|Štefankovič|2001}} credit this observation to {{harvtxt|Sinden|1966}}.</ref> जैसा कि चित्र में दिखाया गया है, शीर्ष के चारों ओर और प्रत्येक समीपस्थ किनारे के मध्य बिंदु के चारों ओर घूमने वाले प्रत्येक शीर्ष के लिए स्ट्रिंग खींचकर समतल-सन्निहित ग्राफ का एक स्ट्रिंग ग्राफ प्रतिनिधित्व कर सकता है। ग्राफ के किसी भी किनारे uv के लिए, u और v के लिए स्ट्रिंग uv के मध्य बिंदु के पास एक दूसरे को दो बार उत्तीर्ण करते हैं, और कोई अन्य  प्रसंकरण नहीं होती है, इसलिए स्ट्रिंग के जोड़े जो उत्तीर्ण करते हैं, मूल समतली आलेख के निकटवर्ती जोड़े का प्रतिनिधित्व करते हैं। वैकल्पिक रूप से, [[सर्कल पैकिंग प्रमेय]] द्वारा, किसी भी समतली आलेख को वृत्त के संग्रह के रूप में दिखाया जा सकता है, जिनमें से कोई भी दो उत्तीर्ण हो सकता है यदि और केवल तभी जब समरूपी किनारे समीपस्थ हैं; ये वृत्त (प्रारंभिक और अंतिम बिंदु के साथ उन्हें खुले वक्रों में बदलने के लिए चुने गए) दिए गए समतली आलेख का स्ट्रिंग ग्राफ प्रतिनिधित्व प्रदान करते हैं। {{harvtxt|चालोपिन|गोंकाल्वेस|ओकेम|2007}} ने प्रमाणित किया कि प्रत्येक समतलीय ग्राफ में एक स्ट्रिंग प्रतिनिधित्व होता है जिसमें ऊपर वर्णित प्रतिनिधित्वों के विपरीत स्ट्रिंग्स की प्रत्येक जोड़ी में अधिकतम एक प्रसंकरण बिन्दु होता है। स्कीनरमैन का अनुमान, जो अब सिद्ध हो चुका है, अब और भी सबल कथन है कि प्रत्येक समतली आलेख को सीधी रेखा खंडों के प्रतिच्छेदन ग्राफ द्वारा दिखाया जा सकता है, जो स्ट्रिंग्स का बहुत ही विशेष व्यवहार है।[[File:Subdivided K5.svg|thumb|180px|''K''<sub>5</sub> का उपखंड जो स्ट्रिंग ग्राफ नहीं है।]]यदि किसी दिए गए ग्राफ़ G का प्रत्येक किनारा उपखंड (ग्राफ़ सिद्धांत) है, तो परिणामी ग्राफ़ एक स्ट्रिंग ग्राफ़ है यदि और केवल तभी जब G समतलीय है। विशेष रूप से, पूर्ण ग्राफ K<sub>5</sub> का उपखंड उदाहरण में दिखाया गया स्ट्रिंग ग्राफ नहीं है, क्योंकि K<sub>5</sub> समतलीय नहीं है।<ref name="ss-s"/>

प्रत्येक वृत्त ग्राफ, रेखा खंडों (एक वृत्त की जीवा) के प्रतिच्छेदन ग्राफ़ के रूप में, एक स्ट्रिंग ग्राफ़ भी है। प्रत्येक [[कॉर्डल ग्राफ|पृष्ठरज्जु ग्राफ]] को स्ट्रिंग ग्राफ़ के रूप में दिखाया जा सकता है: पृष्ठरज्जु ग्राफ़ पेड़ों के उपट्रीज़ के प्रतिच्छेदन ग्राफ़ हैं, और एक पृष्ठरज्जु ग्राफ़ का स्ट्रिंग प्रतिनिधित्व बना सकता है जो संबंधित पेड़ के समतलीय अंतःस्थापन का निर्माण करता है और प्रत्येक सबट्री को एक स्ट्रिंग द्वारा प्रतिस्थापित करता है जो सबट्री के किनारों के आसपास अवशेष करता है।

प्रत्येक [[तुलनात्मक ग्राफ]] का [[पूरक ग्राफ]] भी एक स्ट्रिंग ग्राफ होता है।<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2010}}.</ref>
== अन्य परिणाम ==
{{harvtxt|एर्लिच|ईवन|टारजन|1976}} ने एन.पी-हार्ड होने के लिए स्ट्रिंग ग्राफ़ की वर्णिक अंक की गणना करना दिखाया। {{harvtxt|क्रैटोचविल|1991a}} ने पाया कि स्ट्रिंग ग्राफ़ प्रेरित उपसारणिक संवृत वर्ग बनाते हैं, लेकिन ग्राफ़ के उपसारणिक संवृत वर्ग नहीं।

प्रत्येक m-किनारों वाली स्ट्रिंग ग्राफ को दो उपसमुच्चयों में विभाजित किया जा सकता है,  O(m)<sup>3/4</sup>log<sup>1/2</sup>m) शीर्षों को हटाकर, जिनमें से प्रत्येक पूरे ग्राफ़ के स्वरूप का एक स्थिर अंश होता है। यह इस प्रकार है कि बिक्लिक-मुक्त ग्राफ, स्ट्रिंग ग्राफ़ जिसमें कुछ स्थिरांक t के लिए कोई उप ग्राफ K<sub>''t'',''t''</sub> नहीं होते है, ''O''(''n'') किनारे होते हैं और अधिक दृढ़ता से बहुपद विस्स्ट्रिंग होता है।<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|2015}}.</ref>


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


== संदर्भ ==
*{{citation
 | first = S. | last = Benzer | authorlink = Seymour Benzer
 | title = On the topology of the genetic fine structure
 | journal = [[Proceedings of the National Academy of Sciences of the United States of America]]
 | volume = 45
 | year = 1959
 | issue = 11
 | pages = 1607–1620
 | doi = 10.1073/pnas.45.11.1607
 | bibcode=1959PNAS...45.1607B
 | pmid=16590553
 | pmc=222769| doi-access = free }}.
*{{citation
 | last1 = Chalopin | first1 = J. | last2 = Gonçalves | first2 = D. | last3 = Ochem | first3 = P.
 | contribution = Planar graphs are in 1-STRING
 | title = Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms
 | publisher = ACM and SIAM
 | year = 2007
 | pages = 609–617}}.
*{{citation
 | last1 = Dvořák | first1 = Zdeněk | author1-link = Zdeněk Dvořák
 | last2 = Norin | first2 = Sergey
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | volume = 30
 | issue = 2
 | pages = 1095–1101 
 | arxiv = 1504.04821
 | title = Strongly sublinear separators and polynomial expansion
 | year = 2016 | bibcode = 2015arXiv150404821D
 | doi=10.1137/15M1017569}}.
*{{citation
 | first1 = G. | last1 = Ehrlich | first2 = S. | last2 = Even | first3 = R. E. | last3 = Tarjan | author3-link = Robert Tarjan
 | title = Intersection graphs of curves in the plane
 | journal = [[Journal of Combinatorial Theory]]
 | volume = 21
 | issue = 1
 | pages = 8–20
 | year = 1976
 | doi = 10.1016/0095-8956(76)90022-8| doi-access = free}}.
*{{citation
 | last1 = Fox | first1 = Jacob | author1-link = Jacob Fox
 | last2 = Pach | first2 = János | author2-link = János Pach
 | doi = 10.1017/s0963548309990459
 | issue = 3
 | journal = [[Combinatorics, Probability and Computing]]
 | page = 371
 | title = A separator theorem for string graphs and its applications
 | volume = 19
 | year = 2010| s2cid = 5705145 }}.
*{{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
 | first = R. L. | last = Graham | authorlink = Ronald Graham
 | contribution = Problem 1
 | title = Open Problems at 5th Hungarian Colloquium on Combinatorics
 | year = 1976}}.
*{{citation
 | first = Jan | last = Kratochvil | authorlink = Jan Kratochvíl
 | title = String Graphs. I. The number of critical nonstring graphs is infinite
 | journal = [[Journal of Combinatorial Theory]], Series B
 | year = 1991a
 | volume = 52
 | pages = 53–66
 | doi = 10.1016/0095-8956(91)90090-7
 | issue = 1| doi-access = free
 }}.
*{{citation
 | first = Jan | last = Kratochvil | authorlink = Jan Kratochvíl
 | title = String Graphs. II. Recognizing string graphs is NP-Hard
 | journal = [[Journal of Combinatorial Theory]], Series B
 | year = 1991b
 | volume = 52
 | pages = 67–78
 | doi = 10.1016/0095-8956(91)90091-W
 | issue = 1| doi-access = free
 }}.
*{{citation
 | first = L. | last = Lovász | authorlink = 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
 | journal = [[Discrete & Computational Geometry]]
 | title = Recognizing string graphs is decidable
 | first1 = János | last1 = Pach | author1-link = János Pach | first2 = Geza | last2 = Tóth
 | volume = 28
 | issue = 4
 | pages = 593–606
 | year = 2002
 | doi = 10.1007/s00454-002-2891-4| doi-access = free
 }}.
*{{citation
 | first1 = Marcus | last1 = Schaefer | first2 = Daniel | last2 = Štefankovič
 | title = Decidability of string graphs
 | journal = [[Symposium on Theory of Computing|Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001)]]
 | year = 2001
 | pages = 241–246}}.
*{{citation
 | first1 = Marcus | last1 = Schaefer | first2 = Eric | last2 = Sedgwick | first3 = Daniel | last3 = Štefankovič
 | title = Recognizing string graphs in NP
 | journal = Journal of Computer and System Sciences
 | volume = 67
 | issue = 2
 | pages = 365–380
 | year = 2003
 | doi = 10.1016/S0022-0000(03)00045-X | doi-access = free
 }}.
*{{citation
 | journal = Bell System Technical Journal
 | title = Topology of thin film RC-circuits
 | first = F. W. | last = Sinden
 | year = 1966
 | volume = 45
 | issue = 9
 | pages = 1639–1662
 | doi=10.1002/j.1538-7305.1966.tb01713.x}}.
[[Category: सामयिक ग्राफ सिद्धांत]] [[Category: रेखांकन के चौराहे वर्ग]] 



[[Category: Machine Translated Page]]
[[Category:Created On 28/02/2023]]
[[Category:Vigyan Ready]]