Treewidth
ग्राफ सिद्धांत में, एक दिशाहीन ग्राफ की त्रि-चौड़ाई एक पूर्णांक संख्या है जो अनौपचारिक रूप से निर्दिष्ट करती है कि ग्राफ एक वृक्ष होने से कितनी दूर है। सबसे छोटी त्रि-चौड़ाई 1 है; त्रि-चौड़ाई 1 वाले ग्राफ बिल्कुल पेड़ और जंगल हैं। अधिकतम 2 त्रि-चौड़ाई वाले ग्राफ श्रृंखला-समानांतर ग्राफ हैं। सटीक रूप से त्रि-चौड़ाई वाले अधिकतम ग्राफ को-ट्री कहा जाता है, और अधिक से अधिक त्रि-चौड़ाई वाले ग्राफ को आंशिक-ट्री कहा जाता है। कई अन्य अच्छी तरह से अध्ययन किए गए ग्राफ परिवारों में भी त्रि-चौड़ाई सीमित है। त्रि-चौड़ाई को औपचारिक रूप से कई समतुल्य तरीकों से परिभाषित किया जा सकता हैः ग्राफ के पेड़ के अपघटन में सबसे बड़े शीर्ष सेट के आकार के संदर्भ में, ग्राफ के कॉर्डल समापन में सबसे बड़े गुट के आकार के संदर्भ में, ग्राफ पर एक खोज-चोरी खेल के लिए रणनीति का वर्णन करने वाले एक आश्रय के अधिकतम क्रम के संदर्भ में, या एक ब्रैम्बल के अधिकतम क्रम के संदर्भ में, जुड़े हुए उपग्राफ का एक संग्रह जो सभी एक दूसरे को छूते हैं। त्रि-चौड़ाई का उपयोग आमतौर पर ग्राफ एल्गोरिदम के मानकीकृत जटिलता विश्लेषण में एक पैरामीटर के रूप में किया जाता है। कई एल्गोरिदम जो सामान्य ग्राफ के लिए एन. पी.-कठोर होते हैं, तब आसान हो जाते हैं जब त्रि-चौड़ाई एक स्थिरांक से घिरी होती है। त्रि-चौड़ाई की अवधारणा मूल रूप से आयाम के नाम से पेश की गई थी। बाद में इसे उन गुणों के आधार पर फिर से खोजा गया, जिन्हें यह एक अलग ग्राफ पैरामीटर, हैडविगर संख्या के साथ साझा करता है। बाद में इसे फिर से खोजा गया और तब से कई अन्य लेखकों द्वारा इसका अध्ययन किया गया है। परिभाषा ग्राफ का एक वृक्ष अपघटन नोड्स के साथ एक वृक्ष है, जहां प्रत्येक का एक उपसमुच्चय है, जो निम्नलिखित गुणों को संतुष्ट करता है (नोड शब्द का उपयोग के शीर्षों के साथ भ्रम से बचने के लिए के शीर्ष को संदर्भित करने के लिए किया जाता है): सभी सेटों का मिलन बराबर होता है। अर्थात्, प्रत्येक ग्राफ शीर्ष कम से कम एक ट्री नोड में निहित होता है। यदि और दोनों में एक शीर्ष होता है, तो और के बीच (अद्वितीय) पथ के सभी नोड्स भी होते हैं। समान रूप से, शीर्ष वाले ट्री नोड्स एक जुड़े हुए उप-वृक्ष का निर्माण करते हैं। ग्राफ में प्रत्येक किनारे के लिए, एक उपसमुच्चय है जिसमें और दोनों शामिल हैं। अर्थात्, ग्राफ में शीर्ष केवल तभी निकट होते हैं जब संबंधित उप-वृक्षों में एक समान नोड होता है। एक पेड़ के अपघटन की चौड़ाई उसके सबसे बड़े समूह माइनस एक का आकार है। ग्राफ की त्रि-चौड़ाई सभी संभावित वृक्ष अपघटनों के बीच न्यूनतम चौड़ाई है। इस परिभाषा में, एक पेड़ की त्रि-चौड़ाई को एक के बराबर बनाने के लिए सबसे बड़े समूह का आकार एक से कम किया जाता है। समान रूप से, की त्रि-चौड़ाई कॉर्डल ग्राफ में सबसे बड़े गुट के आकार से एक कम है जिसमें सबसे छोटी गुट संख्या होती है। इस गुट के आकार के साथ एक कॉर्डल ग्राफ प्रत्येक दो शीर्षों के बीच एक किनारे को जोड़कर प्राप्त किया जा सकता है जो दोनों कम से कम एक सेट से संबंधित हैं। त्रि-चौड़ाई को आश्रय के संदर्भ में भी चिह्नित किया जा सकता है, जो एक ग्राफ पर परिभाषित एक निश्चित खोज-चोरी खेल के लिए एक चोरी रणनीति का वर्णन करने वाले कार्य हैं। एक ग्राफ की त्रि-चौड़ाई केवल तभी होती है जब इसमें क्रम का एक हेवन होता है लेकिन कोई उच्च क्रम नहीं होता है, जहां एक हेवन ऑफ ऑर्डर एक ऐसा कार्य है जो प्रत्येक शीर्ष के प्रत्येक सेट को जुड़े हुए घटकों में से एक में मैप करता है और जो एकरसता गुण का पालन करता है। एक समान लक्षण वर्णन ब्रैम्बल का उपयोग करके भी किया जा सकता है, जुड़े हुए उपग्राफ के परिवार जो सभी एक दूसरे को छूते हैं (जिसका अर्थ है कि वे एक शीर्ष साझा करते हैं या एक किनारे से जुड़े होते हैं)। ब्रैम्बल का क्रम सबग्राफ के परिवार के लिए सबसे छोटा हिट सेट है, और ग्राफ की त्रि-चौड़ाई ब्रैम्बल के अधिकतम क्रम से एक कम है। उदाहरण प्रत्येक पूर्ण ग्राफ में त्रि-चौड़ाई होती है। यह कॉर्डल ग्राफ के संदर्भ में त्रि-चौड़ाई की परिभाषा का उपयोग करके सबसे आसानी से देखा जाता हैः पूरा ग्राफ पहले से ही कॉर्डल है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े गुट के आकार को कम नहीं किया जा सकता है। कम से कम दो शीर्षों के साथ एक जुड़े हुए ग्राफ में तीन चौड़ाई 1 होती है यदि और केवल अगर यह एक पेड़ है। एक पेड़ की त्रि-चौड़ाई एक होती है जो पूर्ण ग्राफ के लिए एक ही तर्क द्वारा होती है (अर्थात्, यह कॉर्डल है, और इसका अधिकतम गुट आकार दो होता है)। इसके विपरीत, यदि एक ग्राफ में एक चक्र है, तो ग्राफ के प्रत्येक कॉर्डल पूर्णता में कम से कम एक त्रिभुज शामिल होता है जिसमें चक्र के तीन लगातार शीर्ष होते हैं, जिससे यह पता चलता है कि इसकी त्रि-चौड़ाई कम से कम दो है। किसी भी निश्चित स्थिरांक के लिए, अधिकतम त्रि-चौड़ाई के ग्राफ को आंशिक-वृक्ष कहा जाता है। बंधे हुए त्रि-चौड़ाई वाले ग्राफ के अन्य परिवारों में कैक्टस ग्राफ, छद्म वन, श्रृंखला-समानांतर ग्राफ, बाहरी समतल ग्राफ, हेलिन ग्राफ और अपोलोनीयन नेटवर्क शामिल हैं। संरचित कार्यक्रमों के संकलन में उत्पन्न होने वाले नियंत्रण-प्रवाह ग्राफ में तीन चौड़ाई भी सीमित होती है, जो रजिस्टर आवंटन जैसे कुछ कार्यों को उन पर कुशलता से करने की अनुमति देता है। समतल ग्राफ में त्रि-चौड़ाई की सीमा नहीं होती है, क्योंकि ग्रिड ग्राफ एक समतल ग्राफ है जिसमें त्रि-चौड़ाई बिल्कुल होती है। इसलिए, यदि सीमित त्रि-चौड़ाई वाला एक लघु-बंद ग्राफ परिवार है, तो इसमें सभी समतल ग्राफ शामिल नहीं हो सकते हैं। इसके विपरीत, यदि कुछ समतल ग्राफ परिवार में ग्राफ के लिए एक मामूली के रूप में नहीं हो सकता है, तो एक स्थिरांक ऐसा है कि सभी ग्राफों में अधिक से अधिक त्रि-चौड़ाई हो। अर्थात्, निम्नलिखित तीन शर्तें एक-दूसरे के बराबर हैंः सीमित-त्रि-चौड़ाई ग्राफ का एक छोटा-बंद परिवार है; सीमित रूप से कई निषिद्ध नाबालिगों में से एक समतलीय है; एक छोटा-बंद ग्राफ परिवार है जिसमें सभी समतलीय ग्राफ शामिल नहीं हैं। निषिद्ध नाबालिग प्रत्येक सीमित मूल्य के लिए, अधिक से अधिक त्रि-चौड़ाई के ग्राफ को निषिद्ध नाबालिगों के एक सीमित समूह द्वारा चिह्नित किया जा सकता है। (अर्थात्, त्रि-चौड़ाई के किसी भी ग्राफ में सेट में एक ग्राफ को मामूली के रूप में शामिल किया जाता है।) निषिद्ध नाबालिगों के इन सेटों में से प्रत्येक में कम से कम एक समतल ग्राफ शामिल है। क्योंकि, अद्वितीय वर्जित लघु एक 3-वर्टेक्स चक्र ग्राफ है। क्योंकि, अद्वितीय वर्जित लघु 4-वर्टेक्स पूर्ण ग्राफ है। क्योंकि, चार वर्जित नाबालिग हैंः, ऑक्टाहेड्रॉन का ग्राफ, पंचकोणीय प्रिज्म ग्राफ और वैगनर ग्राफ। इनमें से दो पॉलीहेड्रल ग्राफ समतल हैं। के बड़े मूल्यों के लिए, वर्जित नाबालिगों की संख्या कम से कम उतनी ही तेजी से बढ़ती है जितनी कि के वर्गमूल की घातांक। हालाँकि, निषिद्ध नाबालिगों के आकार और संख्या पर ज्ञात ऊपरी सीमाएँ इस निचली सीमा की तुलना में बहुत अधिक हैं। एल्गोरिदम त्रि-चौड़ाई की गणना यह निर्धारित करने के लिए एन. पी.-पूर्ण है कि क्या दिए गए ग्राफ में दिए गए चर की अधिकतम त्रि-चौड़ाई है। हालांकि, जब कोई निश्चित स्थिरांक होता है, तो त्रि-चौड़ाई वाले ग्राफ को पहचाना जा सकता है, और रैखिक समय में उनके लिए एक चौड़ाई वृक्ष अपघटन का निर्माण किया जा सकता है। इस एल्गोरिथ्म की समय निर्भरता घातीय है। विशाल संख्या में क्षेत्रों में त्रि-चौड़ाई की भूमिकाओं के कारण, ग्राफ की त्रि-चौड़ाई की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक एल्गोरिदम विकसित किए गए थे। हाथ पर अनुप्रयोग के आधार पर, कोई भी बेहतर सन्निकटन अनुपात, या चालू समय में इनपुट के आकार या त्रि-चौड़ाई से बेहतर निर्भरता को पसंद कर सकता है। नीचे दी गई तालिका कुछ त्रि-चौड़ाई एल्गोरिदम का अवलोकन प्रदान करती है। यहाँ त्रि-चौड़ाई है और एक इनपुट ग्राफ के शीर्षों की संख्या है। प्रत्येक एल्गोरिदम समय पर सन्निकटन कॉलम में दी गई चौड़ाई का अपघटन करता है। उदाहरण के लिए, इन टाइम का एल्गोरिथ्म या तो अधिक से अधिक चौड़ाई के इनपुट ग्राफ के ट्री अपघटन का निर्माण करता है या रिपोर्ट करता है कि की त्रि-चौड़ाई से अधिक है। इसी तरह, इन टाइम का एल्गोरिथ्म या तो अधिक से अधिक चौड़ाई के इनपुट ग्राफ के ट्री अपघटन का निर्माण करता है या रिपोर्ट करता है कि की त्रि-चौड़ाई से अधिक है। इसे उसी चल रहे समय में सुधार दिया। यह ज्ञात नहीं है कि समतल ग्राफ की त्रि-चौड़ाई का निर्धारण एन. पी.-पूर्ण है या नहीं, या क्या उनकी त्रि-चौड़ाई की गणना बहुपद समय में की जा सकती है। व्यवहार में, का एक एल्गोरिथ्म 100 शीर्षों तक के ग्राफ की त्रि-चौड़ाई और 11 तक त्रि-चौड़ाई निर्धारित कर सकता है, जिससे इष्टतम त्रि-चौड़ाई के साथ इन ग्राफों का एक कॉर्डल समापन मिल सकता है। बड़े ग्राफ के लिए, कोई भी खोज-आधारित तकनीकों का उपयोग कर सकता है जैसे कि शाखा और बाध्य खोज (बीएनबी) और त्रि-चौड़ाई की गणना करने के लिए सर्वश्रेष्ठ-प्रथम खोज। ये एल्गोरिदम किसी भी समय होते हैं कि जब जल्दी बंद हो जाते हैं, तो वे त्रि-चौड़ाई पर एक ऊपरी सीमा का उत्पादन करेंगे। त्रि-चौड़ाई की गणना के लिए पहला बीएनबी एल्गोरिथ्म, जिसे क्विकबीबी एल्गोरिथ्म कहा जाता है, गोगेट और डेक्टर द्वारा प्रस्तावित किया गया था। चूँकि किसी भी बी. एन. बी. एल्गोरिदम की गुणवत्ता उपयोग की जाने वाली निचली सीमा की गुणवत्ता पर अत्यधिक निर्भर है, गोगेट और डेक्टर ने छोटी-न्यूनतम-चौड़ाई नामक त्रि-चौड़ाई पर निचली सीमा की गणना के लिए एक नए एल्गोरिदम का भी प्रस्ताव रखा। एक उच्च स्तर पर, लघु-न्यूनतम-चौड़ाई एल्गोरिथ्म इन तथ्यों को जोड़ता है कि एक ग्राफ की त्रि-चौड़ाई कभी भी इसकी न्यूनतम डिग्री से बड़ी नहीं होती है या त्रि-चौड़ाई पर कम सीमा प्राप्त करने के लिए इसकी लघु होती है। लघु-न्यूनतम-चौड़ाई एल्गोरिथ्म बार-बार न्यूनतम डिग्री शीर्ष और उसके पड़ोसियों में से एक के बीच एक किनारे को संकुचित करके एक लघु ग्राफ का निर्माण करता है, जब तक कि केवल एक शीर्ष न रह जाए। इन निर्मित नाबालिगों पर न्यूनतम डिग्री का अधिकतम ग्राफ की त्रि-चौड़ाई पर एक निचली सीमा होने की गारंटी है। डॉव और कॉर्फ ने बेस्ट-फर्स्ट सर्च का उपयोग करके क्विकबीबी एल्गोरिदम में सुधार किया। कुछ ग्राफों पर, यह सबसे अच्छा-पहला खोज एल्गोरिथ्म क्विकबीबी की तुलना में तेजी से परिमाण का एक क्रम है। छोटे त्रि-चौड़ाई वाले ग्राफ पर अन्य समस्याओं का समाधान 1970 के दशक की शुरुआत में, यह देखा गया था कि ग्राफ पर परिभाषित संयोजन अनुकूलन समस्याओं के एक बड़े वर्ग को गैर-क्रमिक गतिशील प्रोग्रामिंग द्वारा कुशलता से हल किया जा सकता है, जब तक कि ग्राफ में एक सीमित आयाम होता है, एक पैरामीटर जिसे त्रि-चौड़ाई के बराबर दिखाया जाता है। बाद में, कई लेखकों ने 1980 के दशक के अंत में स्वतंत्र रूप से देखा कि मनमाने ग्राफ के लिए एन. पी.-पूर्ण कई एल्गोरिदमिक समस्याओं को इन ग्राफों के वृक्ष-अपघटन का उपयोग करके बंधे हुए त्रि-चौड़ाई के ग्राफ के लिए गतिशील प्रोग्रामिंग द्वारा कुशलता से हल किया जा सकता है। उदाहरण के लिए, त्रि-चौड़ाई के ग्राफ को रंगने की समस्या को ग्राफ के वृक्ष अपघटन पर एक गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग करके हल किया जा सकता है। वृक्ष अपघटन के प्रत्येक समूह के लिए, और रंग वर्गों में शीर्षों के प्रत्येक विभाजन के लिए, एल्गोरिथ्म यह निर्धारित करता है कि क्या वह रंग मान्य है और वृक्ष अपघटन में सभी वंशज नोड्स तक बढ़ाया जा सकता है, एक समान प्रकार की जानकारी को जोड़कर और उन नोड्स पर संग्रहीत किया जा सकता है। परिणामी एल्गोरिथ्म समय में एक-वर्टेक्स ग्राफ का एक इष्टतम रंग पाता है, एक समय सीमा जो इस समस्या को निश्चित-पैरामीटर ट्रैक्टेबल बनाती है। कॉर्सेल की प्रमेय समस्याओं के एक बड़े वर्ग के लिए, वर्ग से एक समस्या को हल करने के लिए एक रैखिक समय एल्गोरिथ्म है यदि निरंतर बंधी त्रि-चौड़ाई के साथ एक वृक्ष-अपघटन प्रदान किया जाता है। विशेष रूप से, कोरसेल के प्रमेय में कहा गया है कि यदि एक ग्राफ समस्या को मोनैडिक सेकंड ऑर्डर लॉजिक का उपयोग करके ग्राफ के तर्क में व्यक्त किया जा सकता है, तो इसे बाउंडेड त्रि-चौड़ाई वाले ग्राफ पर रैखिक समय में हल किया जा सकता है। मोनैडिक सेकंड ऑर्डर लॉजिक ग्राफ गुणों का वर्णन करने के लिए एक भाषा है जो निम्नलिखित संरचनाओं का उपयोग करती हैः लॉजिक ऑपरेशन, जैसे सदस्यता परीक्षण, जैसे, शीर्षों पर मात्रा, किनारों, शीर्षों के सेट, और/या किनारों के सेट, जैसे,,, एडजसेंसी परीक्षण (एक अंतिम बिंदु है), और कुछ एक्सटेंशन जो अनुकूलन जैसी चीजों के लिए अनुमति देते हैं। उदाहरण के लिए ग्राफ के लिए 3-रंग की समस्या पर विचार करें। ग्राफ के लिए, यह समस्या पूछती है कि क्या प्रत्येक शीर्ष को 3 रंगों में से एक इस तरह से निर्दिष्ट करना संभव है कि किसी भी दो आसन्न शीर्षों को एक ही रंग निर्दिष्ट न किया जाए। इस समस्या को मोनडिक द्वितीय क्रम तर्क में निम्नानुसार व्यक्त किया जा सकता हैः, जहाँ, 3 रंगों में से प्रत्येक वाले शीर्षों के उपसमुच्चय का प्रतिनिधित्व करते हैं। इसलिए, कोरसेल के परिणामों से, 3-रंग की समस्या को एक ग्राफ के लिए रैखिक समय में हल किया जा सकता है, जो कि बंधी हुई स्थिर त्रि-चौड़ाई के वृक्ष-अपघटन को देखते हुए दिया गया है। संबंधित मापदंड पथ चौड़ाई ग्राफ की पथ चौड़ाई की परिभाषा वृक्ष अपघटन के माध्यम से त्रि चौड़ाई के समान है, लेकिन यह वृक्ष अपघटन तक सीमित है जिसमें अपघटन का अंतर्निहित वृक्ष एक पथ ग्राफ है। वैकल्पिक रूप से, पथ चौड़ाई को अंतराल ग्राफ से कॉर्डल ग्राफ से त्रि-चौड़ाई की परिभाषा के अनुरूप परिभाषित किया जा सकता है। नतीजतन, एक ग्राफ की पथ चौड़ाई हमेशा कम से कम अपनी त्रि-चौड़ाई जितनी बड़ी होती है, लेकिन यह केवल एक लघुगणक कारक द्वारा बड़ी हो सकती है। एक अन्य पैरामीटर, ग्राफ बैंडविड्थ, में उचित अंतराल ग्राफ से एक अनुरूप परिभाषा है, और कम से कम पथ चौड़ाई के रूप में बड़ी है। अन्य संबंधित मापदंडों में वृक्ष-गहराई शामिल है, एक संख्या जो एक मामूली-बंद ग्राफ परिवार के लिए सीमित है यदि और केवल तभी जब परिवार एक पथ को बाहर करता है, और अपक्षय, एक ग्राफ के अंतराल का एक उपाय जो इसकी त्रि-चौड़ाई के बराबर है। ग्रिड का छोटा आकार क्योंकि एक ग्रिड ग्राफ की त्रि-चौड़ाई है, एक ग्राफ की त्रि-चौड़ाई हमेशा सबसे बड़े वर्ग ग्रिड के आकार से अधिक या उसके बराबर होती है। दूसरी दिशा में, रॉबर्टसन और सीमोर द्वारा ग्रिड माइनर थ्योरम से पता चलता है कि एक अनबाउंडेड फंक्शन मौजूद है जैसे कि सबसे बड़े स्क्वायर ग्रिड माइनर का आकार कम से कम जहाँ त्रि-चौड़ाई है। ज्ञात सबसे अच्छी सीमाएँ हैं कि कम से कम कुछ निश्चित स्थिरांक के लिए होनी चाहिए, और अधिक से अधिक निचली सीमा में संकेतन के लिए, बड़ा ओ संकेतन देखें। सख्त सीमाएँ प्रतिबंधित ग्राफ परिवारों के लिए जानी जाती हैं, जो द्वि-आयामीता के सिद्धांत के माध्यम से उन परिवारों पर कई ग्राफ अनुकूलन समस्याओं के लिए कुशल एल्गोरिदम की ओर ले जाती हैं। हेलिन का ग्रिड प्रमेय अनंत ग्राफों के लिए त्रि-चौड़ाई और ग्रिड के छोटे आकार के बीच संबंध का एक अनुरूप प्रदान करता है। व्यास और स्थानीय त्रि-चौड़ाई उप-आलेखों के तहत बंद किए गए आलेखों के एक परिवार को सीमित स्थानीय त्रि-चौड़ाई, या व्यास-त्रि-चौड़ाई गुण कहा जाता है, यदि परिवार में आलेखों की त्रि-चौड़ाई उनके व्यास के एक कार्य से ऊपरी रूप से घिरी हुई है। यदि कक्षा को नाबालिगों को लेने के तहत बंद माना जाता है, तो स्थानीय त्रि-चौड़ाई को सीमित किया जाता है यदि और केवल तभी जब निषिद्ध नाबालिगों में से एक शीर्ष ग्राफ हो। इस परिणाम के मूल प्रमाणों से पता चला कि एक शीर्ष-लघु-मुक्त ग्राफ परिवार में त्रि-चौड़ाई व्यास के एक कार्य के रूप में अधिकतम दोगुनी तेजी से बढ़ती है; बाद में इसे एकल रूप से घातीय और अंत में एक रैखिक सीमा तक कम कर दिया गया। बाउंडेड लोकल त्रि-चौड़ाई द्वि-आयामीता के एल्गोरिथमिक सिद्धांत से निकटता से संबंधित है, और प्रथम क्रम तर्क में परिभाषित प्रत्येक ग्राफ गुण को एक शीर्ष-लघु-मुक्त ग्राफ परिवार के लिए उस समय में तय किया जा सकता है जो केवल थोड़ा सुपरलीनियर है। यह भी संभव है कि ग्राफ के एक वर्ग के लिए जो नाबालिगों के तहत बंद नहीं है, स्थानीय त्रि-चौड़ाई को सीमित किया गया हो। विशेष रूप से यह बाउंडेड डिग्री ग्राफ के एक वर्ग के लिए मामूली रूप से सच है, क्योंकि बाउंडेड व्यास सबग्राफ का आकार बाउंडेड होता है। एक अन्य उदाहरण 1-प्लेनर ग्राफ द्वारा दिया गया है, ग्राफ जिन्हें प्रति किनारे एक पार के साथ समतल में खींचा जा सकता है, और अधिक सामान्य रूप से उन ग्राफों के लिए जिन्हें प्रति किनारे पार करने की एक सीमित संख्या के साथ बंधी हुई जीनस की सतह पर खींचा जा सकता है। सीमित स्थानीय त्रि-चौड़ाई के लघु-बंद ग्राफ परिवारों के साथ, इस गुण ने इन ग्राफों के लिए कुशल सन्निकटन एल्गोरिदम का मार्ग प्रशस्त किया है। हैडविगर संख्या और एस-फंक्शन ग्राफ मापदंडों के एक वर्ग को परिभाषित करते हैं जिसे वे-फंक्शन कहते हैं, जिसमें त्रि-चौड़ाई शामिल है। ग्राफ से पूर्णांक तक के इन कार्यों को बिना किसी किनारे वाले ग्राफ पर शून्य होना आवश्यक है, माइनर-मोनोटोन होना आवश्यक है (एक फ़ंक्शन को "माइनर-मोनोटोन" के रूप में संदर्भित किया जाता है यदि, जब भी एक माइनर होता है, तो एक होता है), एक से बढ़ने के लिए जब एक नया शीर्ष जोड़ा जाता है जो पिछले सभी शीर्षों से सटा होता है, और एक समूह विभाजक के दोनों ओर दो उपग्राफ से बड़ा मूल्य लेने के लिए। ऐसे सभी कार्यों का समूह तत्ववार न्यूनतमकरण और अधिकतमकरण के संचालन के तहत एक पूर्ण जाली बनाता है। इस जाली में शीर्ष तत्व त्रि-चौड़ाई है, और निचला तत्व हैडविगर संख्या है, जो दिए गए ग्राफ में सबसे बड़े पूर्ण लघु का आकार है। टिप्पणियाँ संदर्भ। .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ग्राफ अपरिवर्तनीय ग्राफ लघु सिद्धांत