लामन आरेख़

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

पूर्ण द्विदलीय ग्राफ K_3,3, एक गैर-प्लानर लैमन ग्राफ

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

हालाँकि, यह लक्षण वर्णन, 1927 में हिल्डा जिरिंगर द्वारा पहले ही खोजा जा चुका था।

कठोरता

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

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

समतलता

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

विरलता

Lee & Streinu (2008) और Streinu & Theran (2009) एक ग्राफ को होने के रूप में परिभाषित करें $(k,\ell )$-विरल अगर हर गैर-खाली सबग्राफ के साथ $n$ शिखरों में अधिकतम होता है $kn-\ell$ किनारों, और $(k,\ell )$-तंग अगर है $(k,\ell )$-विरल और बिल्कुल है $kn-\ell$ किनारों। इस प्रकार, उनके अंकन में, लैमन ग्राफ बिल्कुल (2,3)-तंग ग्राफ हैं, और लैमन ग्राफ के सबग्राफ बिल्कुल (2,3)-विरल ग्राफ हैं। विरल रेखांकन के अन्य महत्वपूर्ण परिवारों का वर्णन करने के लिए एक ही संकेतन का उपयोग किया जा सकता है, जिसमें पेड़ (ग्राफ सिद्धांत), seudoforest ्स और बंधे हुए वृक्षारोपण के ग्राफ शामिल हैं। इस लक्षण के आधार पर पहचान की जा सकती है n-वरटेक्स लैमन समय में रेखांकन करता है O(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. ग्राफ़ के एक किनारे को उप-विभाजित करें, और नवगठित शीर्ष को एक तीसरे पहले से मौजूद शीर्ष से जोड़ने वाला किनारा जोड़ें।

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