On Extremal Family Trees $(\mathcal{T}_n)_{n\geqslant 3}$ Beyond Caterpillars and Greedy Constructions

तकनीकी सारांश: कैटरपिलर और ग्रीडी निर्माणों से परे चरम पारिवारिक वृक्ष (Extremal Family Trees)

समस्या विवरण
यह शोध पत्र सभी $n \geq 3$ शीर्षों वाले वृक्षों के परिवार $\mathcal{T}_n$ पर सिग्मा सूचकांक ($\sigma$) के चरम गुणों की जांच करता है, जो ग्राफ अनियमितता का एक द्विघात माप (quadratic measure) है। सिग्मा सूचकांक को $\sigma(G) = \sum_{uv \in E(G)} (d_G(u) - d_G(v))^2$ के रूप में परिभाषित किया गया है। केंद्रीय चुनौती $\sigma$ के लिए सटीक सीमाएँ स्थापित करना और यह समझना है कि कौन सी संरचनात्मक श्रेणियाँ इन सीमाओं को प्राप्त करती हैं। विशेष रूप से, लेखक सभी वृक्षों पर $\sigma$ के वैश्विक न्यूनतम (global minimum) की तुलना कैटरपिलर वृक्षों और ग्रीडी वृक्षों (वे वृक्ष जो स्थानीय स्तर पर डिग्री असमानताओं को कम करने के लिए शीर्षों को जोड़कर बनाए जाते हैं) जैसे प्रतिबंधित उप-वर्गों में प्राप्त न्यूनतम मानों से करते हैं। अध्ययन यह भी seeks करता है कि क्या वे वृक्ष जो न तो कैटरपिलर हैं और न ही ग्रीडी वृक्ष, $\sigma$ के मानों को कैटरपिलर के न्यूनतम मान और वैश्विक न्यूनतम के बीच प्राप्त कर सकते हैं।

कार्यप्रणाली (Methodology)
लेखक संरचनात्मक ग्राफ सिद्धांत (structural graph theory) और संयोजन अनुकूलन (combinatorial optimization) के संयोजन का उपयोग करते हैं:

1. परिभाषाएं और पूर्ववृत्त: शोध पत्र कैटरपिलर वृक्षों (वे वृक्ष जहाँ पत्तियाँ हटाने पर एक पथ प्राप्त होता है) और ग्रीडी वृक्षों (वे वृक्ष जो एक नए शीर्ष को मौजूदा शीर्ष से जोड़ने की पुनरावृत्ति द्वारा निर्मित होते हैं जिसके पास वर्तमान में सबसे छोटा डिग्री है और जिसने अभी तक अपना लक्षित डिग्री प्राप्त नहीं किया है) की परिभाषाएँ स्थापित करता है।
2. रूपांतरण तर्क (Transformation Arguments): चरम गुणों को सिद्ध करने के लिए, लेखक 'एज-स्विचिंग' (edge-switching) संचालन का उपयोग करते हैं। वे प्रदर्शित करते हैं कि किसी भी गैर-ग्रीडी वृक्ष के लिए, एक विशिष्ट एज स्वैप (डिग्री क्रम का सम्मान करने के लिए शीर्षों को पुन: जोड़ने वाला) सिग्मा सूचकांक को सख्ती से कम कर देता है, जिससे यह सिद्ध होता है कि एक निश्चित डिग्री अनुक्रम के लिए ग्रीडी वृक्ष $\sigma$ को न्यूनतम करता है।
3. मामला विश्लेषण और आगमन (Case Analysis and Induction): शोध पत्र "समस्या 1" और "समस्या 2" द्वारा परिभाषित विशिष्ट वृक्ष संरचनाओं का विश्लेषण करता है। ये समस्याएँ एक केंद्रीय स्पाइन (spine) और विशिष्ट डिग्री बाधाओं के साथ पेंडेंट शीर्षों के कई स्तरों वाले वृक्षों को परिभाषित करती हैं (जैसे, प्रथम-स्तर के पेंडेंट की डिग्री $1+r$ है, द्वितीय-स्तर की $1+s$ है, आदि)।
4. सूत्रों का व्युत्पन्न (Derivation of Formulas): वृक्ष के स्तरों (स्पाइन-से-स्तर 1, स्तर 1-से-स्तर 2, आदि) के आधार पर किनारों (edges) को विभाजित करके, लेखक इन संरचित परिवारों के लिए $\sigma(T)$ के सटीक बीजगणितीय सूत्र व्युत्पन्न करते हैं। वे डिग्री अनुक्रमों के क्रम का विश्लेषण भी करते हैं ताकि कैटरपिलर वृक्षों के अधिकतम और न्यूनतम $\sigma$ मानों को निर्धारित किया जा सके।

