ट्रीविड्थ: Difference between revisions

Revision as of 07:24, 14 March 2023

एक आलेख सिद्धांत में, एक अप्रत्यक्ष आलेख की ट्रीविड्थ एक पूर्णांक संख्या है जो निर्दिष्ट करती है, अनौपचारिक रूप से, आलेख ट्री (आलेख सिद्धांत) होने से कितनी दूर है। सबसे छोटी ट्रीविड्थ 1 है; ट्रीविड्थ 1 वाले आलेख वास्तव में ट्री और ट्री (आलेख सिद्धांत)#वन हैं। अधिकतम 2 ट्रीविड्थ वाले आलेख श्रृंखला-समानांतर आलेख हैं। बिल्कुल ट्रीविड्थ के साथ अधिकतम रेखांकन $k$ के-ट्री कहलाते हैं| $k$ -ट्री, और अधिकतम ट्रीविड्थ वाले रेखांकन $k$ को आंशिक के-ट्री कहा जाता है | आंशिक $k$ -ट्री। कई अन्य अच्छी तरह से अध्ययन किए गए आलेख श्रेणीों में भी ट्रीविड्थ की सीमा होती है।

ट्रीविड्थ को औपचारिक रूप से कई समतुल्य माध्यमों से परिभाषित किया जा सकता है: आलेख के वृक्ष अपघटन में सबसे बड़े शिखर समुच्चय के आकार के संदर्भ में, आलेख के कॉर्डल समापन में सबसे बड़े क्लिक (आलेख सिद्धांत) के आकार के संदर्भ में, हेवन के अधिकतम क्रम के संदर्भ में (आलेख सिद्धांत) आलेख पर पीछा-चोरी के खेल के लिए एक रणनीति का वर्णन, या एक ब्रैमबल (आलेख सिद्धांत) के अधिकतम आदेश के संदर्भ में, जुड़े उप-आलेख का एक संग्रह जो सभी एक दूसरे को छूते हैं .

ट्रीविड्थ का उपयोग आमतौर पर आलेख कलन विधि के पैरामिट्रीकृत जटिलता विश्लेषण में एक पैरामीटर के रूप में किया जाता है। कई कलन विधि जो सामान्य आलेख के लिए एनपी कठिन हैं, आसान हो जाते हैं जब ट्रीविड्थ एक स्थिरांक से घिरा होता है।

ट्रीविड्थ की अवधारणा मूल रूप से किसके द्वारा प्रस्तुत की गई थी? (अम्बर्टो बर्टेल & फ्रांसेस्को ब्रियोस्की 1972) आयाम के नाम से। इसे बाद में द्वारा पुनः से खोजा गया था रुडोल्फ हेलिन (1976), उन गुणों के आधार पर जो इसे एक अलग आलेख पैरामीटर, हैडविगर संख्या के साथ साझा करता है। बाद में इसे पुनः से द्वारा खोजा गया था (नील रॉबर्टसन & पॉल सीमोर 1984) और उसके पश्चात कई अन्य लेखकों द्वारा अध्ययन किया गया है।^[1]

परिभाषा

आठ शीर्षों वाला एक आलेख, और छह नोड्स वाले एक ट्री पर इसका एक ट्री अपघटन। प्रत्येक आलेख एज दो शीर्षों को जोड़ता है जो किसी ट्री नोड पर एक साथ सूचीबद्ध होते हैं, और प्रत्येक आलेख शीर्ष को ट्री के सन्निहित सबट्री के नोड्स पर सूचीबद्ध किया जाता है। प्रत्येक ट्री नोड अधिकतम तीन शीर्षों को सूचीबद्ध करता है, इसलिए इस अपघटन की चौड़ाई दो है।

एक आलेख का एक ट्री अपघटन $G = (V, E)$ एक ट्री है $T$ नोड्स के साथ $X 1, \dots, X n$ , जहां प्रत्येक $X i$ का उपसमुच्चय है $V$ , निम्नलिखित गुणों को संतुष्ट करता है^[2] (नोड शब्द का प्रयोग एक शीर्ष को संदर्भित करने के लिए किया जाता है $T$ के शीर्ष के साथ भ्रम से बचने के लिए $G$ ):

सभी समुच्चयों का मिलन $X i$ बराबर है $V$ . यही है, प्रत्येक आलेख शीर्ष कम से कम एक ट्री नोड में समाहित है।
अगर $X i$ और $X j$ दोनों में एक शीर्ष है $v$ , पुनः सभी नोड्स $X k$ का $T$ के बीच (अद्वितीय) पथ में $X i$ और $X j$ रोकना $v$ भी। समतुल्य रूप से, ट्री नोड्स में शीर्ष होता है $v$ का कनेक्टेड सबट्री बनाता है $T$ .
हर किनारे के लिए $(v, w)$ आलेख में, एक सबसमुच्चय है $X i$ जिसमें दोनों सम्मिलित हैं $v$ और $w$ . यही है, कोने आलेख में आसन्न होते हैं, जब संबंधित उप-वृक्षों में एक आम नोड होता है।

एक ट्री के अपघटन की चौड़ाई उसके सबसे बड़े समुच्चय का आकार है $X i$ शून्य से एक कम। ट्रीविड्थ $tw(G)$ आलेख का $G$ के सभी संभव ट्री अपघटन के बीच न्यूनतम चौड़ाई है $G$ . इस परिभाषा में, ट्रीविड्थ को एक के बराबर बनाने के लिए सबसे बड़े समुच्चय के आकार को एक से घटा दिया जाता है।

समान रूप से, कीट्रीविड्थ $G$ युक्त कॉर्डल आलेख में सबसे बड़े क्लिक (आलेख सिद्धांत) के आकार से एक कम है $G$ सबसे छोटी अधिकतम क्लिक के साथ। इस क्लिक साइज के साथ कॉर्डल आलेख को जोड़कर प्राप्त किया जा सकता है $G$ हर दो शीर्षों के बीच एक किनारा जो दोनों कम से कम एक समुच्चय से संबंधित हैं $X i$ .

ट्रीविड्थ को हेवन (आलेख थ्योरी) के संदर्भ में भी चित्रित किया जा सकता है, एक आलेख पर परिभाषित एक निश्चित खोज-चोरी के खेल के लिए एक चोरी की रणनीति का वर्णन करने वाले कार्य। एक आलेख $G$ में ट्रीविड्थ है $k$ अगर और केवल अगर यह आदेश का स्श्रेणी है $k + 1$ लेकिन कोई उच्च क्रम नहीं, जहां आदेश का स्श्रेणी है $k + 1$ एक कार्य है $β$ जो प्रत्येक समुच्चय को मानचित्र करता है $X$ अधिक से अधिक $k$ कोने में $G$ के जुड़े घटकों में से एक में $G \ X$ और वह एकरसता गुण का पालन करता है $β (Y) \subseteq β (X)$ जब कभी भी $X \subseteq Y$ .

File:3x3 grid graph haven.svg

3×3 ग्रिड आलेख में क्रम चार का एक ब्रैमबल (आलेख सिद्धांत), जिसके अस्तित्व से पता चलता है कि आलेख में कम से कम 3 ट्रीविड्थ है

ब्रम्बल (आलेख सिद्धांत) का उपयोग करके एक समान लक्षण वर्णन भी किया जा सकता है, जुड़े उप-आलेख के श्रेणी जो सभी एक दूसरे को छूते हैं (अर्थात् या तो वे एक शीर्ष साझा करते हैं या किनारे से जुड़े होते हैं)।^[3] एक कंटक-गुल्म का क्रम उप-आलेख के श्रेणी के लिए सबसे छोटा हिटिंग समुच्चय है, और आलेख की ट्रीविड्थ एक कंटक-गुल्म के अधिकतम क्रम से एक कम है।

उदाहरण

हर पूरा आलेख $K n$ में ट्रीविड्थ है $n - 1$ . कॉर्डल आलेख के संदर्भ में ट्रीविड्थ की परिभाषा का उपयोग करके इसे सबसे आसानी से देखा जा सकता है: पूरा आलेख पहले से ही कॉर्डल है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े समूह के आकार को कम नहीं किया जा सकता है।

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

परिबद्ध ट्रीविड्थ

परिबद्ध ट्रीविड्थ वाले आलेख श्रेणी

किसी निश्चित स्थिरांक के लिए $k$ , ज़्यादा से ज़्यादा ट्रीविड्थ का आलेख $k$ को आंशिक के-ट्री कहा जाता है | आंशिक $k$ -ट्री। बाउंड ट्रीविड्थ वाले आलेख के अन्य श्रेणीों में कैक्टस आलेख, स्यूडोफॉरेस्ट, श्रृंखला-समानांतर रेखांकन, बाहरी रेखांकन, हालीन आलेख और अपोलोनियन नेटवर्क सम्मिलित हैं।^[4] संरचित प्रोग्रामिंग के संकलक में उत्पन्न होने वाले नियंत्रण-प्रवाह आलेख में ट्रीविड्थ भी होता है, जो कुछ कार्यों जैसे कि रजिस्टर आवंटन को उन पर कुशलता से करने की अनुमति देता है।^[5]

समतलीय रेखांकन में परिबद्ध ट्रीविड्थ नहीं होता है, क्योंकि $n \times n$ ग्रिड आलेख ट्रीविड्थ के साथ एक प्लेनर आलेख है $n$ . इसलिए, अगर $F$ एक उपसारणिक-बंद आलेख श्रेणी है जिसमें बाउंड ट्रीविड्थ है, इसमें सभी समतली आलेख सम्मिलित नहीं हो सकते। इसके विपरीत, यदि श्रेणी में आलेख के लिए कुछ समतली आलेख उपसारणिक के रूप में नहीं हो सकते हैं $F$ , तो एक स्थिरांक है $k$ जैसे कि सभी रेखांकन $F$ में अधिकतम ट्रीविड्थ है $k$ . अर्थात्, निम्नलिखित तीन स्थितियाँ एक दूसरे के समतुल्य हैं:^[6]

$F$ बाउंडेड-ट्रीविड्थ आलेख का उपसारणिक-बंद श्रेणी है;
चरित्र चित्रण करने वाले बहुत से वर्जित उपसारणिकों में से एक $F$ तलीय है;
$F$ एक छोटा-बंद आलेख श्रेणी है जिसमें सभी समतली आलेख सम्मिलित नहीं हैं।

निषिद्ध उपसारणिक

Error creating thumbnail:

ट्रीविड्थ 3 के लिए चार प्रतिबंधित उपसारणिक:

K 5

(शीर्ष-बाएँ), अष्टफलक का आलेख (नीचे-बाएँ), वैगनर आलेख (शीर्ष-दाएँ), और पंचकोणीय प्रिज़्म का आलेख (नीचे-दाएँ)

के प्रत्येक परिमित मूल्य के लिए $k$ , ज़्यादा से ज़्यादा ट्रीविड्थ का आलेख $k$ निषिद्ध आलेख लक्षण वर्णन के एक परिमित समुच्चय द्वारा विशेषता हो सकती है। (अर्थात, ट्रीविड्थ का कोई भी आलेख $> k$ में उपसारणिक के रूप में समुच्चय में से एक आलेख सम्मिलित है।) वर्जित उपसारणिकों के इन समुच्चयों में से प्रत्येक में कम से कम एक समतली आलेख सम्मिलित है।

के लिए $k = 1$ , अद्वितीय वर्जित उपसारणिक एक 3-शीर्ष चक्र आलेख है।^[7]
के लिए $k = 2$ , अद्वितीय वर्जित उपसारणिक 4-शीर्ष पूर्ण आलेख है $K 4$ .^[7]*के लिए $k = 3$ , चार वर्जित उपसारणिक हैं: $K 5$ , अष्टफलक का आलेख, पंचकोणीय प्रिज्म प्रिज्म आलेख और वैगनर आलेख। इनमें से दो बहुफलकीय आलेख समतलीय हैं।^[8]

के बड़े मूल्यों के लिए $k$ , वर्जित उपसारणिकों की संख्या कम से कम उतनी ही तीव्रतासे बढ़ती है जितनी कि के श्रेणीमूल की चरघातांकी $k$ .^[9] हालांकि, वर्जित उपसारणिकों के आकार और संख्या पर ज्ञात ऊपरी सीमाएं इस निचली सीमा से बहुत अधिक हैं।^[10]

कलन विधि

ट्रीविड्थ की गणना

यह निर्धारित करने के लिए एनपी-पूर्ण है कि क्या दिया गया आलेख है $G$ में किसी दिए गए वेरिएबल पर ट्रीविड्थ है $k$ .^[11]

हालाँकि, कब $k$ कोई निश्चित स्थिरांक है, ट्रीविड्थ वाला आलेख $k$ पहचाना जा सकता है, और एक चौड़ाई $k$ उनके लिए निर्मित वृक्ष अपघटन, रैखिक समय में।^[12] इस एल्गोरिथम की समय निर्भरता $k$ चरघातांकी है।

बड़ी संख्या में फ़ील्ड्स में ट्रीविड्थ की भूमिकाओं के कारण, आलेख के ट्रीविड्थ की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक कलन विधि विकसित किए गए थे। हाथ में आवेदन के आधार पर, इनपुट या ट्रीविड्थ के आकार से चलने वाले समय में बेहतर सन्निकटन अनुपात, या बेहतर निर्भरता पसंद कर सकते हैं।

नीचे दी गई तालिका कुछ ट्रीविड्थ कलन विधि का अवलोकन प्रदान करती है। यहाँ $k$ ट्रीविड्थ है और $n$ एक इनपुट आलेख के शीर्षों की संख्या है $G$ . प्रत्येक कलन विधि समय में आउटपुट करता है $f (k) \cdot g (n)$ अनुमानित कॉलम में दी गई चौड़ाई का अपघटन। उदाहरण के लिए, का कलन विधि बोडलैंडर (1996) समय के भीतर $2 O (k 3) \cdot n$ या तो इनपुट आलेख के ट्री अपघटन का निर्माण करता है $G$ अधिकतम चौड़ाई $k$ या रिपोर्ट करता है कि की ट्रीविड्थ $G$ से अधिक होता है $k$ . इसी तरह, का कलन विधि बोडलैंडर एट अल et al. (2016) समय के भीतर $2 O (k) \cdot n$ या तो इनपुट आलेख के ट्री अपघटन का निर्माण करता है $G$ अधिकतम चौड़ाई $5 k + 4$ या रिपोर्ट करता है कि की ट्रीविड्थ $G$ से अधिक होता है $k$ . Korhonen (2021) ने इसमें सुधार किया $2 k + 1$ एक ही रनिंग टाइम में।

सन्निकटन	$f (k)$	$g (n)$	संदर्भ
यथार्थ	$O (1)$	$O (n k +2)$	अर्नबोर्ग, कॉर्नियल & प्रोस्कुरोव्स्की (1987)
$4 k + 3$	$O (3 3 k)$	$O (n 2)$	रॉबर्टसन & सेमुर (1995)
$8 k + 7$	$2 O (k log k)$	$n log 2 n$	लेगरग्रेन (1996)
$5 k + 4$ (or $7 k + 6$ )	$2 O (k log k)$	$n log n$	रीड (1996)
यथार्थ	$2 O (k 3)$	$O (n)$	बोडलैंडर (1996)
$O\left(k\cdot {\sqrt {\log k}}\right)$	$O (1)$	$n O (1)$	फीज, हजियाघयी & ली (2008)
$4.5 k + 4$	$2 3 k$	$n 2$	आमिर (2010)
$.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}11/3k + 4$	$2 3.6982 k$	$n 3 log 4 n$	आमिर (2010)
यथार्थ	$O (1)$	$O (1.7347 n)$	फोमिन, टोडिंका & विलंगेर (2015)
$3 k + 2$	$2 O (k)$	$O (n log n)$	बोडलैंडर et al. (2016)
$5 k + 4$	$2 O (k)$	$O (n)$	बोडलैंडर et al. (2016)
$k 2$	$O (k 7)$	$O (n log n)$	फोमिन et al. (2018)
$5 k + 4$	$2 8.765 k$	$O (n log n)$	बेलबासी & फ्यूरर (2021a)
$2 k + 1$	$2 O (k)$	$O (n)$	कोरहोनेन (2021)
$5 k + 4$	$2 6.755 k$	$O (n log n)$	बेलबासी & फ्यूरर (2021b)
यथार्थ	$2 O (k 2)$	$n 4$	कोरहोनेन & लोकशतानोव (2022)
$\varepsilon$	$\varepsilon$	$n 4$	कोरहोनेन & लोकशतानोव (2022)

Unsolved problem in गणित:

क्या बहुपद समय में प्लानर ग्राफ की ट्रेविड्थ की गणना की जा सकती है?

(more unsolved problems in गणित)

यह ज्ञात नहीं है कि प्लैनर आलेख की ट्रीविड्थ का निर्धारण एनपी-पूर्ण है, या क्या उनकी ट्रीविड्थ की गणना बहुपद समय में की जा सकती है।^[13]

व्यवहार में, का एक एल्गोरिथ्म Shoikhet & Geiger (1997) इष्टतम ट्रीविड्थ के साथ इन आलेखों की कॉर्डल पूर्णता का पता लगाते हुए 100 शीर्षों तक के आलेख की ट्रीविड्थ और 11 तक ट्रीविड्थ का निर्धारण कर सकते हैं।

बड़े आलेख के लिए, कोई भी खोज-आधारित तकनीकों जैसे शाखा और बाउंड (BnB) का उपयोग कर सकता है और ट्रीविड्थ की गणना करने के लिए सर्वोत्तम-प्रथम खोज कर सकता है। ये कलन विधि कभी भी कलन विधि हैं, जब जल्दी बंद कर दिया जाता है, तो वे ट्रीविड्थ पर एक ऊपरी सीमा का उत्पादन करेंगे।

ट्रीविड्थ की गणना के लिए पहला BnB एल्गोरिथम, जिसे QuickBB एल्गोरिथम कहा जाता है^[14] गोगेट और डेक्टर द्वारा प्रस्तावित किया गया था।^[15] चूँकि किसी भी BnB एल्गोरिथम की गुणवत्ता उपयोग की जाने वाली निचली सीमा, Gogate और Dechter की गुणवत्ता पर अत्यधिक निर्भर है^[15]लघु-न्यूनतम-चौड़ाई नामक ट्रीविड्थ पर निचली सीमा की गणना करने के लिए एक उपन्यास एल्गोरिद्म भी प्रस्तावित किया।^[15]एक उच्च स्तर पर, लघु-न्यूनतम-चौड़ाई कलन विधि तथ्यों को जोड़ती है कि एक आलेख की ट्रीविड्थ कभी भी इसकी न्यूनतम डिग्री (आलेख थ्योरी) या इसके आलेख उपसारणिक से ट्रीविड्थ पर कम सीमा उत्पन्न करने के लिए बड़ी नहीं होती है। उपसारणिक-मिन-चौड़ाई एल्गोरिद्म बार-बार एक न्यूनतम डिग्री शीर्ष और उसके पड़ोसियों में से एक के बीच एक किनारे को अनुबंधित करके एक आलेख उपसारणिक का निर्माण करता है, जब तक कि केवल एक शीर्ष नहीं रहता। इन निर्मित उपसारणिकों पर न्यूनतम डिग्री की अधिकतम सीमा आलेख के ट्रीविड्थ पर निचली सीमा होने की गारंटी है।

डॉव और कोर्फ़^[16] सर्वोत्तम-प्रथम खोज का उपयोग करके QuickBB एल्गोरिद्म में सुधार किया। कुछ आलेख पर, यह सर्वोत्तम-प्रथम खोज एल्गोरिथम QuickBB की तुलना में तीव्रता का एक क्रम है।

छोटी ट्रीविड्थ के आलेख पर अन्य समस्याओं का समाधान

1970 के दशक की प्रारंभिक में, यह देखा गया कि आलेख पर परिभाषित संयोजी अनुकूलन समस्याओं की एक बड़ी श्रेणी को गैर सीरियल गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है, जब तक कि आलेख में एक परिबद्ध आयाम हो,^[17] द्वारा ट्रीविड्थ के समतुल्य दिखाया गया पैरामीटर Bodlaender (1998). बाद में, कई लेखकों ने स्वतंत्र रूप से 1980 के दशक के अंत में अवलोकन किया^[18] कि कई एल्गोरिथम समस्याएं जो एनपी-पूर्णता हैं | मनमानी आलेख के लिए एनपी-पूर्ण को इन आलेखों के ट्री-अपघटन का उपयोग करके बाध्य ट्रीविड्थ के आलेख के लिए गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है।

एक उदाहरण के रूप में, ट्रीविड्थ के आलेख को रंगने वाले आलेख की समस्या $k$ आलेख के वृक्ष अपघटन पर एक गतिशील प्रोग्रामिंग कलन विधि का उपयोग करके हल किया जा सकता है। प्रत्येक समुच्चय के लिए $X i$ ट्री के अपघटन का, और प्रत्येक विभाजन के शीर्षों के एक समुच्चय का $X i$ रंग श्रेणीों में, एल्गोरिथ्म निर्धारित करता है कि क्या वह रंग वैध है और ट्री के अपघटन में सभी वंशज नोड्स तक बढ़ाया जा सकता है, उन नोड्स पर गणना की गई और संग्रहीत समान प्रकार की जानकारी को मिलाकर। परिणामी एल्गोरिथ्म एक का एक इष्टतम रंग पाता है $n$ -समय में शीर्ष आलेख $O (k k + O (1) n)$ , एक समयबद्धता जो इस समस्या को पैरामिट्रीकृत जटिलता|फिक्स्ड-पैरामीटर ट्रैक्टेबल बनाती है।

कौरसेल प्रमेय

समस्याओं के एक बड़े श्रेणी के लिए, कक्षा से किसी समस्या को हल करने के लिए एक रैखिक समय एल्गोरिथ्म है यदि एक ट्री-अपघटन निरंतर बाध्य ट्रीविड्थ के साथ प्रदान किया जाता है। विशेष रूप से, कौरसेल की प्रमेय^[19] बताता है कि यदि मोनाडिक द्वितीय-क्रम तर्क का उपयोग करते हुए आलेख के तर्क में एक आलेख समस्या व्यक्त की जा सकती है, तो इसे रेखीय समय में बाउंड ट्रीविड्थ के साथ आलेख पर हल किया जा सकता है। मोनाडिक दूसरे क्रम का तर्क लॉजिक आलेख गुणों का वर्णन करने वाली एक भाषा है जो निम्नलिखित निर्माणों का उपयोग करती है:

तर्क संचालन, जैसे $\wedge ,\vee ,\neg ,\Rightarrow$
सदस्यता परीक्षण, जैसे $e \in E$ , $v \in V$
शीर्षों, किनारों, शीर्षों के समुच्चयों और/या किनारों के समुच्चयों पर परिमाणीकरण, जैसे $\forall v \in V$ , $\exists e \in E$ , $\exists I \subseteq V$ , $\forall F \subseteq E$
निकटता परीक्षण ( $u$ का समापन बिंदु है $e$ ), और कुछ एक्सटेंशन जो ऑप्टिमाइज़ेशन जैसी चीज़ों की अनुमति देते हैं।

उदाहरण के लिए आलेख कलरिंग | आलेख के लिए 3-कलरिंग समस्या पर विचार करें। एक आलेख के लिए $G = (V, E)$ , यह समस्या पूछती है कि क्या प्रत्येक शीर्ष निर्दिष्ट करना संभव है $v \in V$ 3 रंगों में से एक ऐसा है कि कोई भी दो आसन्न शीर्षों को समान रंग नहीं दिया गया है। इस समस्या को मोनाडिक सेकंड ऑर्डर लॉजिक में निम्नानुसार व्यक्त किया जा सकता है:

\exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge

\forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))

,

कहाँ $W 1$ , $W 2$ , $W 3$ 3 रंगों में से प्रत्येक वाले कोने के सबसमुच्चय का प्रतिनिधित्व करते हैं।

इसलिए, कौरसेल के परिणामों से, 3-रंग की समस्या को एक आलेख के लिए रैखिक समय में हल किया जा सकता है, जो कि निरंतर ट्रीविड्थ के ट्री-अपघटन को देखते हैं।

↑ Diestel (2005) pp.354–355
↑ Diestel (2005) section 12.3
↑ Seymour & Thomas (1993).
↑ ^4.0 ^4.1 Bodlaender (1998).
↑ Thorup (1998).
↑ Robertson & Seymour (1986).
↑ ^7.0 ^7.1 Bodlaender (1988).
↑ Arnborg, Proskurowski & Corneil (1990); Satyanarayana & Tung (1990).
↑ Ramachandramurthi (1997).
↑ Lagergren (1993).
↑ Arnborg, Corneil & Proskurowski (1987).
↑ Bodlaender (1996).
↑ Kao (2008).
↑ "विभव गोगटे". personal.utdallas.edu. Retrieved 2022-11-27.
↑ ^15.0 ^15.1 ^15.2 Gogate, Vibhav; Dechter, Rina (2012-07-11). "ट्रीविड्थ के लिए एक पूर्ण एनीटाइम एल्गोरिथम". arXiv:1207.4109 [cs.DS].
↑ "ट्रीविड्थ के लिए सर्वश्रेष्ठ-प्रथम खोज". www.aaai.org. Retrieved 2022-11-27.
↑ Bertelè & Brioschi (1972).
↑ Arnborg & Proskurowski (1989); Bern, Lawler & Wong (1987); Bodlaender (1988).
↑ Courcelle (1990); Courcelle (1992)
↑ Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1] open access publication – free to read
↑ Chekuri & Chuzhoy (2016)
↑ ^22.0 ^22.1 Demaine & Hajiaghayi (2008).
↑ Diestel (2004).
↑ Eppstein (2000).
↑ Eppstein (2000); Demaine & Hajiaghayi (2004a).
↑ Demaine & Hajiaghayi (2004b).
↑ Demaine et al. (2004); Demaine & Hajiaghayi (2008).
↑ Frick & Grohe (2001).
↑ Grigoriev & Bodlaender (2007).

संदर्भ

Amir, Eyal (2010), "Approximation algorithms for treewidth", Algorithmica, 56 (4): 448–479, doi:10.1007/s00453-008-9180-4, MR 2581059, S2CID 5874913.
Arnborg, S.; Corneil, D.; Proskurowski, A. (1987), "Complexity of finding embeddings in a $k$ -tree", SIAM Journal on Matrix Analysis and Applications, 8 (2): 277–284, doi:10.1137/0608024.
Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Forbidden minors characterization of partial 3-trees", Discrete Mathematics, 80 (1): 1–19, doi:10.1016/0012-365X(90)90292-P, MR 1045920.
Arnborg, S.; Proskurowski, A. (1989), "Linear time algorithms for NP-hard problems restricted to partial $k$ -trees", Discrete Applied Mathematics, 23 (1): 11–24, doi:10.1016/0166-218X(89)90031-0.
Belbasi, Mahdi; Fürer, Martin (2021a), "An improvement of Reed's treewidth approximation", in Uehara, Ryuhei; Hong, Seok-Hee; Nandy, Subhas C. (eds.), WALCOM: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, February 28 - March 2, 2021, Proceedings, Lecture Notes in Computer Science, vol. 12635, Springer, pp. 166–181, arXiv:2010.03105, doi:10.1007/978-3-030-68211-8_14, MR 4239527, S2CID 222177100.
Belbasi, Mahdi; Fürer, Martin (2021b), "Finding all leftmost separators of size $\leq k$ ", in Du, Ding-Zhu; Du, Donglei; Wu, Chenchen; Xu, Dachuan (eds.), Combinatorial Optimization and Applications - 15th International Conference, COCOA 2021, Tianjin, China, December 17-19, 2021, Proceedings, Lecture Notes in Computer Science, vol. 13135, Springer, pp. 273–287, arXiv:2111.02614, doi:10.1007/978-3-030-92681-6_23, S2CID 242758210
Bern, M. W.; Lawler, E. L.; Wong, A. L. (1987), "Linear-time computation of optimal subgraphs of decomposable graphs", Journal of Algorithms, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
Bertelè, Umberto; Brioschi, Francesco (1972), Nonserial Dynamic Programming, Academic Press, pp. 37–38, ISBN 978-0-12-093450-8.
Bodlaender, Hans L. (1988), "Dynamic programming on graphs with bounded treewidth", Proc. 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 317, Springer-Verlag, pp. 105–118, CiteSeerX 10.1.1.18.8503, doi:10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
Bodlaender, Hans L. (1996), "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing, 25 (6): 1305–1317, CiteSeerX 10.1.1.19.7484, doi:10.1137/S0097539793251219.
Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
Bodlaender, Hans L.; Drange, Pal G.; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michal (2016), "A $c^{k}n$ 5-approximation algorithm for treewidth", SIAM Journal on Computing, 45 (2): 317–378, arXiv:1304.6321, doi:10.1137/130947374.
Chekuri, Chandra; Chuzhoy, Julia (2016), "Polynomial bounds for the grid-minor theorem", Journal of the ACM, 63 (5): A40:1–65, arXiv:1305.6577, doi:10.1145/2820609, MR 3593966, S2CID 209860422.
Courcelle, B. (1990), "The monadic second-order logic of graphs I: Recognizable sets of finite graphs", Information and Computation, 85: 12–75, CiteSeerX 10.1.1.158.5595, doi:10.1016/0890-5401(90)90043-h.
Courcelle, B. (1992), "The monadic second-order logic of graphs III: Treewidth, forbidden minors and complexity issues.", Informatique Théorique (26): 257–286.
Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Bidimensional parameters and local treewidth", SIAM Journal on Discrete Mathematics, 18 (3): 501–511, CiteSeerX 10.1.1.107.6195, doi:10.1137/S0895480103433410, MR 2134412, S2CID 7803025.
Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004a), "Diameter and treewidth in minor-closed graph families, revisited", Algorithmica, 40 (3): 211–215, doi:10.1007/s00453-004-1106-1, MR 2080518, S2CID 390856.
Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004b), "Equivalence of local treewidth and linear local treewidth and its algorithmic applications", Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New York: ACM, pp. 840–849, MR 2290974.
Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2008), "Linearity of grid minors in treewidth with applications through bidimensionality" (PDF), Combinatorica, 28 (1): 19–36, doi:10.1007/s00493-008-2140-4, S2CID 16520181.
Diestel, Reinhard (2004), "A short proof of Halin's grid theorem", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 74: 237–242, doi:10.1007/BF02941538, MR 2112834, S2CID 124603912.
Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 978-3-540-26182-7.
Eppstein, D. (2000), "Diameter and treewidth in minor-closed graph families", Algorithmica, 27 (3–4): 275–291, arXiv:math/9907126, doi:10.1007/s004530010020, MR 1759751, S2CID 3172160.
Feige, Uriel; Hajiaghayi, MohammadTaghi; Lee, James R. (2008), "Improved approximation algorithms for minimum weight vertex separators", SIAM Journal on Computing, 38 (2): 629–657, CiteSeerX 10.1.1.597.5634, doi:10.1137/05064299X.
Fomin, Fedor V.; Todinca, Ioan; Villanger, Yngve (2015), "Large induced subgraphs via triangulations and CMSO", SIAM Journal on Computing, 44 (1): 54–87, arXiv:1309.1559, doi:10.1137/140964801, S2CID 15880453.
Frick, Markus; Grohe, Martin (2001), "Deciding first-order properties of locally tree-decomposable structures", Journal of the ACM, 48 (6): 1184–1206, arXiv:cs/0004007, doi:10.1145/504794.504798, MR 2143836, S2CID 999472.
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michal; Wrochna, Marcin (2018), "Fully polynomial-time parameterized computations for graphs and matrices of low treewidth", ACM Transactions on Algorithms, 14 (3): 34:1–34:45, arXiv:1511.01379, doi:10.1145/3186898, S2CID 2144798.
Grigoriev, Alexander; Bodlaender, Hans L. (2007), "Algorithms for graphs embeddable with few crossings per edge", Algorithmica, 49 (1): 1–11, CiteSeerX 10.1.1.65.5071, doi:10.1007/s00453-007-0010-x, MR 2344391, S2CID 8174422.
Halin, Rudolf (1976), "S-functions for graphs", Journal of Geometry, 8 (1–2): 171–186, doi:10.1007/BF01917434, S2CID 120256194.
Kao, Ming-Yang, ed. (2008), "Treewidth of graphs", Encyclopedia of Algorithms, Springer, p. 969, ISBN 9780387307701, Another long-standing open problem is whether there is a polynomial-time algorithm to compute the treewidth of planar graphs.
Korhonen, Tuukka (2021), "A Single-Exponential Time 2-Approximation Algorithm for Treewidth", Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, IEEE, pp. 184–192, arXiv:2104.07463, doi:10.1109/FOCS52979.2021.00026, S2CID 233240958.
Lagergren, Jens (1993), "An upper bound on the size of an obstruction", Graph structure theory (Seattle, WA, 1991), Contemporary Mathematics, vol. 147, Providence, RI: American Mathematical Society, pp. 601–621, doi:10.1090/conm/147/01202, ISBN 9780821851609, MR 1224734.
Lagergren, Jens (1996), "Efficient parallel algorithms for graphs of bounded tree-width", Journal of Algorithms, 20 (1): 20–44, doi:10.1006/jagm.1996.0002, MR 1368716.
Ramachandramurthi, Siddharthan (1997), "The structure and number of obstructions to treewidth", SIAM Journal on Discrete Mathematics, 10 (1): 146–157, doi:10.1137/S0895480195280010, MR 1430552.
Reed, Bruce A. (1992), "Finding approximate separators and computing tree width quickly", in Kosaraju, S. Rao; Fellows, Mike; Wigderson, Avi; Ellis, John A. (eds.), Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, ACM, pp. 221–228, doi:10.1145/129712.129734, S2CID 16259988.
Robertson, Neil; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory, Series B, 36 (1): 49–64, doi:10.1016/0095-8956(84)90013-3.
Robertson, Neil; Seymour, Paul D. (1986), "Graph minors V: Excluding a planar graph", Journal of Combinatorial Theory, Series B, 41 (1): 92–114, doi:10.1016/0095-8956(86)90030-4.
Robertson, Neil; Seymour, Paul D. (1995), "Graph Minors XIII: The Disjoint Paths Problem", Journal of Combinatorial Theory, Series B, 63 (1): 65–110, doi:10.1006/jctb.1995.1006.
Robertson, Neil; Seymour, Paul; Thomas, Robin (1994), "Quickly excluding a planar graph", Journal of Combinatorial Theory, Series B, 62 (2): 323–348, doi:10.1006/jctb.1994.1073, MR 1305057.
Satyanarayana, A.; Tung, L. (1990), "A characterization of partial 3-trees", Networks, 20 (3): 299–322, doi:10.1002/net.3230200304, MR 1050503.
Seymour, Paul D.; Thomas, Robin (1993), "Graph searching and a min-max theorem for tree-width", Journal of Combinatorial Theory, Series B, 58 (1): 22–33, doi:10.1006/jctb.1993.1027.
Shoikhet, Kirill; Geiger, Dan (1997), "A Practical Algorithm for Finding Optimal Triangulations", in Kuipers, Benjamin; Webber, Bonnie L. (eds.), Proceedings of the Fourteenth National Conference on Artificial Intelligence and Ninth Innovative Applications of Artificial Intelligence Conference, AAAI 97, IAAI 97, July 27-31, 1997, Providence, Rhode Island, USA, AAAI Press / The MIT Press, pp. 185–190.
Thorup, Mikkel (1998), "All structured programs have small tree width and good register allocation", Information and Computation, 142 (2): 159–181, doi:10.1006/inco.1997.2697.
Korhonen, Tuukka; Lokshtanov, Daniel (2022), "An Improved Parameterized Algorithm for Treewidth", arXiv:2211.07154 [cs.DS].

[1] Diestel (2005) pp.354–355

[2] Diestel (2005) section 12.3

[3] Seymour & Thomas (1993).

[b98-4] 4.0 ^4.1 Bodlaender (1998).

[5] Thorup (1998).

[6] Robertson & Seymour (1986).

[b88-7] 7.0 ^7.1 Bodlaender (1988).

[8] Arnborg, Proskurowski & Corneil (1990); Satyanarayana & Tung (1990).

[FOOTNOTERamachandramurthi1997-9] Ramachandramurthi (1997).

[FOOTNOTELagergren1993-10] Lagergren (1993).

[FOOTNOTEArnborgCorneilProskurowski1987-11] Arnborg, Corneil & Proskurowski (1987).

[b96-12] Bodlaender (1996).

[FOOTNOTEKao2008-13] Kao (2008).

[14] "विभव गोगटे". personal.utdallas.edu. Retrieved 2022-11-27.

[:0-15] 15.0 ^15.1 ^15.2 Gogate, Vibhav; Dechter, Rina (2012-07-11). "ट्रीविड्थ के लिए एक पूर्ण एनीटाइम एल्गोरिथम". arXiv:1207.4109 [cs.DS].

[16] "ट्रीविड्थ के लिए सर्वश्रेष्ठ-प्रथम खोज". www.aaai.org. Retrieved 2022-11-27.

[FOOTNOTEBertelèBrioschi1972-17] Bertelè & Brioschi (1972).

[18] Arnborg & Proskurowski (1989); Bern, Lawler & Wong (1987); Bodlaender (1988).

[19] Courcelle (1990); Courcelle (1992)

[20] Robertson, Seymour. Graph minors. V. Excluding a planar graph. [1] open access publication – free to read

[21] Chekuri & Chuzhoy (2016)

[FOOTNOTEDemaineHajiaghayi2008-22] 22.0 ^22.1 Demaine & Hajiaghayi (2008).

[FOOTNOTEDiestel2004-23] Diestel (2004).

[FOOTNOTEEppstein2000-24] Eppstein (2000).

[25] Eppstein (2000); Demaine & Hajiaghayi (2004a).

[FOOTNOTEDemaineHajiaghayi2004b-26] Demaine & Hajiaghayi (2004b).

[27] Demaine et al. (2004); Demaine & Hajiaghayi (2008).

[FOOTNOTEFrickGrohe2001-28] Frick & Grohe (2001).

[FOOTNOTEGrigorievBodlaender2007-29] Grigoriev & Bodlaender (2007).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

@@ Line 1: / Line 1: @@
 {{Short description|Number denoting a graph's closeness to a tree}}
-ग्राफ़ सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ]]़ की ट्रीविड्थ एक [[पूर्णांक]] संख्या है जो निर्दिष्ट करती है, अनौपचारिक रूप से, ग्राफ़ ट्री (ग्राफ़ सिद्धांत) होने से कितनी दूर है। सबसे छोटी ट्रीविड्थ 1 है; ट्रेविड्थ 1 वाले ग्राफ वास्तव में पेड़ और पेड़ ([[ग्राफ सिद्धांत]])#वन हैं। अधिकतम 2 ट्रीविड्थ वाले ग्राफ़ श्रृंखला-समानांतर ग्राफ़ हैं। बिल्कुल ट्रेविड्थ के साथ अधिकतम रेखांकन {{mvar|k}} के-ट्री कहलाते हैं|{{math|k}}-पेड़, और अधिकतम वृक्ष चौड़ाई वाले रेखांकन {{mvar|k}} को आंशिक के-ट्री कहा जाता है | आंशिक {{math|k}}-पेड़। कई अन्य अच्छी तरह से अध्ययन किए गए ग्राफ़ परिवारों में भी ट्रेविड्थ की सीमा होती है।
+एक आलेख सिद्धांत में, एक [[अप्रत्यक्ष ग्राफ|अप्रत्यक्ष]] आलेख की ट्रीविड्थ एक [[पूर्णांक]] संख्या है जो निर्दिष्ट करती है, अनौपचारिक रूप से, आलेख ट्री (आलेख सिद्धांत) होने से कितनी दूर है। सबसे छोटी ट्रीविड्थ 1 है; ट्रीविड्थ 1 वाले आलेख वास्तव में ट्री और ट्री ([[ग्राफ सिद्धांत|आलेख सिद्धांत]])#वन हैं। अधिकतम 2 ट्रीविड्थ वाले आलेख श्रृंखला-समानांतर आलेख हैं। बिल्कुल ट्रीविड्थ के साथ अधिकतम रेखांकन {{mvar|k}} के-ट्री कहलाते हैं|{{math|k}}-ट्री, और अधिकतम ट्रीविड्थ वाले रेखांकन {{mvar|k}} को आंशिक के-ट्री कहा जाता है | आंशिक {{math|k}}-ट्री। कई अन्य अच्छी तरह से अध्ययन किए गए आलेख श्रेणीों में भी ट्रीविड्थ की सीमा होती है।
-ट्रेविड्थ को औपचारिक रूप से कई समतुल्य तरीकों से परिभाषित किया जा सकता है: ग्राफ के [[वृक्ष अपघटन]] में सबसे बड़े शिखर सेट के आकार के संदर्भ में, ग्राफ के कॉर्डल समापन में सबसे बड़े क्लिक (ग्राफ सिद्धांत) के आकार के संदर्भ में, हेवन के अधिकतम क्रम के संदर्भ में (ग्राफ सिद्धांत) ग्राफ पर पीछा-चोरी के खेल के लिए एक रणनीति का वर्णन, या एक ब्रैमबल (ग्राफ सिद्धांत) के अधिकतम आदेश के संदर्भ में, जुड़े सबग्राफ का एक संग्रह जो सभी एक दूसरे को छूते हैं .
+ट्रीविड्थ को औपचारिक रूप से कई समतुल्य माध्यमों से परिभाषित किया जा सकता है: आलेख के [[वृक्ष अपघटन]] में सबसे बड़े शिखर समुच्चय के आकार के संदर्भ में, आलेख के कॉर्डल समापन में सबसे बड़े क्लिक (आलेख सिद्धांत) के आकार के संदर्भ में, हेवन के अधिकतम क्रम के संदर्भ में (आलेख सिद्धांत) आलेख पर पीछा-चोरी के खेल के लिए एक रणनीति का वर्णन, या एक ब्रैमबल (आलेख सिद्धांत) के अधिकतम आदेश के संदर्भ में, जुड़े उप-आलेख का एक संग्रह जो सभी एक दूसरे को छूते हैं .
-ट्रेविड्थ का उपयोग आमतौर पर ग्राफ़ [[कलन विधि]] के पैरामिट्रीकृत जटिलता विश्लेषण में एक पैरामीटर के रूप में किया जाता है। कई एल्गोरिदम जो सामान्य ग्राफ़ के लिए [[ एनपी कठिन ]] हैं, आसान हो जाते हैं जब ट्रीविड्थ एक स्थिरांक से घिरा होता है।
+ट्रीविड्थ का उपयोग आमतौर पर आलेख [[कलन विधि]] के पैरामिट्रीकृत जटिलता विश्लेषण में एक पैरामीटर के रूप में किया जाता है। कई कलन विधि जो सामान्य आलेख के लिए [[ एनपी कठिन ]] हैं, आसान हो जाते हैं जब ट्रीविड्थ एक स्थिरांक से घिरा होता है।
-ट्रीविड्थ की अवधारणा मूल रूप से किसके द्वारा प्रस्तुत की गई थी? {{harvs|last1 = Bertelè|first1=Umberto|last2=Brioschi|first2=Francesco|year = 1972|txt}} आयाम के नाम से। इसे बाद में द्वारा फिर से खोजा गया था {{harvs|last=Halin|first=Rudolf|authorlink=Rudolf Halin|year=1976|txt}}, उन गुणों के आधार पर जो इसे एक अलग ग्राफ़ पैरामीटर, [[हैडविगर संख्या]] के साथ साझा करता है। बाद में इसे फिर से द्वारा खोजा गया था {{harvs|first1=Neil|last1=Robertson|author1-link=Neil Robertson (mathematician)|first2=Paul|last2=Seymour|author2-link=Paul Seymour (mathematician)|year=1984|txt}} और उसके बाद से कई अन्य लेखकों द्वारा अध्ययन किया गया है।<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>
+ट्रीविड्थ की अवधारणा मूल रूप से किसके द्वारा प्रस्तुत की गई थी? {{harvs|last1 = बर्टेल|first1=अम्बर्टो|last2=ब्रियोस्की|first2=फ्रांसेस्को|year = 1972|और}} आयाम के नाम से। इसे बाद में द्वारा पुनः से खोजा गया था {{harvs|last=हेलिन|first=रुडोल्फ|authorlink=रुडोल्फ हेलिन|year=1976|txt}}, उन गुणों के आधार पर जो इसे एक अलग आलेख पैरामीटर, [[हैडविगर संख्या]] के साथ साझा करता है। बाद में इसे पुनः से द्वारा खोजा गया था {{harvs|first1=नील|last1=रॉबर्टसन|author1-link=नील रॉबर्टसन (गणितज्ञ)|first2=पॉल|last2=सीमोर|author2-link=पॉल सीमोर (गणितज्ञ)|year=1984|और}} और उसके पश्चात कई अन्य लेखकों द्वारा अध्ययन किया गया है।<ref>{{harvtxt|Diestel|2005}} pp.354–355</ref>
 == परिभाषा ==
