लामन आरेख़: Difference between revisions

Revision as of 17:29, 15 May 2023

मोजर धुरी , एक छद्मत्रिकोण के रूप में खींचा गया एक तलीय लैमन आरेख

पूर्ण द्विदलीय आरेख K_3,3, एक गैर-तलीय लैमन आरेख

आरेख़ सिद्धांत में लैमन आरेख़ विरल आरेख़ का एक समूह है जो समतल में छड़ और युग्म की न्यूनतम जटिल प्रणाली का वर्णन करता है। औपचारिक रूप से लैमन आरेख़ $n$ शीर्षों पर एक आरेख़ होता है जैसे कि सभी k के लिए प्रत्येक k कोणबिंदु उपआरेख में अधिकतम 2k − 3 शीर्ष होते हैं और ऐसे ही संपूर्ण आरेख़ में 2n − 3 शीर्ष होते हैं। लैमन आरेख का नाम एम्स्टर्डम विश्वविद्यालय के जेरार्ड लैमन के नाम पर रखा गया है जिन्होंने 1970 में जटिल तलीय संरचनाओं को चित्रित करने के लिए उनका उपयोग किया था। हालाँकि इस विधि का वर्णन 1927 में हिल्डा जिरिंगर द्वारा पहले ही खोजा जा चुका था।^[1]

जटिलता

जटिलता सिद्धांत में लैमन आरेख उत्पन्न होते हैं यदि कोई यूयूक्लिडियन समतल में एक लैमन आरेख के शीर्ष को सामान्य स्थिति में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करता है एक आरेख इस अर्थ में जटिलहोता है यदि और केवल यदि उसके पास एक लैमन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लैमन आरेख सामान्यतः न्यूनतम जटिल आरेख हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।

यदि समतल में n बिंदु दिए गए हैं, तो उनके प्लेसमेंट में स्वतंत्रता की 2n डिग्री होती है (प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं), लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है (इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन)। सहज रूप से, एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है, इसलिए लैमन आरेख में 2n - 3 शीर्ष प्रारंभिक बिंदु प्लेसमेंट की स्वतंत्रता की 2n डिग्री को एक की स्वतंत्रता की तीन डिग्री तक कम कर देते हैं। जटिल आरेख। हालांकि, 2n − 3 किनारों वाला हर आरेख जटिल नहीं होता है; लैमन आरेख की परिभाषा में यह शर्त कि किसी भी उप आरेख में बहुत अधिक शीर्ष नहीं हो सकते हैं, यह सुनिश्चित करता है कि प्रत्येक किनारा स्वतंत्रता की कुल संख्या को कम करने में योगदान देता है और एक उप आरेख के भीतर नष्ट नहीं होता है जो पहले से ही अपने अन्य किनारों के कारण जटिल है।

समतलता

एक नुकीला स्यूडोट्रायंगुलेशन एक आरेख़ का एक तलीय स्ट्रेट-लाइन ड्रॉइंग है, जिसमें गुण हैं कि बाहरी चेहरा उत्तल है, कि हर घिरा हुआ चेहरा एक स्यूडोट्राएंगल है, एक बहुभुज जिसमें केवल तीन उत्तल शीर्ष होते हैं, और किनारों की घटना हर शीर्ष पर होती है। 180 डिग्री से कम का कोण। पॉइंटेड स्यूडोट्राएंगुलेशन के रूप में खींचे जा सकने वाले आरेख़ वास्तव में तलीय लैमन आरेख़ हैं।^[2] हालाँकि, लैमन आरेख़ में तलीय एम्बेडिंग होते हैं जो स्यूडोट्रायंगुलेशन नहीं होते हैं और ऐसे लैमन आरेख़ होते हैं जो तलीय नहीं होते हैं, जैसे कि यूटिलिटी आरेख़ K3,3।

विरलता

Lee & Streinu (2008) और Streinu & Theran (2009) एक आरेख को $(k,\ell )$ -विरल के रूप में परिभाषित करते हैं, यदि $n$ शीर्ष वाले प्रत्येक गैर-खाली उप आरेख में अधिकतम $kn-\ell$ शीर्ष हों, और $(k,\ell )$ - तंग यदि यह $(k,\ell )$ -विरल है और बिल्कुल $kn-\ell$ शीर्ष हैं। इस प्रकार, उनके अंकन में, लैमन आरेख बिल्कुल (2,3)-तंग आरेख हैं, और लैमन आरेख के उप आरेख बिल्कुल (2,3)-विरल आरेख हैं। विरल आरेख के अन्य महत्वपूर्ण समूहों का वर्णन करने के लिए एक ही संकेतन का उपयोग किया जा सकता है, जिसमें पेड़, स्यूडोफॉरेस्ट, और बाउंडेड आर्बरसिटी के आरेख सम्मिलित हैं।^[3]^[4]

इस चरित्र-चित्रण के आधार पर, समय $O (n 2)$ में $n$ -वर्टेक्स लैमन आरेख को पहचानना संभव है, एक "कंकड़ खेल" का अनुकरण करके, जो $n$ शीर्ष वाले आरेख से प्रारम्भ होता है और कोई किनारा नहीं होता है, प्रत्येक शीर्ष पर दो कंकड़ रखे जाते हैं, और आरेख़ के सभी किनारों को बनाने के लिए निम्नलिखित दो प्रकार के चरणों का अनुक्रम करता है:

किसी भी दो शीर्ष को जोड़ने वाला एक नया निर्देशित किनारा बनाएं जिसमें दोनों में दो कंकड़ हों, और एक कंकड़ को नए शीर्ष के शुरुआती शीर्ष से हटा दें।
यदि कोई किनारा शीर्ष से इंगित करता है $u$ अधिक से अधिक एक कंकड़ से दूसरे शीर्ष पर $v$ कम से कम एक कंकड़ के साथ, एक कंकड़ ले जाएँ $v$ को $u$ और शीर्ष को उलट दें।

यदि इन परिचालनों का उपयोग दिए गए आरेख के अभिविन्यास (आरेख सिद्धांत) के निर्माण के लिए किया जा सकता है, तो यह अनिवार्य रूप से (2,3)-विरल और इसके विपरीत है। हालांकि, तेजी से एल्गोरिदम संभव है, समय $O(n^{3/2}{\sqrt {\log n}})$ में चल रहा है, परीक्षण के आधार पर कि क्या दिए गए आरेख के एक शीर्ष को दोगुना करने से मल्टीआरेख में परिणाम मिलता है (2,2) -टाइट (समतुल्य रूप से, क्या इसे दो शीर्ष-विच्छेद फैले हुए पेड़ों में विघटित किया जा सकता है) और फिर इस अपघटन का उपयोग करके यह जांचने के लिए कि क्या दिया गया आरेख लैमन आरेख है।^[5] नेटवर्क प्रवाह तकनीकों का उपयोग यह परीक्षण करने के लिए किया जा सकता है कि क्या एक तलीय आरेख समय में अधिक तेजी से एक लैमन आरेख है $O(n\log ^{3}n)$ ^[6]

हेनबर्ग निर्माण

मोजर स्पिंडल का हेन्नेबर्ग निर्माण

लैमन और गीरिंगर के काम से पहले, Lebrecht Henneberg [de] ने द्वि-आयामी न्यूनतम जटिल आरेख (यानी, लैमन आरेख) को एक अलग तरीके से चित्रित किया। ^[7] हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम जटिल रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक शीर्ष से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:

आरेख़ में एक नया शीर्ष जोड़ें, किनारों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
आरेख़ के एक शीर्ष को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।

इन परिचालनों का एक क्रम जो एक दिए गए आरेख को बनाता है, उसे आरेख के हेनेबर्ग निर्माण के रूप में जाना जाता है। उदाहरण के लिए, त्रिभुज बनाने के लिए पहले ऑपरेशन का उपयोग करके पूर्ण द्विदलीय आरेख K3,3 का गठन किया जा सकता है और फिर त्रिकोण के प्रत्येक शीर्ष को उप-विभाजित करने के लिए दूसरा ऑपरेशन लागू किया जा सकता है और प्रत्येक उपखंड बिंदु को विपरीत त्रिभुज शीर्ष से जोड़ा जा सकता है।

