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

From Vigyanwiki
No edit summary
No edit summary
Line 12: Line 12:
[[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में लैमन आरेख उत्पन्न होते हैं यदि कोई यू[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में एक लैमन आरेख के शीर्ष को [[सामान्य स्थिति]] में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करता है एक आरेख इस अर्थ में जटिलहोता है यदि और केवल यदि उसके पास एक लैमन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लैमन आरेख सामान्यतः न्यूनतम जटिल आरेख हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।
[[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में लैमन आरेख उत्पन्न होते हैं यदि कोई यू[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में एक लैमन आरेख के शीर्ष को [[सामान्य स्थिति]] में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करता है एक आरेख इस अर्थ में जटिलहोता है यदि और केवल यदि उसके पास एक लैमन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लैमन आरेख सामान्यतः न्यूनतम जटिल आरेख हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।


'''यदि समतल में 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
  | last1 = Haas | first1 = Ruth | author1-link = Ruth Haas
  | last2 = Orden | first2 = David
  | last2 = Orden | first2 = David
Line 34: Line 34:
  | year = 2005
  | year = 2005
  | arxiv = math/0307347
  | arxiv = math/0307347
  | s2cid = 38637747 }}.</ref> हालाँकि, लैमन आरेख़ में तलीय एम्बेडिंग होते हैं जो स्यूडोट्रायंगुलेशन नहीं होते हैं और ऐसे लैमन आरेख़ होते हैं जो तलीय नहीं होते हैं, जैसे कि यूटिलिटी आरेख़ K3,3।
  | s2cid = 38637747 }}.</ref> हालाँकि, लैमन आरेख़ में तलीय अंतःस्थापन होता हैं जो छद्म त्रिभुज नहीं होता हैं और ये ऐसे लैमन आरेख़ होते हैं जो यूटिलिटी आरेख़ ''K<sub>3</sub>'',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)-विरल आरेख हैं। विरल आरेख के अन्य महत्वपूर्ण समूहों का वर्णन करने के लिए एक ही संकेतन का उपयोग किया जा सकता है, जिसमें पेड़, स्यूडोफॉरेस्ट, और बाउंडेड आर्बरसिटी के आरेख सम्मिलित हैं।<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
  | last1 = Lee | first1 = Audrey
  | last2 = Streinu | first2 = Ileana | author2-link = Ileana Streinu
  | last2 = Streinu | first2 = Ileana | author2-link = Ileana Streinu
Line 51: Line 51:
  }}.</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>
  }}.</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>


इस चरित्र-चित्रण के आधार पर, समय {{math|''O''(''n''<sup>2</sup>)}} में {{mvar|n}}-वर्टेक्स लैमन आरेख को पहचानना संभव है, एक "कंकड़ खेल" का अनुकरण करके, जो {{mvar|n}} शीर्ष वाले आरेख से प्रारम्भ होता है और कोई किनारा नहीं होता है, प्रत्येक शीर्ष पर दो कंकड़ रखे जाते हैं, और आरेख़ के सभी किनारों को बनाने के लिए निम्नलिखित दो प्रकार के चरणों का अनुक्रम करता है:
इस चरित्र-चित्रण के आधार पर समय {{math|''O''(''n''<sup>2</sup>)}} में {{mvar|n}} शीर्ष लैमन आरेख को पहचानना संभव है एक "कंकड़ खेल" का अनुकरण करके {{mvar|n}} शीर्ष वाले आरेख को प्रारम्भ करते है जिसमे कोई शीर्ष नहीं होता है प्रत्येक शीर्ष पर दो कंकड़ रखे जाते हैं और आरेख़ के सभी शीर्षों को बनाने के लिए निम्नलिखित दो प्रकार के चरणों का अनुक्रम किया जाता है।
* किसी भी दो शीर्ष को जोड़ने वाला एक नया निर्देशित किनारा बनाएं जिसमें दोनों में दो कंकड़ हों, और एक कंकड़ को नए शीर्ष के शुरुआती शीर्ष से हटा दें।
* किसी भी दो शीर्ष को जोड़ने वाला एक नया निर्देशित शीर्ष बनाएं जिसमें दोनों में दो कंकड़ हों और एक कंकड़ को नए शीर्ष के प्रारम्भ शीर्ष से हटा दें।
*यदि कोई किनारा शीर्ष से इंगित करता है {{mvar|u}} अधिक से अधिक एक कंकड़ से दूसरे शीर्ष पर {{mvar|v}} कम से कम एक कंकड़ के साथ, एक कंकड़ ले जाएँ {{mvar|v}} को {{mvar|u}} और शीर्ष को उलट दें।
*यदि कोई किनारा शीर्ष से इंगित करता है तब {{mvar|u}} अधिक से अधिक एक कंकड़ से दूसरे शीर्ष {{mvar|v}} प कम से कम एक कंकड़ के साथ एक कंकड़ ले जाएँ और {{mvar|v}} को {{mvar|u}} शीर्ष पर रख दें।
यदि इन परिचालनों का उपयोग दिए गए आरेख के [[अभिविन्यास (ग्राफ सिद्धांत)|अभिविन्यास (आरेख सिद्धांत)]] के निर्माण के लिए किया जा सकता है, तो यह अनिवार्य रूप से (2,3)-विरल और इसके विपरीत है। हालांकि, तेजी से एल्गोरिदम संभव है, समय <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.
  | last1 = Daescu | first1 = O.
  | last2 = Kurdia | first2 = A.
  | last2 = Kurdia | first2 = A.
Line 87: Line 87:
  | title = Die graphische Statik der starren Systeme
  | title = Die graphische Statik der starren Systeme
  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम जटिल रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक शीर्ष से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:
  | year = 1911}}</ref> हेन्नेबर्ग ने दिखाया कि दो या दो से अधिक शीर्षों पर कम से कम जटिल रेखांकन वास्तव में ऐसे रेखांकन हैं जो एक शीर्ष से प्राप्त किए जा सकते हैं, निम्नलिखित दो प्रकार के संचालन के अनुक्रम द्वारा:
# आरेख़ में एक नया शीर्ष जोड़ें, किनारों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
# आरेख़ में एक नया शीर्ष जोड़ें, शीर्षों के साथ इसे पहले से मौजूद दो शीर्षों से जोड़ें।
# आरेख़ के एक शीर्ष को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।
# आरेख़ के एक शीर्ष को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।


Revision as of 21:53, 15 May 2023

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

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

जटिलता

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

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

समतलता

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

विरलता

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

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

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

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

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

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

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

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

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

संदर्भ

  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)
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लामन_आरेख़&oldid=162012’