-[[Image:Tree decomposition.svg|thumb|240px|आठ शीर्षों वाला एक ग्राफ, और छह नोड्स वाले एक पेड़ पर इसका एक पेड़ अपघटन। प्रत्येक ग्राफ़ एज दो शीर्षों को जोड़ता है जो किसी ट्री नोड पर एक साथ सूचीबद्ध होते हैं, और प्रत्येक ग्राफ़ वर्टेक्स को ट्री के सन्निहित सबट्री के नोड्स पर सूचीबद्ध किया जाता है। प्रत्येक ट्री नोड अधिकतम तीन शीर्षों को सूचीबद्ध करता है, इसलिए इस अपघटन की चौड़ाई दो है।]]एक ग्राफ का एक पेड़ अपघटन {{math|1={{mvar|G}} = (''V'', ''E'')}} एक पेड़ है {{mvar|T}} नोड्स के साथ {{math|''X''{{sub|1}}, …, ''X''{{sub|''n''}}}}, जहां प्रत्येक {{mvar|X{{sub|i}}}} का उपसमुच्चय है {{mvar|V}}, निम्नलिखित गुणों को संतुष्ट करता है<ref>{{harvtxt|Diestel|2005}} section 12.3</ref> (नोड शब्द का प्रयोग एक शीर्ष को संदर्भित करने के लिए किया जाता है {{mvar|T}} के शीर्ष के साथ भ्रम से बचने के लिए {{mvar|G}}):
+[[Image:Tree decomposition.svg|thumb|240px|आठ शीर्षों वाला एक आलेख, और छह नोड्स वाले एक ट्री पर इसका एक ट्री अपघटन। प्रत्येक आलेख एज दो शीर्षों को जोड़ता है जो किसी ट्री नोड पर एक साथ सूचीबद्ध होते हैं, और प्रत्येक आलेख शीर्ष को ट्री के सन्निहित सबट्री के नोड्स पर सूचीबद्ध किया जाता है। प्रत्येक ट्री नोड अधिकतम तीन शीर्षों को सूचीबद्ध करता है, इसलिए इस अपघटन की चौड़ाई दो है।]]एक आलेख का एक ट्री अपघटन {{math|1={{mvar|G}} = (''V'', ''E'')}} एक ट्री है {{mvar|T}} नोड्स के साथ {{math|''X''{{sub|1}}, …, ''X''{{sub|''n''}}}}, जहां प्रत्येक {{mvar|X{{sub|i}}}} का उपसमुच्चय है {{mvar|V}}, निम्नलिखित गुणों को संतुष्ट करता है<ref>{{harvtxt|Diestel|2005}} section 12.3</ref> (नोड शब्द का प्रयोग एक शीर्ष को संदर्भित करने के लिए किया जाता है {{mvar|T}} के शीर्ष के साथ भ्रम से बचने के लिए {{mvar|G}}):
-# सभी सेटों का मिलन {{mvar|X{{sub|i}}}} बराबर है {{mvar|V}}. यही है, प्रत्येक ग्राफ़ वर्टेक्स कम से कम एक ट्री नोड में समाहित है।
+# सभी समुच्चयों का मिलन {{mvar|X{{sub|i}}}} बराबर है {{mvar|V}}. यही है, प्रत्येक आलेख शीर्ष कम से कम एक ट्री नोड में समाहित है।
-# अगर {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} दोनों में एक शीर्ष है {{mvar|v}}, फिर सभी नोड्स {{mvar|X{{sub|k}}}} का {{mvar|T}} के बीच (अद्वितीय) पथ में {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} रोकना {{mvar|v}} भी। समतुल्य रूप से, ट्री नोड्स में वर्टेक्स होता है {{mvar|v}} का कनेक्टेड सबट्री बनाता है {{mvar|T}}.
+# अगर {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} दोनों में एक शीर्ष है {{mvar|v}}, पुनः सभी नोड्स {{mvar|X{{sub|k}}}} का {{mvar|T}} के बीच (अद्वितीय) पथ में {{mvar|X{{sub|i}}}} और {{mvar|X{{sub|j}}}} रोकना {{mvar|v}} भी। समतुल्य रूप से, ट्री नोड्स में शीर्ष होता है {{mvar|v}} का कनेक्टेड सबट्री बनाता है {{mvar|T}}.
-# हर किनारे के लिए {{math|(''v'', ''w'')}} ग्राफ में, एक सबसेट है {{mvar|X{{sub|i}}}} जिसमें दोनों शामिल हैं {{mvar|v}} और {{mvar|w}}. यही है, कोने ग्राफ़ में आसन्न होते हैं, जब संबंधित उप-वृक्षों में एक आम नोड होता है।
+# हर किनारे के लिए {{math|(''v'', ''w'')}} आलेख में, एक सबसमुच्चय है {{mvar|X{{sub|i}}}} जिसमें दोनों सम्मिलित हैं {{mvar|v}} और {{mvar|w}}. यही है, कोने आलेख में आसन्न होते हैं, जब संबंधित उप-वृक्षों में एक आम नोड होता है।
-एक पेड़ के अपघटन की चौड़ाई उसके सबसे बड़े सेट का आकार है {{mvar|X{{sub|i}}}} शून्य से एक कम। पेड़ की चौड़ाई {{math|tw(''G'')}} ग्राफ का {{mvar|G}} के सभी संभव पेड़ अपघटन के बीच न्यूनतम चौड़ाई है {{mvar|G}}. इस परिभाषा में, पेड़ की चौड़ाई को एक के बराबर बनाने के लिए सबसे बड़े सेट के आकार को एक से घटा दिया जाता है।
+एक ट्री के अपघटन की चौड़ाई उसके सबसे बड़े समुच्चय का आकार है {{mvar|X{{sub|i}}}} शून्य से एक कम। ट्रीविड्थ {{math|tw(''G'')}} आलेख का {{mvar|G}} के सभी संभव ट्री अपघटन के बीच न्यूनतम चौड़ाई है {{mvar|G}}. इस परिभाषा में, ट्रीविड्थ को एक के बराबर बनाने के लिए सबसे बड़े समुच्चय के आकार को एक से घटा दिया जाता है।
-समान रूप से, की वृक्ष चौड़ाई {{mvar|G}} युक्त [[कॉर्डल ग्राफ]] में सबसे बड़े क्लिक (ग्राफ सिद्धांत) के आकार से एक कम है {{mvar|G}} सबसे छोटी अधिकतम क्लिक के साथ। इस क्लिक साइज के साथ कॉर्डल ग्राफ को जोड़कर प्राप्त किया जा सकता है {{mvar|G}} हर दो शीर्षों के बीच एक किनारा जो दोनों कम से कम एक सेट से संबंधित हैं {{mvar|X{{sub|i}}}}.
+समान रूप से, कीट्रीविड्थ {{mvar|G}} युक्त [[कॉर्डल ग्राफ|कॉर्डल आलेख]] में सबसे बड़े क्लिक (आलेख सिद्धांत) के आकार से एक कम है {{mvar|G}} सबसे छोटी अधिकतम क्लिक के साथ। इस क्लिक साइज के साथ कॉर्डल आलेख को जोड़कर प्राप्त किया जा सकता है {{mvar|G}} हर दो शीर्षों के बीच एक किनारा जो दोनों कम से कम एक समुच्चय से संबंधित हैं {{mvar|X{{sub|i}}}}.
-ट्रेविड्थ को हेवन (ग्राफ थ्योरी) के संदर्भ में भी चित्रित किया जा सकता है, एक ग्राफ पर परिभाषित एक निश्चित खोज-चोरी के खेल के लिए एक चोरी की रणनीति का वर्णन करने वाले कार्य। एक ग्राफ {{mvar|G}} में ट्रीविड्थ है {{mvar|k}} अगर और केवल अगर यह आदेश का स्वर्ग है {{math|''k'' + 1}} लेकिन कोई उच्च क्रम नहीं, जहां आदेश का स्वर्ग है {{math|''k'' + 1}} एक कार्य है {{mvar|β}} जो प्रत्येक सेट को मैप करता है {{mvar|X}} अधिक से अधिक {{mvar|k}} कोने में {{mvar|G}} के जुड़े घटकों में से एक में {{math|{{mvar|G}} \ ''X''}} और वह एकरसता गुण का पालन करता है {{math|''&beta;''(''Y'') ⊆ ''&beta;''(''X'')}} जब कभी भी {{math|''X'' ⊆ ''Y''}}.
+ट्रीविड्थ को हेवन (आलेख थ्योरी) के संदर्भ में भी चित्रित किया जा सकता है, एक आलेख पर परिभाषित एक निश्चित खोज-चोरी के खेल के लिए एक चोरी की रणनीति का वर्णन करने वाले कार्य। एक आलेख {{mvar|G}} में ट्रीविड्थ है {{mvar|k}} अगर और केवल अगर यह आदेश का स्श्रेणी है {{math|''k'' + 1}} लेकिन कोई उच्च क्रम नहीं, जहां आदेश का स्श्रेणी है {{math|''k'' + 1}} एक कार्य है {{mvar|β}} जो प्रत्येक समुच्चय को मानचित्र करता है {{mvar|X}} अधिक से अधिक {{mvar|k}} कोने में {{mvar|G}} के जुड़े घटकों में से एक में {{math|{{mvar|G}} \ ''X''}} और वह एकरसता गुण का पालन करता है {{math|''&beta;''(''Y'') ⊆ ''&beta;''(''X'')}} जब कभी भी {{math|''X'' ⊆ ''Y''}}.
-[[File:3x3 grid graph haven.svg|thumb|3×3 ग्रिड ग्राफ़ में क्रम चार का एक ब्रैमबल (ग्राफ़ सिद्धांत), जिसके अस्तित्व से पता चलता है कि ग्राफ़ में कम से कम 3 पेड़ की चौड़ाई है]]ब्रम्बल (ग्राफ सिद्धांत) का उपयोग करके एक समान लक्षण वर्णन भी किया जा सकता है, जुड़े सबग्राफ के परिवार जो सभी एक दूसरे को छूते हैं (अर्थात् या तो वे एक शीर्ष साझा करते हैं या किनारे से जुड़े होते हैं)।<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref> एक ब्रैम्बल का क्रम सबग्राफ के परिवार के लिए सबसे छोटा [[हिटिंग सेट]] है, और ग्राफ़ की ट्रेविड्थ एक ब्रैम्बल के अधिकतम क्रम से एक कम है।
+[[File:3x3 grid graph haven.svg|thumb|3×3 ग्रिड आलेख में क्रम चार का एक ब्रैमबल (आलेख सिद्धांत), जिसके अस्तित्व से पता चलता है कि आलेख में कम से कम 3 ट्रीविड्थ है]]ब्रम्बल (आलेख सिद्धांत) का उपयोग करके एक समान लक्षण वर्णन भी किया जा सकता है, जुड़े उप-आलेख के श्रेणी जो सभी एक दूसरे को छूते हैं (अर्थात् या तो वे एक शीर्ष साझा करते हैं या किनारे से जुड़े होते हैं)।<ref>{{harvtxt|Seymour|Thomas|1993}}.</ref> एक कंटक-गुल्म का क्रम उप-आलेख के श्रेणी के लिए सबसे छोटा [[हिटिंग सेट|हिटिंग समुच्चय]] है, और आलेख की ट्रीविड्थ एक कंटक-गुल्म के अधिकतम क्रम से एक कम है।
 == उदाहरण ==