संदर्भ

↑ Pollaczek‐Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik, 7 (1): 58–72, Bibcode:1927ZaMM....7...58P, doi:10.1002/zamm.19270070107.
↑ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802, S2CID 38637747.
↑ Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics, 308 (8): 1425–1437, arXiv:math/0702129, doi:10.1016/j.disc.2007.07.104, MR 2392060, S2CID 2826.
↑ Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics, 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018, S2CID 5477763.
↑ Daescu, O.; Kurdia, A. (2009), "Towards an optimal algorithm for recognizing Laman graphs", Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09), IEEE, pp. 1–10, arXiv:0801.2404, doi:10.1109/HICSS.2009.470.
↑ Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019), "Recognizing planar Laman graphs", in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 79:1–79:12, doi:10.4230/LIPIcs.ESA.2019.79, ISBN 978-3-95977-124-5
↑ Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig{{citation}}: CS1 maint: location missing publisher (link)

[1] Pollaczek‐Geiringer, Hilda (1927), "Über die Gliederung ebener Fachwerke", Zeitschrift für Angewandte Mathematik und Mechanik, 7 (1): 58–72, Bibcode:1927ZaMM....7...58P, doi:10.1002/zamm.19270070107.

[2] Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802, S2CID 38637747.

[3] Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics, 308 (8): 1425–1437, arXiv:math/0702129, doi:10.1016/j.disc.2007.07.104, MR 2392060, S2CID 2826.

[4] Streinu, I.; Theran, L. (2009), "Sparse hypergraphs and pebble game algorithms", European Journal of Combinatorics, 30 (8): 1944–1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018, S2CID 5477763.

[5] Daescu, O.; Kurdia, A. (2009), "Towards an optimal algorithm for recognizing Laman graphs", Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09), IEEE, pp. 1–10, arXiv:0801.2404, doi:10.1109/HICSS.2009.470.

[6] Rollin, Jonathan; Schlipf, Lena; Schulz, André (2019), "Recognizing planar Laman graphs", in Bender, Michael A.; Svensson, Ola; Herman, Grzegorz (eds.), 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 144, Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 79:1–79:12, doi:10.4230/LIPIcs.ESA.2019.79, ISBN 978-3-95977-124-5

