लामन आरेख़

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

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

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

जटिलता

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

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

समतलता

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

विरलता

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

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

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

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

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

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

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

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

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