-हर [[पूरा ग्राफ]] {{mvar|K{{sub|n}}}} में ट्रीविड्थ है{{math| ''n'' – 1}}. कॉर्डल ग्राफ़ के संदर्भ में ट्रीविड्थ की परिभाषा का उपयोग करके इसे सबसे आसानी से देखा जा सकता है: पूरा ग्राफ़ पहले से ही कॉर्डल है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े समूह के आकार को कम नहीं किया जा सकता है।
+हर [[पूरा ग्राफ|पूरा आलेख]] {{mvar|K{{sub|n}}}} में ट्रीविड्थ है{{math| ''n'' – 1}}. कॉर्डल आलेख के संदर्भ में ट्रीविड्थ की परिभाषा का उपयोग करके इसे सबसे आसानी से देखा जा सकता है: पूरा आलेख पहले से ही कॉर्डल है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े समूह के आकार को कम नहीं किया जा सकता है।
-कम से कम दो शीर्षों वाले कनेक्टेड ग्राफ़ में ट्रीविड्थ 1 है यदि और केवल यदि वह एक ट्री है। एक पेड़ की ट्रीविड्थ एक ही तर्क के अनुसार पूर्ण रेखांकन के लिए होती है (अर्थात्, यह कॉर्डल है, और अधिकतम क्लिक आकार दो है)। इसके विपरीत, यदि किसी ग्राफ़ में एक चक्र है, तो ग्राफ़ के प्रत्येक कॉर्डल पूर्णता में कम से कम एक त्रिभुज शामिल होता है जिसमें चक्र के लगातार तीन कोने होते हैं, जिससे यह पता चलता है कि इसकी ट्रीविड्थ कम से कम दो है।
+कम से कम दो शीर्षों वाले कनेक्टेड आलेख में ट्रीविड्थ 1 है यदि और केवल यदि वह एक ट्री है। एक ट्री की ट्रीविड्थ एक ही तर्क के अनुसार पूर्ण रेखांकन के लिए होती है (अर्थात्, यह कॉर्डल है, और अधिकतम क्लिक आकार दो है)। इसके विपरीत, यदि किसी आलेख में एक चक्र है, तो आलेख के प्रत्येक कॉर्डल पूर्णता में कम से कम एक त्रिभुज सम्मिलित होता है जिसमें चक्र के लगातार तीन कोने होते हैं, जिससे यह पता चलता है कि इसकी ट्रीविड्थ कम से कम दो है।
-== परिबद्ध ट्रेविड्थ ==
+== परिबद्ध ट्रीविड्थ ==
-=== परिबद्ध ट्रेविड्थ वाले ग्राफ़ परिवार ===
+=== परिबद्ध ट्रीविड्थ वाले आलेख श्रेणी ===
-किसी निश्चित स्थिरांक के लिए {{mvar|k}}, ज़्यादा से ज़्यादा ट्रीविड्थ का ग्राफ़ {{mvar|k}} को आंशिक के-ट्री कहा जाता है | आंशिक {{mvar|k}}-पेड़। बाउंड ट्रेविड्थ वाले ग्राफ़ के अन्य परिवारों में [[कैक्टस ग्राफ]]़, [[seudoforest]], श्रृंखला-समानांतर ग्राफ़, [[आउटरप्लानर ग्राफ]]़, [[हालीन ग्राफ]] और [[अपोलोनियन नेटवर्क]] शामिल हैं।<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> [[संरचित प्रोग्रामिंग]] के [[संकलक]] में उत्पन्न होने वाले [[नियंत्रण-प्रवाह ग्राफ]]़ में ट्रीविड्थ भी होता है, जो कुछ कार्यों जैसे कि रजिस्टर आवंटन को उन पर कुशलता से करने की अनुमति देता है।<ref>{{harvtxt|Thorup|1998}}.</ref>
+किसी निश्चित स्थिरांक के लिए {{mvar|k}}, ज़्यादा से ज़्यादा ट्रीविड्थ का आलेख {{mvar|k}} को आंशिक के-ट्री कहा जाता है | आंशिक {{mvar|k}}-ट्री। बाउंड ट्रीविड्थ वाले आलेख के अन्य श्रेणीों में [[कैक्टस ग्राफ|कैक्टस]] आलेख, [[seudoforest|स्यूडोफॉरेस्ट]], श्रृंखला-समानांतर रेखांकन, बाहरी रेखांकन, [[हालीन ग्राफ|हालीन आलेख]] और [[अपोलोनियन नेटवर्क]] सम्मिलित हैं।<ref name="b98">{{harvtxt|Bodlaender|1998}}.</ref> [[संरचित प्रोग्रामिंग]] के [[संकलक]] में उत्पन्न होने वाले [[नियंत्रण-प्रवाह ग्राफ|नियंत्रण-प्रवाह]] आलेख में ट्रीविड्थ भी होता है, जो कुछ कार्यों जैसे कि रजिस्टर आवंटन को उन पर कुशलता से करने की अनुमति देता है।<ref>{{harvtxt|Thorup|1998}}.</ref>
-समतलीय रेखांकन में परिबद्ध ट्रेविड्थ नहीं होता है, क्योंकि {{math|''n'' × ''n''}} [[ग्रिड ग्राफ]] ट्रीविड्थ के साथ एक प्लेनर ग्राफ है {{mvar|n}}. इसलिए, अगर {{mvar|F}} एक ग्राफ़_माइनर#माइनर-क्लोज़_ग्राफ़_फ़ैमिली|माइनर-क्लोज़्ड ग्राफ़ फ़ैमिली है जिसमें बाउंड ट्रीविड्थ है, इसमें सभी प्लानर ग्राफ़ शामिल नहीं हो सकते। इसके विपरीत, यदि परिवार में ग्राफ के लिए कुछ प्लानर ग्राफ नाबालिग के रूप में नहीं हो सकते हैं {{mvar|F}}, तो एक स्थिरांक है {{mvar|k}} जैसे कि सभी रेखांकन {{mvar|F}} में अधिकतम ट्रीविड्थ है {{mvar|k}}. अर्थात्, निम्नलिखित तीन स्थितियाँ एक दूसरे के समतुल्य हैं:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
-#{{mvar|F}} बाउंडेड-ट्रीविड्थ ग्राफ़ का माइनर-क्लोज़्ड फ़ैमिली है;
-# चरित्र चित्रण करने वाले बहुत से वर्जित नाबालिगों में से एक {{mvar|F}} तलीय है;
-#{{mvar|F}} एक छोटा-बंद ग्राफ़ परिवार है जिसमें सभी प्लानर ग्राफ़ शामिल नहीं हैं।
-===निषिद्ध अवयस्क===
+समतलीय रेखांकन में परिबद्ध ट्रीविड्थ नहीं होता है, क्योंकि {{math|''n'' × ''n''}} [[ग्रिड ग्राफ|ग्रिड आलेख]] ट्रीविड्थ के साथ एक प्लेनर आलेख है {{mvar|n}}. इसलिए, अगर {{mvar|F}} एक उपसारणिक-बंद आलेख श्रेणी है जिसमें बाउंड ट्रीविड्थ है, इसमें सभी  समतली आलेख सम्मिलित नहीं हो सकते। इसके विपरीत, यदि श्रेणी में आलेख के लिए कुछ  समतली आलेख उपसारणिक के रूप में नहीं हो सकते हैं {{mvar|F}}, तो एक स्थिरांक है {{mvar|k}} जैसे कि सभी रेखांकन {{mvar|F}} में अधिकतम ट्रीविड्थ है {{mvar|k}}. अर्थात्, निम्नलिखित तीन स्थितियाँ एक दूसरे के समतुल्य हैं:<ref>{{harvtxt|Robertson|Seymour|1986}}.</ref>
-[[File:Partial 3-tree forbidden minors.svg|thumb|300px|ट्रीविड्थ 3 के लिए चार प्रतिबंधित अवयस्क: {{math|''K''{{sub|5}}}} (शीर्ष-बाएँ), अष्टफलक का ग्राफ़ (नीचे-बाएँ), वैगनर ग्राफ़ (शीर्ष-दाएँ), और पंचकोणीय प्रिज़्म का ग्राफ़ (नीचे-दाएँ)]]के प्रत्येक परिमित मूल्य के लिए {{mvar|k}}, ज़्यादा से ज़्यादा ट्रीविड्थ का ग्राफ़ {{mvar|k}} निषिद्ध ग्राफ़ लक्षण वर्णन के एक परिमित सेट द्वारा विशेषता हो सकती है। (यानी, ट्रेविड्थ का कोई भी ग्राफ {{math|> ''k''}} में नाबालिग के रूप में सेट में से एक ग्राफ शामिल है।) वर्जित नाबालिगों के इन सेटों में से प्रत्येक में कम से कम एक प्लानर ग्राफ शामिल है।
+#{{mvar|F}} बाउंडेड-ट्रीविड्थ आलेख का उपसारणिक-बंद श्रेणी है;
-*के लिए {{math|1=''k'' = 1}}, अद्वितीय वर्जित माइनर एक 3-शीर्ष [[चक्र ग्राफ]] है।<ref name="b88">{{harvtxt|Bodlaender|1988}}.</ref>
+# चरित्र चित्रण करने वाले बहुत से वर्जित उपसारणिकों में से एक {{mvar|F}} तलीय है;
-*के लिए {{math|1=''k'' = 2}}, अद्वितीय वर्जित माइनर 4-शीर्ष पूर्ण ग्राफ़ है {{math|''K''{{sub|4}}}}.<ref name="b88"/>*के लिए {{math|1=''k'' = 3}}, चार वर्जित अवयस्क हैं: {{math|''K''{{sub|5}}}}, [[अष्टफलक]] का ग्राफ, [[पंचकोणीय प्रिज्म]] [[प्रिज्म ग्राफ]] और [[वैगनर ग्राफ]]। इनमें से दो [[बहुफलकीय ग्राफ]] समतलीय हैं।<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
+#{{mvar|F}} एक छोटा-बंद आलेख श्रेणी है जिसमें सभी  समतली आलेख सम्मिलित नहीं हैं।
-के बड़े मूल्यों के लिए {{mvar|k}}, वर्जित अवयस्कों की संख्या कम से कम उतनी ही तेजी से बढ़ती है जितनी कि के वर्गमूल की चरघातांकी{{mvar|k}}.{{sfnp|Ramachandramurthi|1997}} हालांकि, वर्जित अवयस्कों के आकार और संख्या पर ज्ञात ऊपरी सीमाएं इस निचली सीमा से बहुत अधिक हैं।{{sfnp|Lagergren|1993}}
-== एल्गोरिदम ==
+===निषिद्ध उपसारणिक===
+[[File:Partial 3-tree forbidden minors.svg|thumb|300px|ट्रीविड्थ 3 के लिए चार प्रतिबंधित उपसारणिक: {{math|''K''{{sub|5}}}} (शीर्ष-बाएँ), अष्टफलक का आलेख (नीचे-बाएँ), वैगनर आलेख (शीर्ष-दाएँ), और पंचकोणीय प्रिज़्म का आलेख (नीचे-दाएँ)]]के प्रत्येक परिमित मूल्य के लिए {{mvar|k}}, ज़्यादा से ज़्यादा ट्रीविड्थ का आलेख {{mvar|k}} निषिद्ध आलेख लक्षण वर्णन के एक परिमित समुच्चय द्वारा विशेषता हो सकती है। (अर्थात, ट्रीविड्थ का कोई भी आलेख {{math|> ''k''}} में उपसारणिक के रूप में समुच्चय में से एक आलेख सम्मिलित है।) वर्जित उपसारणिकों के इन समुच्चयों में से प्रत्येक में कम से कम एक  समतली आलेख सम्मिलित है।
+*के लिए {{math|1=''k'' = 1}}, अद्वितीय वर्जित उपसारणिक एक 3-शीर्ष [[चक्र ग्राफ|चक्र आलेख]] है।<ref name="b88">{{harvtxt|Bodlaender|1988}}.</ref>
+*के लिए {{math|1=''k'' = 2}}, अद्वितीय वर्जित उपसारणिक 4-शीर्ष पूर्ण आलेख है {{math|''K''{{sub|4}}}}.<ref name="b88" />*के लिए {{math|1=''k'' = 3}}, चार वर्जित उपसारणिक हैं: {{math|''K''{{sub|5}}}}, [[अष्टफलक]] का आलेख, [[पंचकोणीय प्रिज्म]] [[प्रिज्म ग्राफ|प्रिज्म आलेख]] और [[वैगनर ग्राफ|वैगनर आलेख]]। इनमें से दो [[बहुफलकीय ग्राफ|बहुफलकीय आलेख]] समतलीय हैं।<ref>{{harvtxt|Arnborg|Proskurowski|Corneil|1990}}; {{harvtxt|Satyanarayana|Tung|1990}}.</ref>
+के बड़े मूल्यों के लिए {{mvar|k}}, वर्जित उपसारणिकों की संख्या कम से कम उतनी ही तीव्रतासे बढ़ती है जितनी कि के श्रेणीमूल की चरघातांकी{{mvar|k}}.{{sfnp|Ramachandramurthi|1997}} हालांकि, वर्जित उपसारणिकों के आकार और संख्या पर ज्ञात ऊपरी सीमाएं इस निचली सीमा से बहुत अधिक हैं।{{sfnp|Lagergren|1993}}
+== कलन विधि ==
 === ट्रीविड्थ की गणना ===
-यह निर्धारित करने के लिए एनपी-पूर्ण है कि क्या दिया गया ग्राफ है {{mvar|G}} में किसी दिए गए वेरिएबल पर ट्रीविड्थ है {{mvar|k}}.{{sfnp|Arnborg|Corneil|Proskurowski|1987}}
+यह निर्धारित करने के लिए एनपी-पूर्ण है कि क्या दिया गया आलेख है {{mvar|G}} में किसी दिए गए वेरिएबल पर ट्रीविड्थ है {{mvar|k}}.{{sfnp|Arnborg|Corneil|Proskurowski|1987}}
-हालाँकि, कब {{mvar|k}} कोई निश्चित स्थिरांक है, ट्रीविड्थ वाला ग्राफ़ {{mvar|k}} पहचाना जा सकता है, और एक चौड़ाई {{mvar|k}} उनके लिए निर्मित वृक्ष अपघटन, रैखिक समय में।<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> इस एल्गोरिथम की समय निर्भरता {{mvar|k}} चरघातांकी है।
+हालाँकि, कब {{mvar|k}} कोई निश्चित स्थिरांक है, ट्रीविड्थ वाला आलेख {{mvar|k}} पहचाना जा सकता है, और एक चौड़ाई {{mvar|k}} उनके लिए निर्मित वृक्ष अपघटन, रैखिक समय में।<ref name="b96">{{harvtxt|Bodlaender|1996}}.</ref> इस एल्गोरिथम की समय निर्भरता {{mvar|k}} चरघातांकी है।
+बड़ी संख्या में फ़ील्ड्स में ट्रीविड्थ की भूमिकाओं के कारण, आलेख के ट्रीविड्थ की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक कलन विधि विकसित किए गए थे। हाथ में आवेदन के आधार पर, इनपुट या ट्रीविड्थ के आकार से चलने वाले समय में बेहतर सन्निकटन अनुपात, या बेहतर निर्भरता पसंद कर सकते हैं।
-बड़ी संख्या में फ़ील्ड्स में ट्रीविड्थ की भूमिकाओं के कारण, ग्राफ के ट्रेविड्थ की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक एल्गोरिदम विकसित किए गए थे। हाथ में आवेदन के आधार पर, इनपुट या ट्रेविड्थ के आकार से चलने वाले समय में बेहतर सन्निकटन अनुपात, या बेहतर निर्भरता पसंद कर सकते हैं।
+नीचे दी गई तालिका कुछ ट्रीविड्थ कलन विधि का अवलोकन प्रदान करती है। यहाँ {{mvar|k}} ट्रीविड्थ है और {{mvar|n}} एक इनपुट आलेख के शीर्षों की संख्या है  {{mvar|G}}.
-नीचे दी गई तालिका कुछ ट्रेविड्थ एल्गोरिदम का अवलोकन प्रदान करती है। यहाँ {{mvar|k}} ट्रीविड्थ है और {{mvar|n}} एक इनपुट ग्राफ़ के शीर्षों की संख्या है  {{mvar|G}}.
+प्रत्येक कलन विधि समय में आउटपुट करता है {{math|''f''(''k'') ⋅ ''g''(''n'')}} अनुमानित कॉलम में दी गई चौड़ाई का अपघटन। उदाहरण के लिए, का कलन विधि {{harvtxt|बोडलैंडर|1996}} समय के भीतर {{math|''2''{{sup|''O''(''k''{{sup|3}})}}⋅''n''}} या तो इनपुट आलेख के ट्री अपघटन का निर्माण करता है {{mvar|G}} अधिकतम चौड़ाई {{mvar|k}} या रिपोर्ट करता है कि की ट्रीविड्थ {{mvar|G}} से अधिक होता है {{mvar|k}}. इसी तरह, का कलन विधि {{harvtxt|बोडलैंडर एट अल|ड्रैंज|ड्रेगी|फोमिन|2016}}  समय के भीतर {{math|2{{sup|''O''(''k'')}}⋅''n''}} या तो इनपुट आलेख के ट्री अपघटन का निर्माण करता है  {{mvar|G}} अधिकतम चौड़ाई {{math|5''k'' + 4}} या रिपोर्ट करता है कि की ट्रीविड्थ {{mvar|G}} से अधिक होता है {{mvar|k}}. {{harvtxt|Korhonen|2021}} ने इसमें सुधार किया {{math|2''k'' + 1}} एक ही रनिंग टाइम में।
-प्रत्येक एल्गोरिदम समय में आउटपुट करता है {{math|''f''(''k'') ⋅ ''g''(''n'')}} अनुमानित कॉलम में दी गई चौड़ाई का अपघटन। उदाहरण के लिए, का एल्गोरिदम {{harvtxt|Bodlaender|1996}} समय के भीतर {{math|''2''{{sup|''O''(''k''{{sup|3}})}}⋅''n''}} या तो इनपुट ग्राफ़ के ट्री अपघटन का निर्माण करता है {{mvar|G}} अधिकतम चौड़ाई {{mvar|k}} या रिपोर्ट करता है कि की ट्रेविड्थ {{mvar|G}} से अधिक होता है {{mvar|k}}. इसी तरह, का एल्गोरिदम {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}  समय के भीतर {{math|2{{sup|''O''(''k'')}}⋅''n''}} या तो इनपुट ग्राफ़ के ट्री अपघटन का निर्माण करता है  {{mvar|G}} अधिकतम चौड़ाई {{math|5''k'' + 4}} या रिपोर्ट करता है कि की ट्रेविड्थ {{mvar|G}} से अधिक होता है {{mvar|k}}. {{harvtxt|Korhonen|2021}} ने इसमें सुधार किया {{math|2''k'' + 1}} एक ही रनिंग टाइम में।
   {| class="wikitable"
 |-
-! Approximation !! {{math|''f''(''k'')}} !! {{math|''g''(''n'')}} !! reference
+! सन्निकटन !! {{math|''f''(''k'')}} !! {{math|''g''(''n'')}} !! संदर्भ
 |-
-| exact || {{math|''O''(1)}} || {{math|''O''(''n''{{sup|''k''+2}})}} || {{harvtxt|Arnborg|Corneil|Proskurowski|1987}}
+| यथार्थ || {{math|''O''(1)}} || {{math|''O''(''n''{{sup|''k''+2}})}} || {{harvtxt|अर्नबोर्ग|कॉर्नियल|प्रोस्कुरोव्स्की|1987}}
 |-
-|  {{math|4''k'' + 3}}  || {{math|''O''(3{{sup|3''k''}})}} || {{math|''O''(''n''{{sup|2}})}} || {{harvtxt|Robertson|Seymour|1995}}
+|  {{math|4''k'' + 3}}  || {{math|''O''(3{{sup|3''k''}})}} || {{math|''O''(''n''{{sup|2}})}} || {{harvtxt|रॉबर्टसन|सेमुर|1995}}
 |-
-| {{math|8''k'' + 7}}|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log{{sup|2}} ''n''}} || {{harvtxt|Lagergren|1996}}
+| {{math|8''k'' + 7}}|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log{{sup|2}} ''n''}} || {{harvtxt|लेगरग्रेन|1996}}
 |-