प्रमुख योगदान और परिणाम

• ग्रीडी वृक्षों के चरम गुण: शोध पत्र सिद्ध करता है कि किसी भी ग्राफिक डिग्री अनुक्रम $D$ के लिए, ग्रीडी वृक्ष $T_D$, $D$ को साकार करने वाले सभी वृक्षों में सिग्मा सूचकांक को न्यूनतम करता है।
• कैटरपिलर वृक्षों की सीमाएँ: लेखक सिद्ध करते हैं कि कैटरपिलर वृक्ष पूरे परिवार $\mathcal{T}_n$ पर $\sigma$ के वैश्विक न्यूनतम को प्राप्त नहीं करते हैं।
• मध्यवर्ती चरम वृक्षों का अस्तित्व: एक महत्वपूर्ण खोज यह प्रमाण है कि ऐसे वृक्ष मौजूद हैं जो न तो कैटरपिलर हैं और न ही ग्रीडी वृक्ष, लेकिन जिनमें वैश्विक न्यूनतम और कैटरपिलर के न्यूनतम मान के बीच $\sigma$-मान प्राप्त करने की क्षमता है। यह वैश्विक न्यूनतम को कैटरपिलर न्यूनतम से अलग करने वाले एक गैर-रिक्त खुले अंतराल (non-empty open interval) को स्थापित करता है।
• संरचित वृक्षों के लिए सटीक सूत्र:
  • लेम्मा 3.2 और 3.3: शोध पत्र विविध डिग्री स्थितियों (रैखिक बनाम वर्गाकार डिग्री वृद्धि) के तहत तीन स्तरों के पेंडेंट वाले वृक्षों के लिए सिग्मा सूचकांक के स्पष्ट सूत्र व्युत्पन्न करता है।
  • प्रमेय 3.6: $n$ स्पाइन शीर्षों और $k$ स्तरों के पेंडेंट वाले वृक्षों के लिए एक सामान्य सूत्र प्रदान किया गया है, जो ब्रांचिंग कारकों के गुणनफल और स्तरों के बीच वर्गाकार डिग्री अंतर को ध्यान में रखता है।
  • प्रपोजिशन 3.3: एक कैटरपिलर वृक्ष $C(n, m)$ के सिग्मा सूचकांक के लिए एक सटीक सूत्र प्रदान किया गया है, जो $n=2$ और $n>2$ के मामलों में अंतर करता है।
• सीमाएँ (Bounds): शोध पत्र कैटरपिलर वृक्षों के सिग्मा सूचकांक के लिए औसत डिग्री और वर्गाकार डिग्री अंतर के योगों को शामिल करते हुए ऊपरी सीमाएँ प्रस्तुत करता है (प्रमेय 3.7)।

महत्व
शोध पत्र का दावा है कि यह $\sigma$ को न्यूनतम करने में गैर-कैटरपिलर, गैर-ग्रीडी वृक्षों की भूमिका के बारे में नई अंतर्दृष्टि प्रदान करता है। यह प्रदर्शित करके कि सिग्मा सूचकांक का वैश्विक न्यूनतम पूरे परिवार $\mathcal{T}_n$ में केवल कैटरपिलर या ग्रीडी वृक्षों तक सीमित नहीं है, यह कार्य चरम समस्याओं के लिए इन सामान्य वर्गों का उपयोग करने की संरचनात्मक सीमाओं को उजागर करता है। व्युत्पन्न सटीक सूत्र और सीमाएँ रैखिक और द्विघात अनियमितता मापों की तुलना करने के लिए एक एकीकृत विश्लेषणात्मक ढांचा प्रदान करती हैं। लेखक इन परिणामों को टोपोलॉजिकल इंडिसेस (topological indices), विशेष रूप से वृक्षों के संरचित परिवारों के अध्ययन के लिए एक आधारशिला के रूप में प्रस्तुत करते हैं, जो निश्चित आकार के उदाहरणों और सामान्य अनुक्रमों पर सत्यापित सटीक सूत्र प्रदान करते हैं।