लामन आरेख़: Difference between revisions
m (5 revisions imported from alpha:लमान_ग्राफ) |
No edit summary |
||
| (2 intermediate revisions by 2 users not shown) | |||
| 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</sub>,<sub>3</sub> एक गैर-तलीय | [[File:Biclique K 3 3.svg|thumb|150px|[[पूर्ण द्विदलीय ग्राफ|पूर्ण द्वितलीय आरेख]] K<sub>3</sub>,<sub>3</sub> एक गैर-तलीय लामन आरेख है। | ||
]]आरेख़ सिद्धांत में ''' | ]]आरेख़ सिद्धांत में '''लामन आरेख़''' (लामन ग्राफ) विरल आरेख़ का एक समूह है जो समतल में छड़ और युग्म की न्यूनतम जटिल प्रणाली का वर्णन करता है। औपचारिक रूप से लामन आरेख़ <math>n</math> शीर्षों पर एक आरेख़ होता है जैसे कि सभी k के लिए प्रत्येक k कोणबिंदु उपआरेख में अधिकतम 2k − 3 शीर्ष होते हैं और ऐसे ही संपूर्ण आरेख़ में 2n − 3 शीर्ष होते हैं। लामन आरेख का नाम [[एम्स्टर्डम विश्वविद्यालय]] के [[जेरार्ड पेज|जेरार्ड]] लामन के नाम पर रखा गया है जिन्होंने 1970 में जटिल तलीय संरचनाओं को चित्रित करने के लिए उनका उपयोग किया था। हालाँकि इस विधि का वर्णन 1927 में [[हिल्डा जिरिंगर]] द्वारा पहले ही खोजा जा चुका था।<ref>{{citation | ||
| last = Pollaczek‐Geiringer | first = Hilda | authorlink = Hilda Geiringer | | last = Pollaczek‐Geiringer | first = Hilda | authorlink = Hilda Geiringer | ||
| issue = 1 | | issue = 1 | ||
| Line 12: | Line 12: | ||
| doi = 10.1002/zamm.19270070107 | bibcode = 1927ZaMM....7...58P }}.</ref> | | doi = 10.1002/zamm.19270070107 | bibcode = 1927ZaMM....7...58P }}.</ref> | ||
== जटिलता == | == जटिलता == | ||
[[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में | [[कठोरता सिद्धांत (संरचनात्मक)|जटिलता सिद्धांत]] में लामन आरेख उत्पन्न होते हैं यदि कोई यू[[यूक्लिडियन विमान|यूक्लिडियन समतल]] में एक लामन आरेख के शीर्ष को [[सामान्य स्थिति]] में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है। यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करते है एक आरेख इस अर्थ में जटिल होता है यदि और केवल यदि उसके पास एक लामन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लामन आरेख सामान्यतः न्यूनतम जटिल आरेख होते हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं। | ||
यदि समतल में <math>n</math> बिंदु दिए गए हैं, तो उनके नियोजन में स्वतंत्रता की 2<math>n</math> डिग्री होती है अर्थात प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन सहज रूप से एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है इसलिए | यदि समतल में <math>n</math> बिंदु दिए गए हैं, तो उनके नियोजन में स्वतंत्रता की 2<math>n</math> डिग्री होती है अर्थात प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन सहज रूप से एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है इसलिए लामन आरेख में (2n - 3) शीर्ष प्रारंभिक बिंदु नियोजन की स्वतंत्रता 2n डिग्री को जटिल आरेख की स्वतंत्रता को तीन डिग्री तक कम कर देते हैं। हालांकि 2n − 3 शीर्षों वाला प्रत्येक आरेख जटिल नहीं होता है लामन आरेख की परिभाषा में यह शर्त है कि किसी भी उप आरेख में बहुत अधिक शीर्ष नहीं हो सकते हैं। यह सुनिश्चित करता है कि प्रत्येक शीर्ष स्वतंत्रता की कुल संख्या को कम करने में योगदान देता है और यह एक उप आरेख के भीतर नष्ट नहीं होता है जो पहले से ही अपने अन्य शीर्षों के कारण जटिल होता है। | ||
== समतलता == | == समतलता == | ||
अंकित छद्म त्रिभुज आरेख़ एक तलीय सीधी रेखा आरेखण है। जिसमें एक विशेष गुण हैं कि इसकी बाहरी आकृति उत्तल होती है तथा प्रत्येक घिरा हुआ फलक एक छद्म त्रिभुज है। एक बहुभुज जिसमें केवल तीन उत्तल शीर्ष होते हैं और शीर्षों की घटना प्रत्येक शीर्ष पर होती है। 180 डिग्री से कम का कोण अंकित छद्म त्रिभुज के रूप में खींचे जा सकने वाले आरेख़ वास्तव में तलीय | अंकित छद्म त्रिभुज आरेख़ एक तलीय सीधी रेखा आरेखण है। जिसमें एक विशेष गुण हैं कि इसकी बाहरी आकृति उत्तल होती है तथा प्रत्येक घिरा हुआ फलक एक छद्म त्रिभुज है। एक बहुभुज जिसमें केवल तीन उत्तल शीर्ष होते हैं और शीर्षों की घटना प्रत्येक शीर्ष पर होती है। 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 36: | Line 36: | ||
| year = 2005 | | year = 2005 | ||
| arxiv = math/0307347 | | arxiv = math/0307347 | ||
| s2cid = 38637747 }}.</ref> हालाँकि, | | s2cid = 38637747 }}.</ref> हालाँकि, लामन आरेख़ में तलीय अंतःस्थापन होता हैं जो छद्म त्रिभुज नहीं होता हैं और ये ऐसे लामन आरेख़ होते हैं जो यूटिलिटी आरेख़ ''K<sub>3</sub>'',<sub>3</sub> की तरह तलीय नहीं होते हैं। | ||
== विरलता == | == विरलता == | ||
{{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> शीर्ष होते हैं। इस प्रकार उनके अंकन में | {{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 53: | Line 53: | ||
}}.</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}} शीर्ष | इस चरित्र-चित्रण के आधार पर समय {{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) समय समतुल्य रूप से क्या इसे दो शीर्ष-विच्छेद विस्तृत आरेख में विघटित किया जा सकता है और फिर इस अपघटन का उपयोग करके यह जांचने के लिए कि क्या दिया गया आरेख | यदि इन परिचालनों का उपयोग दिए गए आरेख के [[अभिविन्यास (ग्राफ सिद्धांत)|अभिविन्यास (आरेख सिद्धांत)]] के निर्माण के लिए किया जा सकता है तो यह अनिवार्य रूप से (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 65: | Line 65: | ||
| title = Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09) | | title = Proc. 42nd Hawaii International Conference on System Sciences (HICSS '09) | ||
| year = 2009| arxiv = 0801.2404 | | year = 2009| arxiv = 0801.2404 | ||
}}.</ref> नेटवर्क प्रवाह तकनीकों का उपयोग यह परीक्षण करने के लिए किया जा सकता है कि क्या एक तलीय आरेख समय में अधिक तीव्र | }}.</ref> नेटवर्क प्रवाह तकनीकों का उपयोग यह परीक्षण करने के लिए किया जा सकता है कि क्या एक तलीय आरेख समय में अधिक तीव्र लामन आरेख <math>O(n\log^3 n)</math> है। <ref>{{citation | ||
| last1 = Rollin | first1 = Jonathan | | last1 = Rollin | first1 = Jonathan | ||
| last2 = Schlipf | first2 = Lena | | last2 = Schlipf | first2 = Lena | ||
| Line 84: | Line 84: | ||
| year = 2019}}</ref> | | year = 2019}}</ref> | ||
== हेनबर्ग निर्माण == | == हेनबर्ग निर्माण == | ||
[[File:Henneberg construction of Moser spindle.svg|thumb|240px|मोजर धुरी का हेन्नेबर्ग निर्माण]] | [[File:Henneberg construction of Moser spindle.svg|thumb|240px|मोजर धुरी का हेन्नेबर्ग निर्माण]]लामन और गीरिंगर के कार्य से पहले, {{ill|लेब्रेक्ट हेनेबर्ग|डी}} ने द्वि-आयामी न्यूनतम जटिल आरेख (अर्थात, लामन आरेख) को एक अलग तरीके से चित्रित किया है। <ref>{{citation | ||
| last = Henneberg | first = L. | | last = Henneberg | first = L. | ||
| location = Leipzig | | location = Leipzig | ||
| Line 96: | Line 96: | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
[[Category:Created On 05/05/2023]] | [[Category:Created On 05/05/2023]] | ||
[[Category:Vigyan Ready]] | [[Category:Machine Translated Page]] | ||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:कठोरता का गणित]] | |||
[[Category:ग्राफ परिवार]] | |||
[[Category:ज्यामितीय रेखांकन]] | |||
Latest revision as of 14:43, 29 August 2023
आरेख़ सिद्धांत में लामन आरेख़ (लामन ग्राफ) विरल आरेख़ का एक समूह है जो समतल में छड़ और युग्म की न्यूनतम जटिल प्रणाली का वर्णन करता है। औपचारिक रूप से लामन आरेख़ शीर्षों पर एक आरेख़ होता है जैसे कि सभी k के लिए प्रत्येक k कोणबिंदु उपआरेख में अधिकतम 2k − 3 शीर्ष होते हैं और ऐसे ही संपूर्ण आरेख़ में 2n − 3 शीर्ष होते हैं। लामन आरेख का नाम एम्स्टर्डम विश्वविद्यालय के जेरार्ड लामन के नाम पर रखा गया है जिन्होंने 1970 में जटिल तलीय संरचनाओं को चित्रित करने के लिए उनका उपयोग किया था। हालाँकि इस विधि का वर्णन 1927 में हिल्डा जिरिंगर द्वारा पहले ही खोजा जा चुका था।[1]
जटिलता
जटिलता सिद्धांत में लामन आरेख उत्पन्न होते हैं यदि कोई यूयूक्लिडियन समतल में एक लामन आरेख के शीर्ष को सामान्य स्थिति में रखता है तो सामान्य रूप से सभी बिंदुओं की एक साथ निरंतर गति नहीं होती है। यूक्लिडियन सर्वांगसमता के अतिरिक्त जो सभी आरेख शीर्ष की लंबाई को संरक्षित करते है एक आरेख इस अर्थ में जटिल होता है यदि और केवल यदि उसके पास एक लामन उप आरेख होता है जो उसके सभी शीर्षों को विस्तृत करता है। इस प्रकार लामन आरेख सामान्यतः न्यूनतम जटिल आरेख होते हैं और ये द्वि-आयामी जटिलता की संरचना के आधार बनाते हैं।
यदि समतल में बिंदु दिए गए हैं, तो उनके नियोजन में स्वतंत्रता की 2 डिग्री होती है अर्थात प्रत्येक बिंदु में दो स्वतंत्र निर्देशांक होते हैं लेकिन एक जटिल आरेख में स्वतंत्रता की केवल तीन डिग्री होती है इसके एक शीर्ष की स्थिति और उस शीर्ष के चारों ओर शेष आरेख़ का घूर्णन सहज रूप से एक आरेख़ में निश्चित लंबाई के शीर्ष को जोड़ने से इसकी स्वतंत्रता की डिग्री की संख्या एक से कम हो जाती है इसलिए लामन आरेख में (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]
हेनबर्ग निर्माण
लामन और गीरिंगर के कार्य से पहले, लेब्रेक्ट हेनेबर्ग ने द्वि-आयामी न्यूनतम जटिल आरेख (अर्थात, लामन आरेख) को एक अलग तरीके से चित्रित किया है। [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)