-| {{math|5''k'' + 4}} (or {{math|7''k'' + 6}})|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log ''n''}} || {{harvtxt|Reed|1996}}
+| {{math|5''k'' + 4}} (or {{math|7''k'' + 6}})|| {{math|2{{sup|''O''(''k'' log ''k'')}}}} || {{math|''n'' log ''n''}} || {{harvtxt|रीड|1996}}
 |-
-|  exact || {{math|2{{sup|''O''(''k''{{sup|3}})}}}} || {{math|''O''(''n'')}} ||{{harvtxt|Bodlaender|1996}}
+|  यथार्थ || {{math|2{{sup|''O''(''k''{{sup|3}})}}}} || {{math|''O''(''n'')}} ||{{harvtxt|बोडलैंडर|1996}}
 |-
-|  <math>O \left( k \cdot \sqrt{\log k} \right)</math> || {{math|''O''(1)}}|| {{math|''n''{{sup|''O''(1)}}}} ||{{harvtxt|Feige|Hajiaghayi|Lee |2008}}
+|  <math>O \left( k \cdot \sqrt{\log k} \right)</math> || {{math|''O''(1)}}|| {{math|''n''{{sup|''O''(1)}}}} ||{{harvtxt|फीज|हजियाघयी|ली|2008}}
 |-
-|  {{math|4.5''k'' + 4}} || {{math|2{{sup|3''k''}}}} || {{math|''n''{{sup|2}}}} ||{{harvtxt|Amir |2010}}
+|  {{math|4.5''k'' + 4}} || {{math|2{{sup|3''k''}}}} || {{math|''n''{{sup|2}}}} ||{{harvtxt|आमिर|2010}}
 |-
-|  {{math|{{sfrac|11|3}}''k'' + 4}} || {{math|2{{sup|3.6982''k''}}}} || {{math|''n''{{sup|3}} log{{sup|4}}''n''}} ||{{harvtxt|Amir |2010}}
+|  {{math|{{sfrac|11|3}}''k'' + 4}} || {{math|2{{sup|3.6982''k''}}}} || {{math|''n''{{sup|3}} log{{sup|4}}''n''}} ||{{harvtxt|आमिर |2010}}
 |-
-|  exact || {{math|''O''(1)}}|| {{math|''O''(1.7347{{sup|''n''}})}} || {{harvtxt|Fomin|Todinca|Villanger|2015}}
+|  यथार्थ || {{math|''O''(1)}}|| {{math|''O''(1.7347{{sup|''n''}})}} || {{harvtxt|फोमिन|टोडिंका|विलंगेर|2015}}
 |-
-|  {{math|3''k'' + 2}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
+|  {{math|3''k'' + 2}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बोडलैंडर|ड्रैंज|ड्रेगी|फोमिन|2016}}
 |-
-|  {{math|5''k'' + 4}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'')}} || {{harvtxt|Bodlaender|Drange|Dregi|Fomin|2016}}
+|  {{math|5''k'' + 4}}  || {{math|2{{sup|''O''(''k'')}}}} || {{math|''O''(''n'')}} || {{harvtxt|बोडलैंडर|ड्रैंज|ड्रेगी|फोमिन|2016}}
 |-
-|  {{math|''k''{{sup|2}}}}  || {{math|''O''(''k''{{sup|7}})}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Fomin|Lokshtanov|Saurabh| Pilipczuk |2018}}
+|  {{math|''k''{{sup|2}}}}  || {{math|''O''(''k''{{sup|7}})}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|फोमिन|लोकशतानोव|सौरभ|पिलिपजुक|2018}}
 |-
-|  {{math|5''k'' + 4}}  || {{math|2{{sup|8.765''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Belbasi|Fürer|2021a}}
+|  {{math|5''k'' + 4}}  || {{math|2{{sup|8.765''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बेलबासी|फ्यूरर|2021a}}
 |-
 |{{math|2''k'' + 1}}
 |{{math|2{{sup|''O''(''k'')}}}}
 |{{math|''O''(''n'')}}
-|{{harvtxt|Korhonen|2021}}
+|{{harvtxt|कोरहोनेन|2021}}
 |-
-|  {{math|5''k'' + 4}}  || {{math|2{{sup|6.755''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|Belbasi|Fürer|2021b}}
+|  {{math|5''k'' + 4}}  || {{math|2{{sup|6.755''k''}}}} || {{math|''O''(''n'' log ''n'')}} || {{harvtxt|बेलबासी|फ्यूरर|2021b}}
 |-
-|  exact  || {{math|2{{sup|''O''(''k''{{sup|2}})}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|Korhonen|Lokshtanov|2022}}
+|  यथार्थ  || {{math|2{{sup|''O''(''k''{{sup|2}})}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|कोरहोनेन|लोकशतानोव|2022}}
 |-
-|  {{math|(1+<math>\varepsilon</math>)''k''}}  || {{math|k{{sup|''O''(''k''/<math>\varepsilon</math>)}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|Korhonen|Lokshtanov|2022}}
+|  {{math|(1+<math>\varepsilon</math>)''k''}}  || {{math|k{{sup|''O''(''k''/<math>\varepsilon</math>)}}}} || {{math|''n''{{sup|4}}}} || {{harvtxt|कोरहोनेन|लोकशतानोव|2022}}
 |-
 |}
-{{unsolved|mathematics|Can the treewidth of [[planar graph]]s be computed in polynomial time?}}
+{{unsolved|गणित|क्या बहुपद समय में [[प्लानर ग्राफ]] की ट्रेविड्थ की गणना की जा सकती है?}}
-यह ज्ञात नहीं है कि प्लैनर ग्राफ़ की ट्रेविड्थ का निर्धारण एनपी-पूर्ण है, या क्या उनकी ट्रीविड्थ की गणना बहुपद समय में की जा सकती है।{{sfnp|Kao|2008}}
-व्यवहार में, का एक एल्गोरिथ्म {{harvtxt|Shoikhet|Geiger|1997}} इष्टतम ट्रेविड्थ के साथ इन ग्राफ़ों की कॉर्डल पूर्णता का पता लगाते हुए 100 शीर्षों तक के ग्राफ़ की ट्रेविड्थ और 11 तक ट्रीविड्थ का निर्धारण कर सकते हैं।
+यह ज्ञात नहीं है कि प्लैनर आलेख की ट्रीविड्थ का निर्धारण एनपी-पूर्ण है, या क्या उनकी ट्रीविड्थ की गणना बहुपद समय में की जा सकती है।{{sfnp|Kao|2008}}
-बड़े ग्राफ़ के लिए, कोई भी खोज-आधारित तकनीकों जैसे शाखा और बाउंड (BnB) का उपयोग कर सकता है और ट्रेविड्थ की गणना करने के लिए सर्वोत्तम-प्रथम खोज कर सकता है। ये एल्गोरिदम [[कभी भी एल्गोरिदम]] हैं, जब जल्दी बंद कर दिया जाता है, तो वे ट्रीविड्थ पर एक ऊपरी सीमा का उत्पादन करेंगे।
+व्यवहार में, का एक एल्गोरिथ्म {{harvtxt|Shoikhet|Geiger|1997}} इष्टतम ट्रीविड्थ के साथ इन आलेखों की कॉर्डल पूर्णता का पता लगाते हुए 100 शीर्षों तक के आलेख की ट्रीविड्थ और 11 तक ट्रीविड्थ का निर्धारण कर सकते हैं।
-ट्रेविड्थ की गणना के लिए पहला BnB एल्गोरिथम, जिसे QuickBB एल्गोरिथम कहा जाता है<ref>{{Cite web |title=विभव गोगटे|url=https://personal.utdallas.edu/~vibhav.gogate/quickbb.html |access-date=2022-11-27 |website=personal.utdallas.edu}}</ref> गोगेट और डेक्टर द्वारा प्रस्तावित किया गया था।<ref name=":0">{{Cite arXiv |last1=Gogate |first1=Vibhav |last2=Dechter |first2=Rina |date=2012-07-11 |title=ट्रीविड्थ के लिए एक पूर्ण एनीटाइम एल्गोरिथम|class=cs.DS |eprint=1207.4109 }}</ref> चूँकि किसी भी BnB एल्गोरिथम की गुणवत्ता उपयोग की जाने वाली निचली सीमा, Gogate और Dechter की गुणवत्ता पर अत्यधिक निर्भर है<ref name=":0" />लघु-न्यूनतम-चौड़ाई नामक ट्रेविड्थ पर निचली सीमा की गणना करने के लिए एक उपन्यास एल्गोरिद्म भी प्रस्तावित किया।<ref name=":0" />एक उच्च स्तर पर, लघु-न्यूनतम-चौड़ाई एल्गोरिदम तथ्यों को जोड़ती है कि एक ग्राफ़ की ट्रेविड्थ कभी भी इसकी न्यूनतम डिग्री (ग्राफ़ थ्योरी) या इसके ग्राफ़ माइनर से ट्रेविड्थ पर कम सीमा उत्पन्न करने के लिए बड़ी नहीं होती है। माइनर-मिन-चौड़ाई एल्गोरिद्म बार-बार एक न्यूनतम डिग्री वर्टेक्स और उसके पड़ोसियों में से एक के बीच एक किनारे को अनुबंधित करके एक [[ग्राफ माइनर]] का निर्माण करता है, जब तक कि केवल एक वर्टेक्स नहीं रहता। इन निर्मित अवयस्कों पर न्यूनतम डिग्री की अधिकतम सीमा ग्राफ़ के ट्रेविड्थ पर निचली सीमा होने की गारंटी है।
+बड़े आलेख के लिए, कोई भी खोज-आधारित तकनीकों जैसे शाखा और बाउंड (BnB) का उपयोग कर सकता है और ट्रीविड्थ की गणना करने के लिए सर्वोत्तम-प्रथम खोज कर सकता है। ये कलन विधि [[कभी भी एल्गोरिदम|कभी भी कलन विधि]] हैं, जब जल्दी बंद कर दिया जाता है, तो वे ट्रीविड्थ पर एक ऊपरी सीमा का उत्पादन करेंगे।
-डॉव और कोर्फ़<ref>{{Cite web |title=ट्रीविड्थ के लिए सर्वश्रेष्ठ-प्रथम खोज|url=https://www.aaai.org/Library/AAAI/2007/aaai07-182.php |access-date=2022-11-27 |website=www.aaai.org}}</ref> सर्वोत्तम-प्रथम खोज का उपयोग करके QuickBB एल्गोरिद्म में सुधार किया। कुछ ग्राफ़ पर, यह सर्वोत्तम-प्रथम खोज एल्गोरिथम QuickBB की तुलना में तीव्रता का एक क्रम है।
+ट्रीविड्थ की गणना के लिए पहला BnB एल्गोरिथम, जिसे QuickBB एल्गोरिथम कहा जाता है<ref>{{Cite web |title=विभव गोगटे|url=https://personal.utdallas.edu/~vibhav.gogate/quickbb.html |access-date=2022-11-27 |website=personal.utdallas.edu}}</ref> गोगेट और डेक्टर द्वारा प्रस्तावित किया गया था।<ref name=":0">{{Cite arXiv |last1=Gogate |first1=Vibhav |last2=Dechter |first2=Rina |date=2012-07-11 |title=ट्रीविड्थ के लिए एक पूर्ण एनीटाइम एल्गोरिथम|class=cs.DS |eprint=1207.4109 }}</ref> चूँकि किसी भी BnB एल्गोरिथम की गुणवत्ता उपयोग की जाने वाली निचली सीमा, Gogate और Dechter की गुणवत्ता पर अत्यधिक निर्भर है<ref name=":0" />लघु-न्यूनतम-चौड़ाई नामक ट्रीविड्थ पर निचली सीमा की गणना करने के लिए एक उपन्यास एल्गोरिद्म भी प्रस्तावित किया।<ref name=":0" />एक उच्च स्तर पर, लघु-न्यूनतम-चौड़ाई कलन विधि तथ्यों को जोड़ती है कि एक आलेख की ट्रीविड्थ कभी भी इसकी न्यूनतम डिग्री (आलेख थ्योरी) या इसके आलेख उपसारणिक से ट्रीविड्थ पर कम सीमा उत्पन्न करने के लिए बड़ी नहीं होती है। उपसारणिक-मिन-चौड़ाई एल्गोरिद्म बार-बार एक न्यूनतम डिग्री शीर्ष और उसके पड़ोसियों में से एक के बीच एक किनारे को अनुबंधित करके एक [[ग्राफ माइनर|आलेख उपसारणिक]] का निर्माण करता है, जब तक कि केवल एक शीर्ष नहीं रहता। इन निर्मित उपसारणिकों पर न्यूनतम डिग्री की अधिकतम सीमा आलेख के ट्रीविड्थ पर निचली सीमा होने की गारंटी है।
-=== छोटी ट्रेविड्थ के ग्राफ़ पर अन्य समस्याओं का समाधान ===
+डॉव और कोर्फ़<ref>{{Cite web |title=ट्रीविड्थ के लिए सर्वश्रेष्ठ-प्रथम खोज|url=https://www.aaai.org/Library/AAAI/2007/aaai07-182.php |access-date=2022-11-27 |website=www.aaai.org}}</ref> सर्वोत्तम-प्रथम खोज का उपयोग करके QuickBB एल्गोरिद्म में सुधार किया। कुछ आलेख पर, यह सर्वोत्तम-प्रथम खोज एल्गोरिथम QuickBB की तुलना में तीव्रता का एक क्रम है।
-के दशक की शुरुआत में, यह देखा गया कि ग्राफ़ पर परिभाषित संयोजी अनुकूलन समस्याओं की एक बड़ी श्रेणी को गैर सीरियल [[गतिशील प्रोग्रामिंग]] द्वारा कुशलतापूर्वक हल किया जा सकता है, जब तक कि ग्राफ़ में एक परिबद्ध आयाम हो,{{sfnp|Bertelè|Brioschi|1972}} द्वारा ट्रीविड्थ के समतुल्य दिखाया गया पैरामीटर {{harvtxt|Bodlaender|1998}}. बाद में, कई लेखकों ने स्वतंत्र रूप से 1980 के दशक के अंत में अवलोकन किया<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> कि कई एल्गोरिथम समस्याएं जो एनपी-पूर्णता हैं | मनमानी ग्राफ के लिए एनपी-पूर्ण को इन ग्राफों के पेड़-अपघटन का उपयोग करके बाध्य ट्रीविड्थ के ग्राफ के लिए गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है।
-एक उदाहरण के रूप में, ट्रीविड्थ के ग्राफ को रंगने वाले ग्राफ की समस्या {{mvar|k}} ग्राफ़ के वृक्ष अपघटन पर एक गतिशील प्रोग्रामिंग एल्गोरिदम का उपयोग करके हल किया जा सकता है। प्रत्येक सेट के लिए {{mvar|X{{sub|i}}}} पेड़ के अपघटन का, और प्रत्येक विभाजन के शीर्षों के एक सेट का  {{mvar|X{{sub|i}}}} रंग वर्गों में, एल्गोरिथ्म निर्धारित करता है कि क्या वह रंग वैध है और पेड़ के अपघटन में सभी वंशज नोड्स तक बढ़ाया जा सकता है, उन नोड्स पर गणना की गई और संग्रहीत समान प्रकार की जानकारी को मिलाकर। परिणामी एल्गोरिथ्म एक का एक इष्टतम रंग पाता है {{mvar|n}}-समय में वर्टेक्स ग्राफ {{math|''O''(''k''<sup>''k''+''O''(1)</sup>''n'')}}, एक समयबद्धता जो इस समस्या को पैरामिट्रीकृत जटिलता|फिक्स्ड-पैरामीटर ट्रैक्टेबल बनाती है।
+=== छोटी ट्रीविड्थ के आलेख पर अन्य समस्याओं का समाधान ===
+के दशक की प्रारंभिक में, यह देखा गया कि आलेख पर परिभाषित संयोजी अनुकूलन समस्याओं की एक बड़ी श्रेणी को गैर सीरियल [[गतिशील प्रोग्रामिंग]] द्वारा कुशलतापूर्वक हल किया जा सकता है, जब तक कि आलेख में एक परिबद्ध आयाम हो,{{sfnp|Bertelè|Brioschi|1972}} द्वारा ट्रीविड्थ के समतुल्य दिखाया गया पैरामीटर {{harvtxt|Bodlaender|1998}}. बाद में, कई लेखकों ने स्वतंत्र रूप से 1980 के दशक के अंत में अवलोकन किया<ref>{{harvtxt|Arnborg|Proskurowski|1989}}; {{harvtxt|Bern|Lawler|Wong|1987}}; {{harvtxt|Bodlaender|1988}}.</ref> कि कई एल्गोरिथम समस्याएं जो एनपी-पूर्णता हैं | मनमानी आलेख के लिए एनपी-पूर्ण को इन आलेखों के ट्री-अपघटन का उपयोग करके बाध्य ट्रीविड्थ के आलेख के लिए गतिशील प्रोग्रामिंग द्वारा कुशलतापूर्वक हल किया जा सकता है।
+एक उदाहरण के रूप में, ट्रीविड्थ के आलेख को रंगने वाले आलेख की समस्या {{mvar|k}} आलेख के वृक्ष अपघटन पर एक गतिशील प्रोग्रामिंग कलन विधि का उपयोग करके हल किया जा सकता है। प्रत्येक समुच्चय के लिए {{mvar|X{{sub|i}}}} ट्री के अपघटन का, और प्रत्येक विभाजन के शीर्षों के एक समुच्चय का  {{mvar|X{{sub|i}}}} रंग श्रेणीों में, एल्गोरिथ्म निर्धारित करता है कि क्या वह रंग वैध है और ट्री के अपघटन में सभी वंशज नोड्स तक बढ़ाया जा सकता है, उन नोड्स पर गणना की गई और संग्रहीत समान प्रकार की जानकारी को मिलाकर। परिणामी एल्गोरिथ्म एक का एक इष्टतम रंग पाता है {{mvar|n}}-समय में शीर्ष आलेख {{math|''O''(''k''<sup>''k''+''O''(1)</sup>''n'')}}, एक समयबद्धता जो इस समस्या को पैरामिट्रीकृत जटिलता|फिक्स्ड-पैरामीटर ट्रैक्टेबल बनाती है।
 === कौरसेल प्रमेय ===
 {{main|Courcelle's theorem}}
-समस्याओं के एक बड़े वर्ग के लिए, कक्षा से किसी समस्या को हल करने के लिए एक रैखिक समय एल्गोरिथ्म है यदि एक वृक्ष अपघटन|वृक्ष-अपघटन निरंतर बाध्य ट्रेविड्थ के साथ प्रदान किया जाता है। विशेष रूप से, कौरसेल की प्रमेय<ref>{{harvtxt|Courcelle|1990}}; {{harvtxt|Courcelle|1992}}</ref> बताता है कि यदि मोनाडिक द्वितीय-क्रम तर्क का उपयोग करते हुए ग्राफ़ के तर्क में एक ग्राफ़ समस्या व्यक्त की जा सकती है, तो इसे रेखीय समय में बाउंड ट्रेविड्थ के साथ ग्राफ़ पर हल किया जा सकता है। [[मोनाडिक दूसरे क्रम का तर्क]] लॉजिक ग्राफ़ गुणों का वर्णन करने वाली एक भाषा है जो निम्नलिखित निर्माणों का उपयोग करती है:
+समस्याओं के एक बड़े श्रेणी के लिए, कक्षा से किसी समस्या को हल करने के लिए एक रैखिक समय एल्गोरिथ्म है यदि एक ट्री-अपघटन निरंतर बाध्य ट्रीविड्थ के साथ प्रदान किया जाता है। विशेष रूप से, कौरसेल की प्रमेय<ref>{{harvtxt|Courcelle|1990}}; {{harvtxt|Courcelle|1992}}</ref> बताता है कि यदि मोनाडिक द्वितीय-क्रम तर्क का उपयोग करते हुए आलेख के तर्क में एक आलेख समस्या व्यक्त की जा सकती है, तो इसे रेखीय समय में बाउंड ट्रीविड्थ के साथ आलेख पर हल किया जा सकता है। [[मोनाडिक दूसरे क्रम का तर्क]] लॉजिक आलेख गुणों का वर्णन करने वाली एक भाषा है जो निम्नलिखित निर्माणों का उपयोग करती है:
 * तर्क संचालन, जैसे <math> \wedge ,\vee ,\neg ,\Rightarrow </math>
 * सदस्यता परीक्षण, जैसे {{math|''e'' ∈ ''E''}}, {{math|''v'' ∈ ''V''}}
-* शीर्षों, किनारों, शीर्षों के सेटों और/या किनारों के सेटों पर परिमाणीकरण, जैसे {{math|∀''v'' ∈ ''V''}}, {{math|∃''e'' ∈ ''E''}}, {{math|∃''I'' ⊆ ''V''}}, {{math|∀''F'' ⊆ ''E''}}
+* शीर्षों, किनारों, शीर्षों के समुच्चयों और/या किनारों के समुच्चयों पर परिमाणीकरण, जैसे {{math|∀''v'' ∈ ''V''}}, {{math|∃''e'' ∈ ''E''}}, {{math|∃''I'' ⊆ ''V''}}, {{math|∀''F'' ⊆ ''E''}}
 * निकटता परीक्षण ({{mvar|u}} का समापन बिंदु है {{mvar|e}}), और कुछ एक्सटेंशन जो ऑप्टिमाइज़ेशन जैसी चीज़ों की अनुमति देते हैं।
-उदाहरण के लिए ग्राफ़ कलरिंग | ग्राफ़ के लिए 3-कलरिंग समस्या पर विचार करें। एक ग्राफ के लिए {{math|1=''G'' = (''V'', ''E'')}}, यह समस्या पूछती है कि क्या प्रत्येक शीर्ष निर्दिष्ट करना संभव है {{math|''v'' ∈ ''V''}}3 रंगों में से एक ऐसा है कि कोई भी दो आसन्न शीर्षों को समान रंग नहीं दिया गया है।
+उदाहरण के लिए आलेख कलरिंग | आलेख के लिए 3-कलरिंग समस्या पर विचार करें। एक आलेख के लिए {{math|1=''G'' = (''V'', ''E'')}}, यह समस्या पूछती है कि क्या प्रत्येक शीर्ष निर्दिष्ट करना संभव है {{math|''v'' ∈ ''V''}}3 रंगों में से एक ऐसा है कि कोई भी दो आसन्न शीर्षों को समान रंग नहीं दिया गया है।
 इस समस्या को मोनाडिक सेकंड ऑर्डर लॉजिक में निम्नानुसार व्यक्त किया जा सकता है:
 :<math> \exists W_1 \subseteq V : \exists W_2 \subseteq V : \exists W_3 \subseteq V : \forall v \in V : (v \in W_1 \vee v \in W_2 \vee v \in W_3) \wedge </math>
 :<math> \forall v \in V : \forall w \in V : (v,w) \in E \Rightarrow (\neg (v \in W_1 \wedge w \in W_1) \wedge \neg (v \in W_2 \wedge w \in W_2) \wedge \neg (v \in W_3 \wedge w \in W_3))</math>,
-कहाँ {{math|''W''{{sub|1}}}}, {{math|''W''{{sub|2}}}}, {{math|''W''{{sub|3}}}} 3 रंगों में से प्रत्येक वाले कोने के सबसेट का प्रतिनिधित्व करते हैं।
+कहाँ {{math|''W''{{sub|1}}}}, {{math|''W''{{sub|2}}}}, {{math|''W''{{sub|3}}}} 3 रंगों में से प्रत्येक वाले कोने के सबसमुच्चय का प्रतिनिधित्व करते हैं।
-इसलिए, कौरसेल के परिणामों से, 3-रंग की समस्या को एक ग्राफ के लिए रैखिक समय में हल किया जा सकता है, जो कि निरंतर ट्रीविड्थ के पेड़-अपघटन को देखते हैं।
+इसलिए, कौरसेल के परिणामों से, 3-रंग की समस्या को एक आलेख के लिए रैखिक समय में हल किया जा सकता है, जो कि निरंतर ट्रीविड्थ के ट्री-अपघटन को देखते हैं।
 == संबंधित पैरामीटर ==
 ===[[ पथचौड़ाई ]]===
-एक ग्राफ़ की पाथविड्थ ट्री डीकंपोज़िशन के माध्यम से ट्रीविड्थ की एक बहुत ही समान परिभाषा है, लेकिन यह ट्री डीकंपोज़िशन तक ही सीमित है जिसमें अपघटन का अंतर्निहित ट्री एक [[पथ ग्राफ]] है। वैकल्पिक रूप से, पाथविड्थ को कॉर्डल ग्राफ़ से ट्रेविड्थ की परिभाषा के अनुरूप [[अंतराल ग्राफ]]़ से परिभाषित किया जा सकता है। नतीजतन, एक ग्राफ की पाथविड्थ हमेशा कम से कम उतनी ही बड़ी होती है, जितनी इसकी ट्रेविड्थ होती है, लेकिन यह केवल एक लघुगणक कारक द्वारा बड़ी हो सकती है।<ref name="b98"/>एक अन्य पैरामीटर, [[ग्राफ बैंडविड्थ]], की [[उचित अंतराल ग्राफ]]़ से समान परिभाषा है, और कम से कम पाथविड्थ जितना बड़ा है। अन्य संबंधित मापदंडों में [[ पेड़ की गहराई ]] शामिल है, एक संख्या जो एक छोटे-बंद ग्राफ़ परिवार के लिए बाध्य है यदि और केवल अगर परिवार एक पथ को छोड़ देता है, और डीजेनेरेसी (ग्राफ़ सिद्धांत), एक ग्राफ़ की विरलता का एक उपाय जो पर है इसकी ट्रेविड्थ के सबसे बराबर।
+एक आलेख की पाथविड्थ ट्री डीकंपोज़िशन के माध्यम से ट्रीविड्थ की एक बहुत ही समान परिभाषा है, लेकिन यह ट्री डीकंपोज़िशन तक ही सीमित है जिसमें अपघटन का अंतर्निहित ट्री एक [[पथ ग्राफ|पथ आलेख]] है। वैकल्पिक रूप से, पाथविड्थ को कॉर्डल आलेख से ट्रीविड्थ की परिभाषा के अनुरूप [[अंतराल ग्राफ|अंतराल]] आलेख से परिभाषित किया जा सकता है। नतीजतन, एक आलेख की पाथविड्थ हमेशा कम से कम उतनी ही बड़ी होती है, जितनी इसकी ट्रीविड्थ होती है, लेकिन यह केवल एक लघुगणक कारक द्वारा बड़ी हो सकती है।<ref name="b98"/>एक अन्य पैरामीटर, [[ग्राफ बैंडविड्थ|आलेख बैंडविड्थ]], की [[उचित अंतराल ग्राफ|उचित अंतराल]] आलेख से समान परिभाषा है, और कम से कम पाथविड्थ जितना बड़ा है। अन्य संबंधित मापदंडों में [[ पेड़ की गहराई | ट्री की गहराई]] सम्मिलित है, एक संख्या जो एक छोटे-बंद आलेख श्रेणी के लिए बाध्य है यदि और केवल अगर श्रेणी एक पथ को छोड़ देता है, और डीजेनेरेसी (आलेख सिद्धांत), एक आलेख की विरलता का एक उपाय जो पर है इसकी ट्रीविड्थ के सबसे बराबर।
 ===ग्रिड लघु आकार===
-क्योंकि एक की ट्रीविड्थ {{math|''n'' × ''n''}} ग्रिड ग्राफ है {{mvar|n}}, ग्राफ की ट्रेविड्थ {{mvar|G}} हमेशा छोटे आकार के सबसे बड़े वर्ग ग्रिड ग्राफ़ के आकार से बड़ा या उसके बराबर होता है {{mvar|G}}. दूसरी दिशा में, [[नील रॉबर्टसन (गणितज्ञ)]] और पॉल सीमोर (गणितज्ञ) द्वारा ग्रिड माइनर प्रमेय से पता चलता है कि एक असीम कार्य मौजूद है {{mvar|f}} जैसे कि सबसे बड़े वर्ग ग्रिड माइनर का आकार कम से कम हो  {{math|''f''(''r'')}} कहाँ {{mvar|r}} ट्रीविड्थ है।<ref>Robertson, Seymour. ''Graph minors. V. Excluding a planar graph''. [http://www.sciencedirect.com/science/article/pii/0095895686900304] {{Open access}}</ref> सबसे अच्छी सीमा पर जाना जाता है {{mvar|f}} वो है {{mvar|f}} कम से कम होना चाहिए {{math|Ω(''r''<sup>''d''</sup>)}} कुछ निश्चित स्थिरांक के लिए {{math|''d'' > 0}}, और अधिक से अधिक<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
+क्योंकि एक की ट्रीविड्थ {{math|''n'' × ''n''}} ग्रिड आलेख है {{mvar|n}}, आलेख की ट्रीविड्थ {{mvar|G}} हमेशा छोटे आकार के सबसे बड़े श्रेणी ग्रिड आलेख के आकार से बड़ा या उसके बराबर होता है {{mvar|G}}. दूसरी दिशा में, [[नील रॉबर्टसन (गणितज्ञ)]] और पॉल सीमोर (गणितज्ञ) द्वारा ग्रिड उपसारणिक प्रमेय से पता चलता है कि एक असीम कार्य मौजूद है {{mvar|f}} जैसे कि सबसे बड़े श्रेणी ग्रिड उपसारणिक का आकार कम से कम हो  {{math|''f''(''r'')}} कहाँ {{mvar|r}} ट्रीविड्थ है।<ref>Robertson, Seymour. ''Graph minors. V. Excluding a planar graph''. [http://www.sciencedirect.com/science/article/pii/0095895686900304] {{Open access}}</ref> सबसे अच्छी सीमा पर जाना जाता है {{mvar|f}} वो है {{mvar|f}} कम से कम होना चाहिए {{math|Ω(''r''<sup>''d''</sup>)}} कुछ निश्चित स्थिरांक के लिए {{math|''d'' > 0}}, और अधिक से अधिक<ref>{{harvtxt|Chekuri|Chuzhoy|2016}}</ref>
 :<math>O \left( \sqrt{ r / \log r} \right).</math>
-के लिए {{math|Ω}} निचले बाउंड में नोटेशन, [[बिग ओ नोटेशन]] देखें। प्रतिबंधित ग्राफ़ परिवारों के लिए सख्त सीमाएँ जानी जाती हैं, जिससे द्विविमता के सिद्धांत के माध्यम से उन परिवारों पर कई ग्राफ़ अनुकूलन समस्याओं के लिए कुशल एल्गोरिदम की ओर अग्रसर होता है।{{sfnp|Demaine|Hajiaghayi|2008}}
+के लिए {{math|Ω}} निचले बाउंड में प्रतीकांकन, [[बिग ओ नोटेशन|बिग ओ प्रतीकांकन]] देखें। प्रतिबंधित आलेख श्रेणीों के लिए सख्त सीमाएँ जानी जाती हैं, जिससे द्विविमता के सिद्धांत के माध्यम से उन श्रेणीों पर कई आलेख अनुकूलन समस्याओं के लिए कुशल कलन विधि की ओर अग्रसर होता है।{{sfnp|Demaine|Hajiaghayi|2008}}
 हैलिन का ग्रिड प्रमेय अनंत रेखांकन के लिए ट्रीविड्थ और ग्रिड लघु आकार के बीच संबंध का एक एनालॉग प्रदान करता है।{{sfnp|Diestel|2004}}
-=== व्यास और स्थानीय वृक्ष चौड़ाई ===
+=== व्यास और स्थानीयट्रीविड्थ ===
-एक परिवार {{mvar|F}सबग्राफ लेने के तहत बंद किए गए ग्राफ़ के बारे में कहा जाता है कि स्थानीय ट्रीविड्थ, या डायमीटर-ट्रीविड्थ गुण, यदि परिवार में ग्राफ़ की ट्रेविड्थ उनके डायमीटर (ग्राफ़ सिद्धांत) के एक फ़ंक्शन द्वारा [[ऊपरी सीमा]] में है। यदि ग्राफ माइनर लेने के अंतर्गत कक्षा को भी बंद माना जाता है, तो {{mvar|F}} ने स्थानीय ट्रेविड्थ को सीमित कर दिया है यदि और केवल यदि के लिए निषिद्ध ग्राफ़ विशेषताओं में से एक है {{mvar|F}} एक [[शीर्ष ग्राफ]] है।{{sfnp|Eppstein|2000}} इस परिणाम के मूल प्रमाणों से पता चला है कि शीर्ष-लघु-मुक्त ग्राफ़ परिवार में ट्रीविड्थ व्यास के कार्य के रूप में सबसे अधिक दोगुनी घातीय रूप से बढ़ता है;<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref> बाद में इसे एकल घातीय तक कम कर दिया गया{{sfnp|Demaine|Hajiaghayi|2008}} और अंत में एक रैखिक सीमा के लिए।{{sfnp|Demaine|Hajiaghayi|2004b}}
+<nowiki>एक श्रेणी {{mvar|F}उप-आलेख लेने के तहत बंद किए गए आलेख के बारे में कहा जाता है कि स्थानीय ट्रीविड्थ, या डायमीटर-ट्रीविड्थ गुण, यदि श्रेणी में आलेख की ट्रीविड्थ उनके डायमीटर (आलेख सिद्धांत) के एक फ़ंक्शन द्वारा </nowiki>[[ऊपरी सीमा]] में है। यदि आलेख उपसारणिक लेने के अंतर्गत कक्षा को भी बंद माना जाता है, तो {{mvar|F}} ने स्थानीय ट्रीविड्थ को सीमित कर दिया है यदि और केवल यदि के लिए निषिद्ध आलेख विशेषताओं में से एक है {{mvar|F}} एक [[शीर्ष ग्राफ|शीर्ष आलेख]] है।{{sfnp|Eppstein|2000}} इस परिणाम के मूल प्रमाणों से पता चला है कि शीर्ष-लघु-मुक्त आलेख श्रेणी में ट्रीविड्थ व्यास के कार्य के रूप में सबसे अधिक दोगुनी घातीय रूप से बढ़ता है;<ref>{{harvtxt|Eppstein|2000}}; {{harvtxt|Demaine|Hajiaghayi|2004a}}.</ref> बाद में इसे एकल घातीय तक कम कर दिया गया{{sfnp|Demaine|Hajiaghayi|2008}} और अंत में एक रैखिक सीमा के लिए।{{sfnp|Demaine|Hajiaghayi|2004b}}
-परिबद्ध स्थानीय ट्रेविड्थ द्विविमीयता के एल्गोरिथम सिद्धांत से निकटता से संबंधित है,<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref> और पहले क्रम तर्क में परिभाषित प्रत्येक ग्राफ संपत्ति को शीर्ष-लघु-मुक्त ग्राफ परिवार के लिए तय किया जा सकता है जो कि केवल थोड़ा सुपरलाइनर है।{{sfnp|Frick|Grohe|2001}}
+परिबद्ध स्थानीय ट्रीविड्थ द्विविमीयता के एल्गोरिथम सिद्धांत से निकटता से संबंधित है,<ref>{{harvtxt|Demaine|Fomin|Hajiaghayi|Thilikos|2004}}; {{harvtxt|Demaine|Hajiaghayi|2008}}.</ref> और पहले क्रम तर्क में परिभाषित प्रत्येक आलेख संपत्ति को शीर्ष-लघु-मुक्त आलेख श्रेणी के लिए तय किया जा सकता है जो कि केवल थोड़ा सुपरलाइनर है।{{sfnp|Frick|Grohe|2001}}
-ग्राफ़ के एक वर्ग के लिए यह भी संभव है कि स्थानीय ट्रेविड्थ को सीमित करने के लिए नाबालिगों के तहत बंद नहीं किया गया है। विशेष रूप से यह बाउंड डिग्री ग्राफ़ के एक वर्ग के लिए तुच्छ रूप से सही है, क्योंकि बाउंडेड व्यास सबग्राफ में बाउंड आकार होता है। एक अन्य उदाहरण [[1-प्लानर ग्राफ]]़ द्वारा दिया गया है, ग्राफ़ जो प्रति किनारे एक क्रॉसिंग के साथ विमान में खींचे जा सकते हैं, और अधिक आम तौर पर उन ग्राफ़ के लिए होते हैं जो बंधे हुए जीनस की सतह पर प्रति किनारे क्रॉसिंग की एक सीमित संख्या के साथ खींचे जा सकते हैं। बंधे हुए स्थानीय ट्रेविड्थ के छोटे-बंद ग्राफ़ परिवारों के साथ, इस संपत्ति ने इन ग्राफ़ों के लिए कुशल सन्निकटन एल्गोरिदम का रास्ता बताया है।{{sfnp|Grigoriev|Bodlaender|2007}}
+आलेख के एक श्रेणी के लिए यह भी संभव है कि स्थानीय ट्रीविड्थ को सीमित करने के लिए उपसारणिकों के तहत बंद नहीं किया गया है। विशेष रूप से यह बाउंड डिग्री आलेख के एक श्रेणी के लिए तुच्छ रूप से सही है, क्योंकि बाउंडेड व्यास उप-आलेख में बाउंड आकार होता है। एक अन्य उदाहरण [[1-प्लानर ग्राफ|1- समतली]] आलेख द्वारा दिया गया है, आलेख जो प्रति किनारे एक क्रॉसिंग के साथ विमान में खींचे जा सकते हैं, और अधिक आम तौर पर उन आलेख के लिए होते हैं जो बंधे हुए जीनस की सतह पर प्रति किनारे क्रॉसिंग की एक सीमित संख्या के साथ खींचे जा सकते हैं। बंधे हुए स्थानीय ट्रीविड्थ के छोटे-बंद आलेख श्रेणीों के साथ, इस संपत्ति ने इन आलेखों के लिए कुशल सन्निकटन कलन विधि का रास्ता बताया है।{{sfnp|Grigoriev|Bodlaender|2007}}
 === हैडविगर संख्या और एस-फ़ंक्शंस ===
-{{harvtxt|Halin|1976}} ग्राफ़ पैरामीटर के एक वर्ग को परिभाषित करता है जिसे वह कॉल करता है {{mvar|S}}-फंक्शंस, जिसमें ट्रीविड्थ शामिल है। ग्राफ माइनर | माइनर-मोनोटोन (एक फ़ंक्शन {{mvar|f}} को माइनर-मोनोटोन के रूप में संदर्भित किया जाता है यदि, जब भी {{mvar|H}} का अवयस्क है {{mvar|G}}, किसी के पास {{math|''f''(''H'') ≤ ''f''(''G'')}}), जब एक नया वर्टेक्स जोड़ा जाता है जो कि [[ सार्वभौमिक शिखर ]] है, और एक क्लिक (ग्राफ थ्योरी) [[ वर्टेक्स विभाजक ]] के दोनों ओर दो सबग्राफ से बड़ा मान लेने के लिए। इस तरह के सभी कार्यों का सेट तत्ववार न्यूनीकरण और अधिकतमकरण के संचालन के तहत एक [[पूर्ण जाली]] बनाता है। इस जाली में शीर्ष तत्व ट्रीविड्थ है, और नीचे का तत्व हैडविगर संख्या है, जो दिए गए ग्राफ में सबसे बड़े पूर्ण ग्राफ ग्राफ का आकार है।
+{{harvtxt|Halin|1976}} आलेख पैरामीटर के एक श्रेणी को परिभाषित करता है जिसे वह कॉल करता है {{mvar|S}}-फंक्शंस, जिसमें ट्रीविड्थ सम्मिलित है। उपसारणिक-मोनोटोन (एक फ़ंक्शन {{mvar|f}} को उपसारणिक-मोनोटोन के रूप में संदर्भित किया जाता है यदि, जब भी {{mvar|H}} का उपसारणिक है {{mvar|G}}, किसी के पास {{math|''f''(''H'') ≤ ''f''(''G'')}}), जब एक नया शीर्ष जोड़ा जाता है जो कि [[ सार्वभौमिक शिखर ]] है, और एक क्लिक (आलेख थ्योरी) [[ वर्टेक्स विभाजक | शीर्ष विभाजक]] के दोनों ओर दो उप-आलेख से बड़ा मान लेने के लिए। इस तरह के सभी कार्यों का समुच्चय तत्ववार न्यूनीकरण और अधिकतमकरण के संचालन के तहत एक [[पूर्ण जाली]] बनाता है। इस जाली में शीर्ष तत्व ट्रीविड्थ है, और नीचे का तत्व हैडविगर संख्या है, जो दिए गए आलेख में सबसे बड़े पूर्ण आलेख आलेख का आकार है।
 ==टिप्पणियाँ==

Anonymous

Search

ट्रीविड्थ: Difference between revisions

Namespaces

More

Page actions

Revision as of 07:24, 14 March 2023

Contents

परिभाषा

उदाहरण