लामन आरेख़

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

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

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

जटिलता

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

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

समतलता

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

विरलता

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

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

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

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

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

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