[7] Henneberg, L. (1911), Die graphische Statik der starren Systeme, Leipzig{{citation}}: CS1 maint: location missing publisher (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
-[[File:Moser spindle pseudotriangulation.svg|thumb|240px|[[ मोजर धुरी ]], एक [[छद्मत्रिकोण]] के रूप में खींचा गया एक प्लेनर लैमन ग्राफ]]
+[[File:Moser spindle pseudotriangulation.svg|thumb|240px|[[ मोजर धुरी ]], एक [[छद्मत्रिकोण]] के रूप में खींचा गया एक तलीय लैमन आरेख]]
-[[File:Biclique K 3 3.svg|thumb|150px|[[पूर्ण द्विदलीय ग्राफ]] K<sub>3,3</sub>, एक गैर-प्लानर लैमन ग्राफ]]ग्राफ़ सिद्धांत में, लैमन ग्राफ़ [[विरल ग्राफ]]़ का एक परिवार है जो विमान में छड़ और जोड़ों की न्यूनतम [[कठोर प्रणाली]] का वर्णन करता है। औपचारिक रूप से, एक लैमन ग्राफ़ ''n'' शीर्षों पर एक ग्राफ़ होता है जैसे कि, सभी ''k'' के लिए, प्रत्येक ''k''-शीर्ष सबग्राफ़ में अधिकतम 2''k'' − 3 किनारे होते हैं, और ऐसे कि पूरे ग्राफ़ में ठीक 2''n'' − 3 किनारे हैं। लैमन ग्राफ का नाम [[एम्स्टर्डम विश्वविद्यालय]] के [[जेरार्ड पेज]] के नाम पर रखा गया है, जिन्होंने 1970 में उन्हें कठोर प्लानर संरचनाओं की विशेषता के लिए इस्तेमाल किया था।<ref>{{citation
+[[File:Biclique K 3 3.svg|thumb|150px|[[पूर्ण द्विदलीय ग्राफ|पूर्ण द्विदलीय आरेख]] K<sub>3,3</sub>, एक गैर-तलीय लैमन आरेख]]आरेख़ सिद्धांत में '''लैमन आरेख़''' विरल आरेख़ का एक समूह है जो समतल में छड़ और युग्म की न्यूनतम जटिल प्रणाली का वर्णन करता है। औपचारिक रूप से लैमन आरेख़ <math>n</math> शीर्षों पर एक आरेख़ होता है जैसे कि सभी k के लिए प्रत्येक k कोणबिंदु उपआरेख में अधिकतम 2k − 3 शीर्ष होते हैं और ऐसे ही संपूर्ण आरेख़ में 2n − 3 शीर्ष होते हैं। लैमन आरेख का नाम [[एम्स्टर्डम विश्वविद्यालय]] के [[जेरार्ड पेज|जेरार्ड]] लैमन के नाम पर रखा गया है जिन्होंने 1970 में जटिल तलीय संरचनाओं को चित्रित करने के लिए उनका उपयोग किया था। हालाँकि इस विधि का वर्णन 1927 में [[हिल्डा जिरिंगर]] द्वारा पहले ही खोजा जा चुका था।<ref>{{citation
- | last = Laman | first = G. | authorlink = Gerard Laman
- | doi = 10.1007/BF01534980
- | issue = 4
- | journal = J. Engineering Mathematics
- | mr = 0269535
- | pages = 331–340
- | title = On graphs and the rigidity of plane skeletal structures
- | volume = 4
- | year = 1970| bibcode = 1970JEnMa...4..331L
- | s2cid = 122631794 }}.</ref>
-हालाँकि, यह लक्षण वर्णन, 1927 में [[हिल्डा जिरिंगर]] द्वारा पहले ही खोजा जा चुका था।<ref>{{citation
   | last = Pollaczek‐Geiringer | first = Hilda | authorlink = Hilda Geiringer
   | issue = 1
@@ Line 20: / Line 9: @@
   | year = 1927
   | doi = 10.1002/zamm.19270070107 | bibcode = 1927ZaMM....7...58P }}.</ref>
+== जटिलता ==
+[[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में लैमन आरेख उत्पन्न होते हैं यदि कोई यू[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में एक लैमन आरेख के शीर्ष को [[सामान्य स्थिति]] में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करता है एक आरेख इस अर्थ में जटिलहोता है यदि और केवल यदि उसके पास एक लैमन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लैमन आरेख सामान्यतः न्यूनतम जटिल आरेख हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।
+'''यदि समतल में n बिंदु दिए गए हैं, तो''' उनके प्लेसमेंट में स्वतंत्रता की 2n डिग्री होती है (प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं), लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है (इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन)। सहज रूप से, एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है, इसलिए लैमन आरेख में 2n - 3 शीर्ष प्रारंभिक बिंदु प्लेसमेंट की स्वतंत्रता की 2n डिग्री को एक की स्वतंत्रता की तीन डिग्री तक कम कर देते हैं। जटिल आरेख। हालांकि, 2n − 3 किनारों वाला हर आरेख जटिल नहीं होता है; लैमन आरेख की परिभाषा में यह शर्त कि किसी भी उप आरेख में बहुत अधिक शीर्ष नहीं हो सकते हैं, यह सुनिश्चित करता है कि प्रत्येक किनारा स्वतंत्रता की कुल संख्या को कम करने में योगदान देता है और एक उप आरेख के भीतर नष्ट नहीं होता है जो पहले से ही अपने अन्य किनारों के कारण जटिल है।
-== कठोरता ==
-[[कठोरता सिद्धांत (संरचनात्मक)]] में लैमन ग्राफ उत्पन्न होते हैं: यदि कोई [[यूक्लिडियन विमान]] में लैमन ग्राफ के शिखर को [[सामान्य स्थिति]] में रखता है, तो सामान्य रूप से [[सर्वांगसमता (ज्यामिति)]] के अलावा सभी बिंदुओं की एक साथ निरंतर गति नहीं होगी, जो कि सभी ग्राफ किनारों की लंबाई को बरकरार रखता है। एक ग्राफ इस अर्थ में कठोर है अगर और केवल अगर उसके पास एक लैमन सबग्राफ है जो उसके सभी शीर्षों को फैलाता है। इस प्रकार, लैमन ग्राफ बिल्कुल न्यूनतम कठोर ग्राफ हैं, और वे द्वि-आयामी कठोरता मैट्रोइड्स के आधार बनाते हैं।
-यदि विमान में n बिंदु दिए गए हैं, तो उनके प्लेसमेंट में स्वतंत्रता की 2n डिग्री (इंजीनियरिंग) हैं (प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक हैं), लेकिन एक कठोर ग्राफ में स्वतंत्रता की केवल तीन डिग्री होती है (इसके एक की स्थिति शीर्ष और उस शीर्ष के चारों ओर शेष ग्राफ का घूर्णन)।
-सहज रूप से, एक ग्राफ़ में निश्चित लंबाई के किनारे को जोड़ने से इसकी [[स्वतंत्रता की डिग्री (इंजीनियरिंग)]] संख्या एक से कम हो जाती है, इसलिए लैमन ग्राफ़ में 2n − 3 किनारे प्रारंभिक बिंदु स्थान की स्वतंत्रता की 2n डिग्री को एक की स्वतंत्रता की तीन डिग्री तक कम कर देते हैं। कठोर ग्राफ। हालांकि, 2n − 3 किनारों वाला हर ग्राफ़ कठोर नहीं होता है; लैमन ग्राफ की परिभाषा में यह शर्त कि किसी भी सबग्राफ में बहुत अधिक किनारे नहीं हो सकते हैं, यह सुनिश्चित करता है कि प्रत्येक किनारा स्वतंत्रता की कुल संख्या को कम करने में योगदान देता है, और एक सबग्राफ के भीतर बर्बाद नहीं होता है जो पहले से ही अपने अन्य किनारों के कारण कठोर है।
 == समतलता ==
-स्यूडोट्राएंगल एक [[प्लानर स्ट्रेट-लाइन ग्राफ]] है। एक ग्राफ का प्लेनर स्ट्रेट-लाइन ड्रॉइंग, गुणों के साथ कि बाहरी चेहरा उत्तल है, कि हर घिरा हुआ चेहरा एक स्यूडोट्राएंगल है, एक बहुभुज जिसमें केवल तीन उत्तल कोने हैं, और किनारों की घटना प्रत्येक शीर्ष पर 180 डिग्री से कम का कोण फैला हुआ है। नुकीले स्यूडोट्रायंगुलेशन के रूप में खींचे जा सकने वाले ग्राफ़ वास्तव में [[प्लेनर ग्राफ]]़ लैमन ग्राफ़ हैं।<ref>{{citation
+एक नुकीला स्यूडोट्रायंगुलेशन एक आरेख़ का एक तलीय स्ट्रेट-लाइन ड्रॉइंग है, जिसमें गुण हैं कि बाहरी चेहरा उत्तल है, कि हर घिरा हुआ चेहरा एक स्यूडोट्राएंगल है, एक बहुभुज जिसमें केवल तीन उत्तल शीर्ष होते हैं, और किनारों की घटना हर शीर्ष पर होती है। 180 डिग्री से कम का कोण। पॉइंटेड स्यूडोट्राएंगुलेशन के रूप में खींचे जा सकने वाले आरेख़ वास्तव में तलीय लैमन आरेख़ हैं।<ref>{{citation
   | last1 = Haas | first1 = Ruth | author1-link = Ruth Haas
   | last2 = Orden | first2 = David
@@ Line 48: / Line 34: @@
   | year = 2005
   | arxiv = math/0307347
-  | s2cid = 38637747 }}.</ref> हालाँकि, लैमन ग्राफ़ में प्लानर एम्बेडिंग होते हैं जो स्यूडोट्रायंगुलेशन नहीं होते हैं, और ऐसे लैमन ग्राफ़ होते हैं जो प्लानर नहीं होते हैं, जैसे कि [[ उपयोगिता ग्राफ ]]़ K<sub>3,3</sub>.
+  | s2cid = 38637747 }}.</ref> हालाँकि, लैमन आरेख़ में तलीय एम्बेडिंग होते हैं जो स्यूडोट्रायंगुलेशन नहीं होते हैं और ऐसे लैमन आरेख़ होते हैं जो तलीय नहीं होते हैं, जैसे कि यूटिलिटी आरेख़ K3,3।
 == विरलता ==
-{{harvtxt|Lee|Streinu|2008}} और {{harvtxt|Streinu|Theran|2009}} एक ग्राफ को होने के रूप में परिभाषित करें <math>(k,\ell)</math>-विरल अगर हर गैर-खाली सबग्राफ के साथ <math>n</math> शिखरों में अधिकतम होता है <math>kn-\ell</math> किनारों, और <math>(k,\ell)</math>-तंग अगर है <math>(k,\ell)</math>-विरल और बिल्कुल है <math>kn-\ell</math> किनारों। इस प्रकार, उनके अंकन में, लैमन ग्राफ बिल्कुल (2,3)-तंग ग्राफ हैं, और लैमन ग्राफ के सबग्राफ बिल्कुल (2,3)-विरल ग्राफ हैं। विरल रेखांकन के अन्य महत्वपूर्ण परिवारों का वर्णन करने के लिए एक ही संकेतन का उपयोग किया जा सकता है, जिसमें [[पेड़ (ग्राफ सिद्धांत)]], [[ seudoforest ]]्स और बंधे हुए [[वृक्षारोपण]] के ग्राफ शामिल हैं।<ref>{{citation
+{{harvtxt|Lee|Streinu|2008}} और {{harvtxt|Streinu|Theran|2009}} एक आरेख को<math>(k,\ell)</math>-विरल के रूप में परिभाषित करते हैं, यदि <math>n</math> शीर्ष वाले प्रत्येक गैर-खाली उप आरेख में अधिकतम <math>kn-\ell</math> शीर्ष हों, और <math>(k,\ell)</math>- तंग यदि यह<math>(k,\ell)</math>-विरल है और बिल्कुल <math>kn-\ell</math> शीर्ष हैं। इस प्रकार, उनके अंकन में, लैमन आरेख बिल्कुल (2,3)-तंग आरेख हैं, और लैमन आरेख के उप आरेख बिल्कुल (2,3)-विरल आरेख हैं। विरल आरेख के अन्य महत्वपूर्ण समूहों का वर्णन करने के लिए एक ही संकेतन का उपयोग किया जा सकता है, जिसमें पेड़, स्यूडोफॉरेस्ट, और बाउंडेड आर्बरसिटी के आरेख सम्मिलित हैं।<ref>{{citation
   | last1 = Lee | first1 = Audrey
   | last2 = Streinu | first2 = Ileana | author2-link = Ileana Streinu
@@ Line 64: / Line 50: @@
   | s2cid = 2826
   }}.</ref><ref>{{citation|first1=I.|last1=Streinu|author1-link=Ileana Streinu|first2=L.|last2=Theran|year=2009|title=Sparse hypergraphs and pebble game algorithms|journal=[[European Journal of Combinatorics]]|volume=30|issue=8|pages=1944–1964|doi=10.1016/j.ejc.2008.12.018|arxiv=math/0703921 |s2cid=5477763}}.</ref>
-इस लक्षण के आधार पर पहचान की जा सकती है {{mvar|n}}-वरटेक्स लैमन समय में रेखांकन करता है {{math|''O''(''n''<sup>2</sup>)}}, एक कंकड़ खेल का अनुकरण करके जो एक ग्राफ के साथ शुरू होता है {{mvar|n}} कोने और कोई किनारा नहीं, प्रत्येक शीर्ष पर दो कंकड़ रखे जाते हैं, और ग्राफ के सभी किनारों को बनाने के लिए निम्नलिखित दो प्रकार के चरणों का एक क्रम करता है:
-* किसी भी दो कोने को जोड़ने वाला एक नया निर्देशित किनारा बनाएं जिसमें दोनों में दो कंकड़ हों, और एक कंकड़ को नए किनारे के शुरुआती शीर्ष से हटा दें।
+इस चरित्र-चित्रण के आधार पर, समय {{math|''O''(''n''<sup>2</sup>)}} में {{mvar|n}}-वर्टेक्स लैमन आरेख को पहचानना संभव है, एक "कंकड़ खेल" का अनुकरण करके, जो {{mvar|n}} शीर्ष वाले आरेख से प्रारम्भ होता है और कोई किनारा नहीं होता है, प्रत्येक शीर्ष पर दो कंकड़ रखे जाते हैं, और आरेख़ के सभी किनारों को बनाने के लिए निम्नलिखित दो प्रकार के चरणों का अनुक्रम करता है:
-*यदि कोई किनारा शीर्ष से इंगित करता है {{mvar|u}} अधिक से अधिक एक कंकड़ से दूसरे शीर्ष पर {{mvar|v}} कम से कम एक कंकड़ के साथ, एक कंकड़ ले जाएँ {{mvar|v}} को {{mvar|u}} और किनारे को उलट दें।
+* किसी भी दो शीर्ष को जोड़ने वाला एक नया निर्देशित किनारा बनाएं जिसमें दोनों में दो कंकड़ हों, और एक कंकड़ को नए शीर्ष के शुरुआती शीर्ष से हटा दें।
-यदि इन संक्रियाओं का उपयोग दिए गए ग्राफ के [[अभिविन्यास (ग्राफ सिद्धांत)]] के निर्माण के लिए किया जा सकता है, तो यह अनिवार्य रूप से (2,3)-विरल और इसके विपरीत है।
+*यदि कोई किनारा शीर्ष से इंगित करता है {{mvar|u}} अधिक से अधिक एक कंकड़ से दूसरे शीर्ष पर {{mvar|v}} कम से कम एक कंकड़ के साथ, एक कंकड़ ले जाएँ {{mvar|v}} को {{mvar|u}} और शीर्ष को उलट दें।
-हालांकि, तेज एल्गोरिदम संभव है, समय में चल रहा है <math>O(n^{3/2}\sqrt{\log n})</math>, परीक्षण के आधार पर कि क्या दिए गए ग्राफ के एक किनारे को दोगुना करने से एक मल्टीग्राफ परिणाम होता है जो (2,2) -टाइट है (समतुल्य रूप से, क्या इसे दो किनारे-विच्छेद फैले हुए पेड़ों में विघटित किया जा सकता है) और फिर इस अपघटन का उपयोग करके जाँच करें कि क्या दिया गया ग्राफ लैमन ग्राफ है।<ref>{{citation
+यदि इन परिचालनों का उपयोग दिए गए आरेख के [[अभिविन्यास (ग्राफ सिद्धांत)|अभिविन्यास (आरेख सिद्धांत)]] के निर्माण के लिए किया जा सकता है, तो यह अनिवार्य रूप से (2,3)-विरल और इसके विपरीत है। हालांकि, तेजी से एल्गोरिदम संभव है, समय <math>O(n^{3/2}\sqrt{\log n})</math> में चल रहा है, परीक्षण के आधार पर कि क्या दिए गए आरेख के एक शीर्ष को दोगुना करने से मल्टीआरेख में परिणाम मिलता है (2,2) -टाइट (समतुल्य रूप से, क्या इसे दो शीर्ष-विच्छेद फैले हुए पेड़ों में विघटित किया जा सकता है) और फिर इस अपघटन का उपयोग करके यह जांचने के लिए कि क्या दिया गया आरेख लैमन आरेख है।<ref>{{citation
   | last1 = Daescu | first1 = O.
   | last2 = Kurdia | first2 = A.
@@ Line 77: / Line 63: @@
   | title = Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09)
   | year = 2009| arxiv = 0801.2404
-  }}.</ref> नेटवर्क प्रवाह समस्या तकनीकों का परीक्षण करने के लिए इस्तेमाल किया जा सकता है कि समय में एक प्लानर ग्राफ लैमन ग्राफ है या नहीं <math>O(n\log^3 n)</math>.<ref>{{citation
+  }}.</ref> नेटवर्क प्रवाह तकनीकों का उपयोग यह परीक्षण करने के लिए किया जा सकता है कि क्या एक तलीय आरेख समय में अधिक तेजी से एक लैमन आरेख है <math>O(n\log^3 n)</math><ref>{{citation
   | last1 = Rollin | first1 = Jonathan
   | last2 = Schlipf | first2 = Lena
@@ Line 95: / Line 81: @@
   | volume = 144
   | year = 2019}}</ref>
 == हेनबर्ग निर्माण ==
-[[File:Henneberg construction of Moser spindle.svg|thumb|240px|मोजर स्पिंडल का हेन्नेबर्ग निर्माण]]लैमन और गीरिंगर के काम से पहले, {{ill|Lebrecht Henneberg|de}} द्वि-आयामी न्यूनतम कठोर रेखांकन (अर्थात, लैमन रेखांकन) को एक अलग तरीके से चित्रित करता है।<ref>{{citation
+[[File:Henneberg construction of Moser spindle.svg|thumb|240px|मोजर स्पिंडल का हेन्नेबर्ग निर्माण]]लैमन और गीरिंगर के काम से पहले, {{ill|Lebrecht Henneberg|de}} ने द्वि-आयामी न्यूनतम जटिल आरेख (यानी, लैमन आरेख) को एक अलग तरीके से चित्रित किया। <ref>{{citation
   | last = Henneberg | first = L.
   | location = Leipzig
   | title = Die graphische Statik der starren Systeme
-  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम कठोर रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक किनारे से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:
+  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम जटिल रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक शीर्ष से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:
-# ग्राफ़ में एक नया शीर्ष जोड़ें, किनारों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
+# आरेख़ में एक नया शीर्ष जोड़ें, किनारों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
-# ग्राफ़ के एक किनारे को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।
+# आरेख़ के एक शीर्ष को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।
-इन परिचालनों का एक क्रम जो एक दिए गए ग्राफ को बनाता है, उसे ग्राफ के हेनेबर्ग निर्माण के रूप में जाना जाता है।
+इन परिचालनों का एक क्रम जो एक दिए गए आरेख को बनाता है, उसे आरेख के हेनेबर्ग निर्माण के रूप में जाना जाता है। उदाहरण के लिए, त्रिभुज बनाने के लिए पहले ऑपरेशन का उपयोग करके पूर्ण द्विदलीय आरेख K3,3 का गठन किया जा सकता है और फिर त्रिकोण के प्रत्येक शीर्ष को उप-विभाजित करने के लिए दूसरा ऑपरेशन लागू किया जा सकता है और प्रत्येक उपखंड बिंदु को विपरीत त्रिभुज शीर्ष से जोड़ा जा सकता है।
-उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ ''K''<sub>3,3</sub> एक त्रिकोण बनाने के लिए पहले ऑपरेशन का उपयोग करके बनाया जा सकता है और फिर त्रिकोण के प्रत्येक किनारे को उपविभाजित करने के लिए दूसरा ऑपरेशन लागू करना और प्रत्येक उपखंड बिंदु को विपरीत त्रिकोण के शीर्ष से जोड़ना।
 ==संदर्भ==

Anonymous

Search

लामन आरेख़: Difference between revisions

Namespaces

More

Page actions

Revision as of 17:29, 15 May 2023

Contents

जटिलता

समतलता

विरलता

हेनबर्ग निर्माण

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

लामन आरेख़: Difference between revisions

Revision as of 17:29, 15 May 2023

जटिलता

समतलता

विरलता

हेनबर्ग निर्माण

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories