प्रवणता संख्या: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Number of edge slopes in graph drawing}} | {{Short description|Number of edge slopes in graph drawing}} | ||
[[File:Petersen graph with slope number 3.svg|thumb| | [[File:Petersen graph with slope number 3.svg|thumb|प्रवणता संख्या 3 के साथ [[पीटरसन ग्राफ]] का चित्र]][[ग्राफ ड्राइंग]] और ज्यामितीय ग्राफ़ सिद्धांत में, ग्राफ़ की '''प्रवणता संख्या''' ग्राफ़ की ड्राइंग में किनारों के भिन्न-भिन्न प्रवणताओं की न्यूनतम संभव संख्या होती है जिसमें कोने को यूक्लिडियन समतल में बिंदुओं के रूप में दर्शाया जाता है और किनारों को [[रेखा खंड]] के रूप में दर्शाया जाता है। किसी भी गैर-घटना शीर्ष से होकर न निकले । | ||
==पूर्ण ग्राफ़== | ==पूर्ण ग्राफ़== | ||
चूंकि [[असतत ज्यामिति]] में निकट संबंधी समस्याओं का अध्ययन पहले किया जा चुका है,इस प्रकार से उदाहरण के लिए द्वारा {{harvtxt|स्कॉट|1970}} और {{harvtxt|जेमिसन|1984}}, | चूंकि [[असतत ज्यामिति]] में निकट संबंधी समस्याओं का अध्ययन पहले किया जा चुका है,इस प्रकार से उदाहरण के लिए द्वारा {{harvtxt|स्कॉट|1970}} और {{harvtxt|जेमिसन|1984}}, | ||
इस प्रकार से ग्राफ़ की | इस प्रकार से ग्राफ़ की प्रवणता संख्या निर्धारित करने की समस्या किसके द्वारा प्रस्तुत की गई थी? {{harvtxt|वेड|चू|1994}}, जिसने दिखाया कि प्रवणता संख्या {{mvar|n}}-वर्टेक्स [[पूरा ग्राफ]] {{math|''K''<sub>''n''</sub>}} बिलकुल {{mvar|n}} है. ग्राफ़ के शीर्षों को [[नियमित बहुभुज]] पर रखकर इस प्रवणता संख्या के साथ चित्र बनाया जा सकता है। | ||
==डिग्री से संबंध== | ==डिग्री से संबंध== | ||
इस प्रकार से अधिकतम डिग्री के ग्राफ़ की | इस प्रकार से अधिकतम डिग्री के ग्राफ़ की प्रवणता संख्या {{mvar|d}} स्पष्ट रूप से कम से कम <math>\lceil d/2\rceil</math> है, क्योंकि घटना के अधिकतम दो किनारे डिग्री पर-{{mvar|d}} शीर्ष प्रवणता साझा कर सकता है। अधिक स्पष्ट रूप से, प्रवणता संख्या कम से कम ग्राफ़ की [[रैखिक आर्बोरिसिटी]] के समान होती है, क्योंकि एकल प्रवणता के किनारों को रैखिक फारेस्ट बनाना चाहिए, और बदले में रैखिक आर्बोरिसिटी कम से कम <math>\lceil d/2\rceil</math> होती है . | ||
अधिकतम [[डिग्री (ग्राफ सिद्धांत)]] पांच वाले ग्राफ़ मौजूद हैं जिनमें मनमाने ढंग से बड़ी प्रवणता संख्या होती है।<ref>Proved independently by {{harvtxt|Barát|Matoušek|Wood|2006}} and {{harvtxt|Pach|Pálvölgyi|2006}}, solving a problem posed by {{harvtxt|Dujmović|Suderman|Wood|2005}}. See theorems 5.1 and 5.2 of {{harvtxt|Pach|Sharir|2009}}.</ref> चूंकि , अधिकतम डिग्री तीन के प्रत्येक ग्राफ में प्रवणता संख्या अधिकतम चार होती है;<ref>{{harvtxt|Mukkamala|Szegedy|2009}}, improving an earlier result of {{harvtxt|Keszegh|Pach|Pálvölgyi|Tóth|2008}}; theorem 5.3 of {{harvtxt|Pach|Sharir|2009}}.</ref> का परिणाम {{harvtxt|वेड|चू|1994}} संपूर्ण ग्राफ़ के लिए {{math|''K''<sub>4</sub>}}दिखाता है कि यह तंग है। इस प्रकार से चार प्रवणताओं का प्रत्येक समुच्य सभी डिग्री-3 ग्राफ़ खींचने के लिए उपयुक्त नहीं किये जाते है: और प्रवणताओं का समुच्य इस उद्देश्य के लिए उपयुक्त होता है अर्यथात यह समांतर [[चतुर्भुज]] के पक्षों और विकर्णों की प्रवणता बनाता है। विशेष रूप से, कोई भी डिग्री 3 ग्राफ़ खींचा जा सकता है किंतु उसके किनारे या तो अक्ष-समानांतर हों या [[पूर्णांक जाली|पूर्णांक जालक]] के मुख्य विकर्णों के समानांतर होता है ।<ref>{{harvtxt|Mukkamala|Pálvölgyi|2012}}.</ref> परन्तु यह ज्ञात नहीं है कि अधिकतम डिग्री चार के ग्राफ़ में प्रवणता संख्या सीमित होती है या असीमित होती है।<ref>{{harvtxt|Pach|Sharir|2009}}.</ref> | |||
अधिकतम [[डिग्री (ग्राफ सिद्धांत)]] पांच वाले ग्राफ़ मौजूद हैं जिनमें मनमाने ढंग से बड़ी | |||
[[File:KesPacPal-GD-10.svg|thumb|की विधि {{harvtxt|केसज़ेघ|पच|पाल्वोल्ग्यी|2011}} परिबद्ध डिग्री के साथ | [[File:KesPacPal-GD-10.svg|thumb|की विधि {{harvtxt|केसज़ेघ|पच|पाल्वोल्ग्यी|2011}} परिबद्ध डिग्री के साथ प्रवणता ग्राफ़ के लिए परिबद्ध प्रवणता संख्या प्राप्त करने के लिए वृत्त पैकिंग और क्वाडट्री के संयोजन के लिए]] | ||
== | ==प्रवणताीय रेखांकन== | ||
जैसा {{harvtxt|केसज़ेग|पच|पाल्वोल्ग्यी|2011}} दिखाया गया है, प्रत्येक [[समतलीय ग्राफ]] में फ़ेरी का प्रमेय होता है और तलीय सीधी-रेखा रेखाचित्र जिसमें भिन्न-भिन्न | जैसा {{harvtxt|केसज़ेग|पच|पाल्वोल्ग्यी|2011}} दिखाया गया है, प्रत्येक [[समतलीय ग्राफ|प्रवणताीय ग्राफ]] में फ़ेरी का प्रमेय होता है और तलीय सीधी-रेखा रेखाचित्र जिसमें भिन्न-भिन्न प्रवणताओं की संख्या ग्राफ़ की डिग्री का कार्य है। इस तरह से प्रमाण निर्माण का अनुसरण करता है {{harvtxt|मालित्ज़|पापाकोस्टास|1994}} प्रवणताीय ग्राफ़ के कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) को डिग्री के फलन के रूप में सीमित करने के लिए, ग्राफ़ को स्थिर कारक से अधिक की डिग्री में वृद्धि किए बिना अधिकतम प्रवणताीय ग्राफ़ में पूर्ण करके, और इस संवर्धित ग्राफ़ का प्रतिनिधित्व करने के लिए [[सर्कल पैकिंग प्रमेय]] को प्रयुक्त करना स्पर्शरेखा वृत्तों के संग्रह के रूप में उपयोग किया गया है । यदि प्रारंभिक ग्राफ़ की डिग्री परिबद्ध है, तो पैकिंग में आसन्न वृत्तों की त्रिज्याओं के मध्य का अनुपात भी [[रिंग लेम्मा]] द्वारा परिबद्ध होगा,<ref>{{harvtxt|Hansen|1988}}.</ref> जिसका तात्पर्य यह है कि प्रत्येक ग्राफ शीर्ष को उसके वृत्त के अन्दर बिंदु पर रखने के लिए [[क्वाडट्री]] का उपयोग करने से प्रवणता उत्पन्न होंगे जोकी छोटे पूर्णांकों के अनुपात होते हैं। इस निर्माण द्वारा उत्पन्न भिन्न-भिन्न प्रवणताओं की संख्या ग्राफ़ की डिग्री में घातीय होती है। | ||
==जटिलता== | ==जटिलता== | ||
इस प्रकार से यह निर्धारित करना एनपी-पूर्ण है कि ग्राफ़ में | इस प्रकार से यह निर्धारित करना एनपी-पूर्ण है कि ग्राफ़ में प्रवणता संख्या दो है या नहीं है ।<ref>{{harvtxt|Formann|Hagerup|Haralambides|Kaufmann|1993}}; {{harvtxt|Eades|Hong|Poon|2010}}; {{harvtxt|Maňuch|Patterson|Poon|Thachuk|2011}}.</ref> इससे यह पता चलता है कि किसी इच्छा से ग्राफ की प्रवणता संख्या निर्धारित करना, या 3/2 से उत्तम [[सन्निकटन अनुपात]] के साथ इसका अनुमान लगाना एनपी-कठिन है। | ||
यह निर्धारित करना भी एनपी-पूर्ण है कि क्या | यह निर्धारित करना भी एनपी-पूर्ण है कि क्या प्रवणताीय ग्राफ़ में प्रवणता संख्या दो के साथ प्रवणताीय रेखाचित्र है,<ref>{{harvtxt|Garg|Tamassia|2001}}.</ref> | ||
और वास्तविकता के अस्तित्व संबंधी सिद्धांत के लिए | और वास्तविकता के अस्तित्व संबंधी सिद्धांत के लिए प्रवणताीय रेखाचित्र की न्यूनतम प्रवणता संख्या निर्धारित करना कठिन होता है।<ref>{{harvtxt|Hoffmann|2016}}.</ref> | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
{{reflist|colwidth=30em}} | {{reflist|colwidth=30em}} | ||
Latest revision as of 14:54, 18 September 2023
प्रवणता संख्या 3 के साथ पीटरसन ग्राफ का चित्र
ग्राफ ड्राइंग और ज्यामितीय ग्राफ़ सिद्धांत में, ग्राफ़ की प्रवणता संख्या ग्राफ़ की ड्राइंग में किनारों के भिन्न-भिन्न प्रवणताओं की न्यूनतम संभव संख्या होती है जिसमें कोने को यूक्लिडियन समतल में बिंदुओं के रूप में दर्शाया जाता है और किनारों को रेखा खंड के रूप में दर्शाया जाता है। किसी भी गैर-घटना शीर्ष से होकर न निकले ।
पूर्ण ग्राफ़
चूंकि असतत ज्यामिति में निकट संबंधी समस्याओं का अध्ययन पहले किया जा चुका है,इस प्रकार से उदाहरण के लिए द्वारा स्कॉट (1970) और जेमिसन (1984),
इस प्रकार से ग्राफ़ की प्रवणता संख्या निर्धारित करने की समस्या किसके द्वारा प्रस्तुत की गई थी? वेड & चू (1994), जिसने दिखाया कि प्रवणता संख्या n-वर्टेक्स पूरा ग्राफ Kn बिलकुल n है. ग्राफ़ के शीर्षों को नियमित बहुभुज पर रखकर इस प्रवणता संख्या के साथ चित्र बनाया जा सकता है।
डिग्री से संबंध
इस प्रकार से अधिकतम डिग्री के ग्राफ़ की प्रवणता संख्या d स्पष्ट रूप से कम से कम है, क्योंकि घटना के अधिकतम दो किनारे डिग्री पर-d शीर्ष प्रवणता साझा कर सकता है। अधिक स्पष्ट रूप से, प्रवणता संख्या कम से कम ग्राफ़ की रैखिक आर्बोरिसिटी के समान होती है, क्योंकि एकल प्रवणता के किनारों को रैखिक फारेस्ट बनाना चाहिए, और बदले में रैखिक आर्बोरिसिटी कम से कम होती है .
अधिकतम डिग्री (ग्राफ सिद्धांत) पांच वाले ग्राफ़ मौजूद हैं जिनमें मनमाने ढंग से बड़ी प्रवणता संख्या होती है।[1] चूंकि , अधिकतम डिग्री तीन के प्रत्येक ग्राफ में प्रवणता संख्या अधिकतम चार होती है;[2] का परिणाम वेड & चू (1994) संपूर्ण ग्राफ़ के लिए K4दिखाता है कि यह तंग है। इस प्रकार से चार प्रवणताओं का प्रत्येक समुच्य सभी डिग्री-3 ग्राफ़ खींचने के लिए उपयुक्त नहीं किये जाते है: और प्रवणताओं का समुच्य इस उद्देश्य के लिए उपयुक्त होता है अर्यथात यह समांतर चतुर्भुज के पक्षों और विकर्णों की प्रवणता बनाता है। विशेष रूप से, कोई भी डिग्री 3 ग्राफ़ खींचा जा सकता है किंतु उसके किनारे या तो अक्ष-समानांतर हों या पूर्णांक जालक के मुख्य विकर्णों के समानांतर होता है ।[3] परन्तु यह ज्ञात नहीं है कि अधिकतम डिग्री चार के ग्राफ़ में प्रवणता संख्या सीमित होती है या असीमित होती है।[4]
की विधि केसज़ेघ, पच & पाल्वोल्ग्यी (2011) परिबद्ध डिग्री के साथ प्रवणता ग्राफ़ के लिए परिबद्ध प्रवणता संख्या प्राप्त करने के लिए वृत्त पैकिंग और क्वाडट्री के संयोजन के लिए
प्रवणताीय रेखांकन
जैसा केसज़ेग, पच & पाल्वोल्ग्यी (2011) दिखाया गया है, प्रत्येक प्रवणताीय ग्राफ में फ़ेरी का प्रमेय होता है और तलीय सीधी-रेखा रेखाचित्र जिसमें भिन्न-भिन्न प्रवणताओं की संख्या ग्राफ़ की डिग्री का कार्य है। इस तरह से प्रमाण निर्माण का अनुसरण करता है मालित्ज़ & पापाकोस्टास (1994) प्रवणताीय ग्राफ़ के कोणीय रिज़ॉल्यूशन (ग्राफ़ ड्राइंग) को डिग्री के फलन के रूप में सीमित करने के लिए, ग्राफ़ को स्थिर कारक से अधिक की डिग्री में वृद्धि किए बिना अधिकतम प्रवणताीय ग्राफ़ में पूर्ण करके, और इस संवर्धित ग्राफ़ का प्रतिनिधित्व करने के लिए सर्कल पैकिंग प्रमेय को प्रयुक्त करना स्पर्शरेखा वृत्तों के संग्रह के रूप में उपयोग किया गया है । यदि प्रारंभिक ग्राफ़ की डिग्री परिबद्ध है, तो पैकिंग में आसन्न वृत्तों की त्रिज्याओं के मध्य का अनुपात भी रिंग लेम्मा द्वारा परिबद्ध होगा,[5] जिसका तात्पर्य यह है कि प्रत्येक ग्राफ शीर्ष को उसके वृत्त के अन्दर बिंदु पर रखने के लिए क्वाडट्री का उपयोग करने से प्रवणता उत्पन्न होंगे जोकी छोटे पूर्णांकों के अनुपात होते हैं। इस निर्माण द्वारा उत्पन्न भिन्न-भिन्न प्रवणताओं की संख्या ग्राफ़ की डिग्री में घातीय होती है।
जटिलता
इस प्रकार से यह निर्धारित करना एनपी-पूर्ण है कि ग्राफ़ में प्रवणता संख्या दो है या नहीं है ।[6] इससे यह पता चलता है कि किसी इच्छा से ग्राफ की प्रवणता संख्या निर्धारित करना, या 3/2 से उत्तम सन्निकटन अनुपात के साथ इसका अनुमान लगाना एनपी-कठिन है।
यह निर्धारित करना भी एनपी-पूर्ण है कि क्या प्रवणताीय ग्राफ़ में प्रवणता संख्या दो के साथ प्रवणताीय रेखाचित्र है,[7]
और वास्तविकता के अस्तित्व संबंधी सिद्धांत के लिए प्रवणताीय रेखाचित्र की न्यूनतम प्रवणता संख्या निर्धारित करना कठिन होता है।[8]
टिप्पणियाँ
- ↑ Proved independently by Barát, Matoušek & Wood (2006) and Pach & Pálvölgyi (2006), solving a problem posed by Dujmović, Suderman & Wood (2005). See theorems 5.1 and 5.2 of Pach & Sharir (2009).
- ↑ Mukkamala & Szegedy (2009), improving an earlier result of Keszegh et al. (2008); theorem 5.3 of Pach & Sharir (2009).
- ↑ Mukkamala & Pálvölgyi (2012).
- ↑ Pach & Sharir (2009).
- ↑ Hansen (1988).
- ↑ Formann et al. (1993); Eades, Hong & Poon (2010); Maňuch et al. (2011).
- ↑ Garg & Tamassia (2001).
- ↑ Hoffmann (2016).
संदर्भ
- Barát, János; Matoušek, Jiří; Wood, David R. (2006), "Bounded-degree graphs have arbitrarily large geometric thickness", Electronic Journal of Combinatorics, 13 (1): R3, MR 2200531.
- Dujmović, Vida; Suderman, Matthew; Wood, David R. (2005), "Really straight graph drawings", in Pach, János (ed.), Graph Drawing: 12th International Symposium, GD 2004, New York, NY, USA, September 29-October 2, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 3383, Berlin: Springer-Verlag, pp. 122–132, arXiv:cs/0405112, doi:10.1007/978-3-540-31843-9_14.
- Eades, Peter; Hong, Seok-Hee; Poon, Sheung-Hung (2010), "On rectilinear drawing of graphs", in Eppstein, David; Gansner, Emden R. (eds.), Graph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009, Revised Papers, Lecture Notes in Computer Science, vol. 5849, Berlin: Springer, pp. 232–243, doi:10.1007/978-3-642-11805-0_23, MR 2680455.
- Formann, M.; Hagerup, T.; Haralambides, J.; Kaufmann, M.; Leighton, F. T.; Symvonis, A.; Welzl, E.; Woeginger, G. (1993), "Drawing graphs in the plane with high resolution", SIAM Journal on Computing, 22 (5): 1035–1052, doi:10.1137/0222063, MR 1237161.
- Garg, Ashim; Tamassia, Roberto (2001), "On the computational complexity of upward and rectilinear planarity testing", SIAM Journal on Computing, 31 (2): 601–625, doi:10.1137/S0097539794277123, MR 1861292.
- Hansen, Lowell J. (1988), "On the Rodin and Sullivan ring lemma", Complex Variables, Theory and Application, 10 (1): 23–30, doi:10.1080/17476938808814284, MR 0946096.
- Hoffmann, Udo (2016), "The planar slope number", Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016).
- Jamison, Robert E. (1984), "Planar configurations which determine few slopes", Geometriae Dedicata, 16 (1): 17–34, doi:10.1007/BF00147419, MR 0757792.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör (2011), "Drawing planar graphs of bounded degree with few slopes", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 293–304, arXiv:1009.1315, doi:10.1007/978-3-642-18469-7_27, MR 2781274.
- Keszegh, Balázs; Pach, János; Pálvölgyi, Dömötör; Tóth, Géza (2008), "Drawing cubic graphs with at most five slopes", Computational Geometry: Theory and Applications, 40 (2): 138–147, doi:10.1016/j.comgeo.2007.05.003, MR 2400539.
- Malitz, Seth; Papakostas, Achilleas (1994), "On the angular resolution of planar graphs", SIAM Journal on Discrete Mathematics, 7 (2): 172–183, doi:10.1137/S0895480193242931, MR 1271989.
- Maňuch, Ján; Patterson, Murray; Poon, Sheung-Hung; Thachuk, Chris (2011), "Complexity of finding non-planar rectilinear drawings of graphs", in Brandes, Ulrik; Cornelsen, Sabine (eds.), Graph Drawing: 18th International Symposium, GD 2010, Konstanz, Germany, September 21-24, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6502, Heidelberg: Springer, pp. 305–316, doi:10.1007/978-3-642-18469-7_28, hdl:10281/217381, MR 2781275.
- Mukkamala, Padmini; Szegedy, Mario (2009), "Geometric representation of cubic graphs with four directions", Computational Geometry: Theory and Applications, 42 (9): 842–851, doi:10.1016/j.comgeo.2009.01.005, MR 2543806.
- Mukkamala, Padmini; Pálvölgyi, Dömötör (2012), "Drawing cubic graphs with the four basic slopes", in van Kreveld, Marc; Speckmann, Bettina (eds.), Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers, Lecture Notes in Computer Science, vol. 7034, Springer, pp. 254–265, arXiv:1106.1973, doi:10.1007/978-3-642-25878-7_25.
- Pach, János; Pálvölgyi, Dömötör (2006), "Bounded-degree graphs can have arbitrarily large slope numbers", Electronic Journal of Combinatorics, 13 (1): N1, MR 2200545.
- Pach, János; Sharir, Micha (2009), "5.5 Angular resolution and slopes", Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures, Mathematical Surveys and Monographs, vol. 152, American Mathematical Society, pp. 126–127.
- Scott, P. R. (1970), "On the sets of directions determined by n points", American Mathematical Monthly, 77: 502–505, doi:10.2307/2317384, MR 0262933.
- Wade, G. A.; Chu, J.-H. (1994), "Drawability of complete graphs using a minimal slope set", The Computer Journal, 37 (2): 139–142, doi:10.1093/comjnl/37.2.139.
