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

Latest revision as of 14:43, 29 August 2023

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

Error creating thumbnail:

पूर्ण द्वितलीय आरेख K₃,₃ एक गैर-तलीय लामन आरेख है।

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

जटिलता

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

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

समतलता

अंकित छद्म त्रिभुज आरेख़ एक तलीय सीधी रेखा आरेखण है। जिसमें एक विशेष गुण हैं कि इसकी बाहरी आकृति उत्तल होती है तथा प्रत्येक घिरा हुआ फलक एक छद्म त्रिभुज है। एक बहुभुज जिसमें केवल तीन उत्तल शीर्ष होते हैं और शीर्षों की घटना प्रत्येक शीर्ष पर होती है। 180 डिग्री से कम का कोण अंकित छद्म त्रिभुज के रूप में खींचे जा सकने वाले आरेख़ वास्तव में तलीय लामन आरेख़ होते हैं।^[2] हालाँकि, लामन आरेख़ में तलीय अंतःस्थापन होता हैं जो छद्म त्रिभुज नहीं होता हैं और ये ऐसे लामन आरेख़ होते हैं जो यूटिलिटी आरेख़ K₃,₃ की तरह तलीय नहीं होते हैं।

विरलता

ली & स्ट्रेनु (2008) और स्ट्रेनु & थेरान (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]

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

Error creating thumbnail:

मोजर धुरी का हेन्नेबर्ग निर्माण

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

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

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

संदर्भ

↑ 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</sub>,<sub>3</sub> एक गैर-तलीय लामन आरेख है।
- | last = Laman | first = G. | authorlink = Gerard Laman
- | doi = 10.1007/BF01534980
+]]आरेख़ सिद्धांत में '''लामन आरेख़''' (लामन ग्राफ) विरल आरेख़ का एक समूह है जो समतल में छड़ और युग्म की न्यूनतम जटिल प्रणाली का वर्णन करता है। औपचारिक रूप से लामन आरेख़ <math>n</math> शीर्षों पर एक आरेख़ होता है जैसे कि सभी k के लिए प्रत्येक k कोणबिंदु उपआरेख में अधिकतम 2k − 3 शीर्ष होते हैं और ऐसे ही संपूर्ण आरेख़ में 2n − 3 शीर्ष होते हैं। लामन आरेख का नाम [[एम्स्टर्डम विश्वविद्यालय]] के [[जेरार्ड पेज|जेरार्ड]] लामन के नाम पर रखा गया है जिन्होंने 1970 में जटिल तलीय संरचनाओं को चित्रित करने के लिए उनका उपयोग किया था। हालाँकि इस विधि का वर्णन 1927 में [[हिल्डा जिरिंगर]] द्वारा पहले ही खोजा जा चुका था।<ref>{{citation
- | 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 11: @@
   | year = 1927
   | doi = 10.1002/zamm.19270070107 | bibcode = 1927ZaMM....7...58P }}.</ref>
+== जटिलता ==
+[[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में लामन आरेख उत्पन्न होते हैं यदि कोई यू[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में एक लामन आरेख के शीर्ष को [[सामान्य स्थिति]] में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है। यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करते है एक आरेख इस अर्थ में जटिल होता है यदि और केवल यदि उसके पास एक लामन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लामन आरेख सामान्यतः न्यूनतम जटिल आरेख होते हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।
+यदि समतल में <math>n</math> बिंदु दिए गए हैं, तो उनके नियोजन में स्वतंत्रता की 2<math>n</math> डिग्री होती है अर्थात प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन सहज रूप से एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है इसलिए लामन आरेख में (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 36: @@
   | year = 2005
   | arxiv = math/0307347
-  | s2cid = 38637747 }}.</ref> हालाँकि, लैमन ग्राफ़ में प्लानर एम्बेडिंग होते हैं जो स्यूडोट्रायंगुलेशन नहीं होते हैं, और ऐसे लैमन ग्राफ़ होते हैं जो प्लानर नहीं होते हैं, जैसे कि [[ उपयोगिता ग्राफ ]]़ K<sub>3,3</sub>.
+  | s2cid = 38637747 }}.</ref> हालाँकि, लामन आरेख़ में तलीय अंतःस्थापन होता हैं जो छद्म त्रिभुज नहीं होता हैं और ये ऐसे लामन आरेख़ होते हैं जो यूटिलिटी आरेख़ ''K<sub>3</sub>'',<sub>3</sub> की तरह तलीय नहीं होते हैं।
 == विरलता ==
-{{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|ली|स्ट्रेनु|2008}} और {{harvtxt|स्ट्रेनु|थेरान|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 52: @@
   | 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 65: @@
   | 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 83: @@
   | 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|लेब्रेक्ट हेनेबर्ग|डी}} ने द्वि-आयामी न्यूनतम जटिल आरेख (अर्थात, लामन आरेख) को एक अलग तरीके से चित्रित किया है। <ref>{{citation
   | last = Henneberg | first = L.
   | location = Leipzig
   | title = Die graphische Statik der starren Systeme
-  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम कठोर रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक किनारे से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:
+  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम जटिल आरेख वास्तव में ऐसे आरेख हैं जो एक शीर्ष से निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा प्राप्त किए जा सकते हैं।
-# ग्राफ़ में एक नया शीर्ष जोड़ें, किनारों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
+# आरेख़ में एक नया शीर्ष जोड़ें और शीर्षों के साथ इसे पहले से सम्मिलित दो शीर्षों से जोड़ें।
-# ग्राफ़ के एक किनारे को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।
+# आरेख़ के एक शीर्ष को उप-विभाजित करें और नवगठित शीर्ष को एक तीसरे पहले से सम्मिलित शीर्ष से जोड़ने वाला शीर्ष जोड़ें।
-इन परिचालनों का एक क्रम जो एक दिए गए ग्राफ को बनाता है, उसे ग्राफ के हेनेबर्ग निर्माण के रूप में जाना जाता है।
+इन परिचालनों का एक क्रम जो दिए गए आरेख को बनाता है उसे आरेख के हेनेबर्ग निर्माण के रूप में जाना जाता है। उदाहरण के लिए, त्रिभुज बनाने के लिए पहले एक संक्रियक का उपयोग करके पूर्ण द्वितलीय आरेख ''K<sub>3</sub>'',<sub>3</sub> का गठन किया जा सकता है और फिर त्रिकोण के प्रत्येक शीर्ष को उप-विभाजित करने के लिए दूसरा संक्रियक को प्रयुक्त किया जा सकता है प्रत्येक उपखंड बिंदु को विपरीत त्रिभुज शीर्ष से जोड़ा जा सकता है।
-उदाहरण के लिए, पूर्ण द्विदलीय ग्राफ ''K''<sub>3,3</sub> एक त्रिकोण बनाने के लिए पहले ऑपरेशन का उपयोग करके बनाया जा सकता है और फिर त्रिकोण के प्रत्येक किनारे को उपविभाजित करने के लिए दूसरा ऑपरेशन लागू करना और प्रत्येक उपखंड बिंदु को विपरीत त्रिकोण के शीर्ष से जोड़ना।
 ==संदर्भ==
 {{reflist}}
-[[Category: ग्राफ परिवार]] [[Category: ज्यामितीय रेखांकन]] [[Category: कठोरता का गणित]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 05/05/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:कठोरता का गणित]]
+[[Category:ग्राफ परिवार]]
+[[Category:ज्यामितीय रेखांकन]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 14:43, 29 August 2023

Contents

जटिलता

समतलता

विरलता

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

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 14:43, 29 August 2023

जटिलता

समतलता

विरलता

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

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories