स्ट्रिंग ग्राफ: Difference between revisions
(Created page with "{{short description|Intersection graph for curves in the plane}} ग्राफ सिद्धांत में, एक स्ट्रिंग ग्राफ स...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Intersection graph for curves in the plane}} | {{short description|Intersection graph for curves in the plane}} | ||
[[ग्राफ सिद्धांत]] में, एक स्ट्रिंग ग्राफ [[समतल वक्र]] का प्रतिच्छेदन ग्राफ है; प्रत्येक वक्र को | [[ग्राफ सिद्धांत]] में, एक स्ट्रिंग ग्राफ [[समतल वक्र]] का प्रतिच्छेदन ग्राफ है; प्रत्येक वक्र को "स्ट्रिंग" कहा जाता है। एक दिया ग्राफ {{mvar|G}} (असतत गणित), {{mvar|G}} एक स्ट्रिंग ग्राफ़ है [[अगर और केवल अगर]] वक्र, या स्ट्रिंग्स का एक समुच्चय उपस्थित है, जैसे कि ग्राफ़ में प्रत्येक वक्र के लिए त्रिभुज का शीर्ष (ग्राफ़ थ्योरी) है और वक्रों की प्रत्येक प्रतिच्छेदन जोड़ी के लिए एक किनारा {{mvar|G}} के लिए समरूपी है। | ||
== पृष्ठभूमि == | == पृष्ठभूमि == | ||
{{harvs|txt|last=Benzer|first=Seymour|authorlink=Seymour Benzer|year=1959}} ने स्ट्रिंग ग्राफ़ के समान एक अवधारणा का वर्णन किया, जैसा कि वे आनुवंशिक संरचनाओं पर लागू होते हैं। उस संदर्भ में, उन्होंने एक रेखा पर अन्तरालों को प्रतिच्छेद करने के विशिष्ट मामले को भी प्रस्तुत किया, अर्थात् [[अंतराल ग्राफ]]़ों का अब शास्त्रीय परिवार। बाद में, {{harvtxt|Sinden|1966}} विद्युत नेटवर्क और मुद्रित सर्किट के लिए समान विचार निर्दिष्ट किया। स्ट्रिंग ग्राफ़ का गणितीय अध्ययन पेपर से शुरू हुआ {{harvtxt|Ehrlich|Even|Tarjan|1976}} और | {{harvs|txt|last=Benzer|first=Seymour|authorlink=Seymour Benzer|year=1959}} ने स्ट्रिंग ग्राफ़ के समान एक अवधारणा का वर्णन किया, जैसा कि वे आनुवंशिक संरचनाओं पर लागू होते हैं। उस संदर्भ में, उन्होंने एक रेखा पर अन्तरालों को प्रतिच्छेद करने के विशिष्ट मामले को भी प्रस्तुत किया, अर्थात् [[अंतराल ग्राफ]]़ों का अब शास्त्रीय परिवार। बाद में, {{harvtxt|Sinden|1966}} विद्युत नेटवर्क और मुद्रित सर्किट के लिए समान विचार निर्दिष्ट किया। स्ट्रिंग ग्राफ़ का गणितीय अध्ययन पेपर से शुरू हुआ {{harvtxt|Ehrlich|Even|Tarjan|1976}} और | ||
सिंडेन और [[रोनाल्ड ग्राहम]] के बीच एक सहयोग के माध्यम से, जहां 1976 में कॉम्बिनेटोरिक्स पर 5वें हंगेरियन कॉलोक्वियम में स्ट्रिंग ग्राफ के लक्षण वर्णन को अंततः एक खुले प्रश्न के रूप में प्रस्तुत किया गया।<ref>{{harvtxt|Graham|1976}}.</ref> हालांकि, स्ट्रिंग ग्राफ़ की मान्यता अंततः एनपी-पूर्ण साबित हुई थी, जिसका अर्थ है कि कोई सरल लक्षण वर्णन | सिंडेन और [[रोनाल्ड ग्राहम]] के बीच एक सहयोग के माध्यम से, जहां 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| | [[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|Chalopin|Gonçalves|Ochem|2007}} ने साबित किया कि प्रत्येक समतली आलेख़ में एक स्ट्रिंग प्रस्तुति होती है जिसमें ऊपर वर्णित प्रस्तुतियों के विपरीत स्ट्रिंग्स की प्रत्येक जोड़ी में अधिकतम एक क्रॉसिंग पॉइंट होता है। | ||
स्कीनरमैन का अनुमान, जो अब सिद्ध हो चुका है, और भी मजबूत कथन है कि प्रत्येक | स्कीनरमैन का अनुमान, जो अब सिद्ध हो चुका है, और भी मजबूत कथन है कि प्रत्येक समतली आलेख को सीधी रेखा खंडों के प्रतिच्छेदन ग्राफ द्वारा दर्शाया जा सकता है, जो स्ट्रिंग्स का एक बहुत ही विशेष मामला है। | ||
[[File:Subdivided K5.svg|thumb|180px|K | [[File:Subdivided K5.svg|thumb|180px|''K''<sub>5</sub> का एक उपखंड जो स्ट्रिंग ग्राफ नहीं है।]]यदि किसी दिए गए ग्राफ़ G का प्रत्येक किनारा उपखंड (ग्राफ़ सिद्धांत) है, तो परिणामी ग्राफ़ एक स्ट्रिंग ग्राफ़ है यदि और केवल यदि G समतलीय है। विशेष रूप से, पूर्ण ग्राफ K का उपखंड<sub>5</sub> उदाहरण में दिखाया गया एक स्ट्रिंग ग्राफ नहीं है, क्योंकि K<sub>5</sub> समतलीय नहीं है।<ref name="ss-s"/> | ||
प्रत्येक वृत्त ग्राफ, रेखा खंडों (एक वृत्त की जीवा) के प्रतिच्छेदन ग्राफ़ के रूप में, एक स्ट्रिंग ग्राफ़ भी है। प्रत्येक [[कॉर्डल ग्राफ]]़ को एक स्ट्रिंग ग्राफ़ के रूप में दर्शाया जा सकता है: कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के प्रतिच्छेदन ग्राफ़ हैं, और एक कॉर्डल ग्राफ़ का एक स्ट्रिंग प्रतिनिधित्व बना सकता है जो संबंधित पेड़ के एक प्लानर एम्बेडिंग का निर्माण करता है और प्रत्येक सबट्री को एक स्ट्रिंग द्वारा प्रतिस्थापित करता है जो ट्रेस करता है सबट्री के किनारों के आसपास। | प्रत्येक वृत्त ग्राफ, रेखा खंडों (एक वृत्त की जीवा) के प्रतिच्छेदन ग्राफ़ के रूप में, एक स्ट्रिंग ग्राफ़ भी है। प्रत्येक [[कॉर्डल ग्राफ]]़ को एक स्ट्रिंग ग्राफ़ के रूप में दर्शाया जा सकता है: कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के प्रतिच्छेदन ग्राफ़ हैं, और एक कॉर्डल ग्राफ़ का एक स्ट्रिंग प्रतिनिधित्व बना सकता है जो संबंधित पेड़ के एक प्लानर एम्बेडिंग का निर्माण करता है और प्रत्येक सबट्री को एक स्ट्रिंग द्वारा प्रतिस्थापित करता है जो ट्रेस करता है सबट्री के किनारों के आसपास। | ||
| Line 20: | Line 20: | ||
== अन्य परिणाम == | == अन्य परिणाम == | ||
{{harvtxt| | {{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> | ||
Revision as of 09:01, 11 March 2023
ग्राफ सिद्धांत में, एक स्ट्रिंग ग्राफ समतल वक्र का प्रतिच्छेदन ग्राफ है; प्रत्येक वक्र को "स्ट्रिंग" कहा जाता है। एक दिया ग्राफ G (असतत गणित), G एक स्ट्रिंग ग्राफ़ है अगर और केवल अगर वक्र, या स्ट्रिंग्स का एक समुच्चय उपस्थित है, जैसे कि ग्राफ़ में प्रत्येक वक्र के लिए त्रिभुज का शीर्ष (ग्राफ़ थ्योरी) है और वक्रों की प्रत्येक प्रतिच्छेदन जोड़ी के लिए एक किनारा G के लिए समरूपी है।
पृष्ठभूमि
Seymour Benzer (1959) ने स्ट्रिंग ग्राफ़ के समान एक अवधारणा का वर्णन किया, जैसा कि वे आनुवंशिक संरचनाओं पर लागू होते हैं। उस संदर्भ में, उन्होंने एक रेखा पर अन्तरालों को प्रतिच्छेद करने के विशिष्ट मामले को भी प्रस्तुत किया, अर्थात् अंतराल ग्राफ़ों का अब शास्त्रीय परिवार। बाद में, Sinden (1966) विद्युत नेटवर्क और मुद्रित सर्किट के लिए समान विचार निर्दिष्ट किया। स्ट्रिंग ग्राफ़ का गणितीय अध्ययन पेपर से शुरू हुआ Ehrlich, Even & Tarjan (1976) और सिंडेन और रोनाल्ड ग्राहम के बीच एक सहयोग के माध्यम से, जहां 1976 में कॉम्बिनेटोरिक्स पर 5वें हंगेरियन कॉलोक्वियम में स्ट्रिंग ग्राफ के लक्षण वर्णन को अंततः एक खुले प्रश्न के रूप में प्रस्तुत किया गया।[1] हालांकि, स्ट्रिंग ग्राफ़ की मान्यता अंततः एनपी-पूर्ण साबित हुई थी, जिसका अर्थ है कि कोई सरल लक्षण वर्णन उपस्थित होने की संभावना नहीं है।[2]
संबंधित ग्राफ वर्ग
प्रत्येक समतली आलेख एक स्ट्रिंग ग्राफ है:[3] जैसा कि चित्र में दिखाया गया है, शीर्ष के चारों ओर और प्रत्येक आसन्न किनारे के मध्य बिंदु के चारों ओर घूमने वाले प्रत्येक शीर्ष के लिए एक स्ट्रिंग खींचकर एक मनमाने ढंग से विमान-एम्बेडेड ग्राफ का एक स्ट्रिंग ग्राफ प्रतिनिधित्व कर सकता है। ग्राफ के किसी भी किनारे uv के लिए, u और v के लिए तार uv के मध्य बिंदु के पास एक दूसरे को दो बार पार करते हैं, और कोई अन्य क्रॉसिंग नहीं है, इसलिए तार के जोड़े जो क्रॉस करते हैं, मूल समतली आलेख के निकटवर्ती जोड़े का प्रतिनिधित्व करते हैं। . वैकल्पिक रूप से, सर्कल पैकिंग प्रमेय द्वारा, किसी भी समतली आलेख को सर्किलों के संग्रह के रूप में दर्शाया जा सकता है, जिनमें से कोई भी दो क्रॉस हो सकता है अगर और केवल अगर संबंधित शिखर निकट हैं; ये वृत्त (शुरुआती और अंतिम बिंदु के साथ उन्हें खुले वक्रों में बदलने के लिए चुने गए) दिए गए समतली आलेख का एक स्ट्रिंग ग्राफ प्रतिनिधित्व प्रदान करते हैं। Chalopin, Gonçalves & Ochem (2007) ने साबित किया कि प्रत्येक समतली आलेख़ में एक स्ट्रिंग प्रस्तुति होती है जिसमें ऊपर वर्णित प्रस्तुतियों के विपरीत स्ट्रिंग्स की प्रत्येक जोड़ी में अधिकतम एक क्रॉसिंग पॉइंट होता है।
स्कीनरमैन का अनुमान, जो अब सिद्ध हो चुका है, और भी मजबूत कथन है कि प्रत्येक समतली आलेख को सीधी रेखा खंडों के प्रतिच्छेदन ग्राफ द्वारा दर्शाया जा सकता है, जो स्ट्रिंग्स का एक बहुत ही विशेष मामला है।
यदि किसी दिए गए ग्राफ़ G का प्रत्येक किनारा उपखंड (ग्राफ़ सिद्धांत) है, तो परिणामी ग्राफ़ एक स्ट्रिंग ग्राफ़ है यदि और केवल यदि G समतलीय है। विशेष रूप से, पूर्ण ग्राफ K का उपखंड5 उदाहरण में दिखाया गया एक स्ट्रिंग ग्राफ नहीं है, क्योंकि K5 समतलीय नहीं है।[3]
प्रत्येक वृत्त ग्राफ, रेखा खंडों (एक वृत्त की जीवा) के प्रतिच्छेदन ग्राफ़ के रूप में, एक स्ट्रिंग ग्राफ़ भी है। प्रत्येक कॉर्डल ग्राफ़ को एक स्ट्रिंग ग्राफ़ के रूप में दर्शाया जा सकता है: कॉर्डल ग्राफ़ पेड़ों के सबट्रीज़ के प्रतिच्छेदन ग्राफ़ हैं, और एक कॉर्डल ग्राफ़ का एक स्ट्रिंग प्रतिनिधित्व बना सकता है जो संबंधित पेड़ के एक प्लानर एम्बेडिंग का निर्माण करता है और प्रत्येक सबट्री को एक स्ट्रिंग द्वारा प्रतिस्थापित करता है जो ट्रेस करता है सबट्री के किनारों के आसपास।
प्रत्येक तुलनात्मक ग्राफ का पूरक ग्राफ भी एक स्ट्रिंग ग्राफ है।[4]
अन्य परिणाम
एर्लिच, ईवन & टारजन (1976) ने एन.पी-हार्ड होने के लिए स्ट्रिंग ग्राफ़ की वर्णिक अंक की गणना करना दिखाया। क्रैटोचविल (1991a) ने पाया कि स्ट्रिंग ग्राफ़ प्रेरित उपसारणिक संवृत वर्ग बनाते हैं, लेकिन ग्राफ़ के उपसारणिक संवृत वर्ग नहीं।
प्रत्येक m-किनारों वाली स्ट्रिंग ग्राफ को दो उपसमुच्चयों में विभाजित किया जा सकता है, O(m)3/4log1/2m) शीर्षों को हटाकर, जिनमें से प्रत्येक पूरे ग्राफ़ के आकार का एक स्थिर अंश होता है। यह इस प्रकार है कि बिक्लिक-मुक्त ग्राफ, स्ट्रिंग ग्राफ़ जिसमें कुछ स्थिर t के लिए कोई उप ग्राफ Kt,t नहीं होता है, O(n) किनारे होते हैं और अधिक दृढ़ता से बहुपद विस्तार होता है।[5]
टिप्पणियाँ
- ↑ Graham (1976).
- ↑ 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 Schaefer & Štefankovič (2001) and Pach & Tóth (2002), Schaefer, Sedgwick & Štefankovič (2003) completed the proof that the problem is NP-complete.
- ↑ 3.0 3.1 Schaefer & Štefankovič (2001) credit this observation to Sinden (1966).
- ↑ Golumbic, Rotem & Urrutia (1983) and Lovász (1983). See also Fox & Pach (2010).
- ↑ Fox & Pach (2010); Dvořák & Norin (2015).
संदर्भ
- Benzer, S. (1959), "On the topology of the genetic fine structure", Proceedings of the National Academy of Sciences of the United States of America, 45 (11): 1607–1620, Bibcode:1959PNAS...45.1607B, doi:10.1073/pnas.45.11.1607, PMC 222769, PMID 16590553.
- Chalopin, J.; Gonçalves, D.; Ochem, P. (2007), "Planar graphs are in 1-STRING", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ACM and SIAM, pp. 609–617.
- Dvořák, Zdeněk; Norin, Sergey (2016), "Strongly sublinear separators and polynomial expansion", SIAM Journal on Discrete Mathematics, 30 (2): 1095–1101, arXiv:1504.04821, Bibcode:2015arXiv150404821D, doi:10.1137/15M1017569.
- Ehrlich, G.; Even, S.; Tarjan, R. E. (1976), "Intersection graphs of curves in the plane", Journal of Combinatorial Theory, 21 (1): 8–20, doi:10.1016/0095-8956(76)90022-8.
- Fox, Jacob; Pach, János (2010), "A separator theorem for string graphs and its applications", Combinatorics, Probability and Computing, 19 (3): 371, doi:10.1017/s0963548309990459, S2CID 5705145.
- 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.
- Graham, R. L. (1976), "Problem 1", Open Problems at 5th Hungarian Colloquium on Combinatorics.
- Kratochvil, Jan (1991a), "String Graphs. I. The number of critical nonstring graphs is infinite", Journal of Combinatorial Theory, Series B, 52 (1): 53–66, doi:10.1016/0095-8956(91)90090-7.
- Kratochvil, Jan (1991b), "String Graphs. II. Recognizing string graphs is NP-Hard", Journal of Combinatorial Theory, Series B, 52 (1): 67–78, doi:10.1016/0095-8956(91)90091-W.
- Lovász, L. (1983), "Perfect graphs", Selected Topics in Graph Theory, vol. 2, London: Academic Press, pp. 55–87.
- Pach, János; Tóth, Geza (2002), "Recognizing string graphs is decidable", Discrete & Computational Geometry, 28 (4): 593–606, doi:10.1007/s00454-002-2891-4.
- Schaefer, Marcus; Štefankovič, Daniel (2001), "Decidability of string graphs", Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC 2001): 241–246.
- Schaefer, Marcus; Sedgwick, Eric; Štefankovič, Daniel (2003), "Recognizing string graphs in NP", Journal of Computer and System Sciences, 67 (2): 365–380, doi:10.1016/S0022-0000(03)00045-X.
- Sinden, F. W. (1966), "Topology of thin film RC-circuits", Bell System Technical Journal, 45 (9): 1639–1662, doi:10.1002/j.1538-7305.1966.tb01713.x.
