ट्रीविड्थ

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

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

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

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

परिभाषा

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

एक आलेख G = (V, E) का ट्री अपघटन एक ट्री T है जिसमें बिंदु X₁, …, X_n, जहां प्रत्येक X_i का एक उपसमुच्चय V है, जो निम्नलिखित गुणों को संतुष्ट करता हैː

1. सम्पूर्ण समुच्चयों का संघ X_i V के समान है, अर्थात, प्रत्येक आलेख शीर्ष कम से कम एक ट्री बिंदु में समाहित है।
2. यदि X_i और X_j दोनों में एक शीर्ष v है, तो X_i और X_j के मध्य (अद्वितीय) पथ में T के सम्पूर्ण बिंदु X_k में v भी सम्मिलित है। समतुल्य रूप से, ट्री बिंदु में शीर्ष v होते है, और T के सम्बद्ध सबट्री का निर्माण किया जाता है।
3. आलेख में प्रत्येक किनारो (v, w) के लिए, एक उपसमुच्चय X_i है जिसमें v और w दोनों सम्मिलित हैं, अर्थात, शीर्ष आलेखों में आसन्न होते हैं, जब संबंधित सबट्री में एक सामान्य बिंदु होता है।

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

सामान्य रूप से, G की ट्रीविड्थ पृष्ठरज्जु आलेख में सबसे छोटे गुट्ट के आकार से एक कम है, जिसमें G सबसे छोटी गुट्ट संख्या है। इस गुट्ट के आकार के साथ एक पृष्ठरज्जु आलेख G को प्रत्येक दो शीर्षों के मध्य जोड़कर प्राप्त किया जा सकता है, जो दोनों समुच्चयों में से कम से कम एक समुच्चय X_i से संबंधित हैं।

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

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

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

उदाहरण

प्रत्येक पूर्ण आलेख K_n में ट्रीविड्थ n – 1 है। पृष्ठरज्जु आलेख के संदर्भ में ट्रीविड्थ की परिभाषा का उपयोग करके इसे सरलता से देखा जा सकता है: सम्पूर्ण आलेख पहले से ही पृष्ठरज्जु है, और अधिक किनारों को जोड़ने से इसके सबसे बड़े समूह के आकार को कम नहीं किया जा सकता है।

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

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

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

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

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

1. F परिबद्ध -ट्रीविड्थ आलेख की उपसारणिक-अवरुद्ध श्रेणी है;
2. F की विशेषता वाले बहुत से निषिद्ध उपसारणिको में से एक समतलीय है;
3. F एक उपसारणिक-अवरुद्ध आलेख श्रेणी है जिसमें सभी समतलीय आलेख सम्मिलित नहीं हैं

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

ट्रीविड्थ 3 के लिए चार प्रतिबंधित उपसारणिक: K₅ (शीर्ष-बाएँ), अष्टफलक का आलेख (नीचे-बाएँ), वैगनर आलेख (शीर्ष-दाएँ), और पंचकोणीय वर्णक्रम का आलेख (नीचे-दाएँ) है।

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

• k = 1 के लिए, अद्वितीय निषिद्ध उपसारणिक 3-शीर्ष चक्र आलेख है।
• k = 2 के लिए, अद्वितीय निषिद्ध उपसारणिक 4-शीर्ष पूर्ण आलेख K₄ है।
• k = 3 के लिए, चार निषिद्ध उपसारणिक K₅ हैं, अष्टफलक का आलेख, पंचकोणीय वर्णक्रम आलेख और वैगनर आलेख इनमें से दो बहुफलकीय आलेख समतलीय हैं।

k के बड़े मानों के लिए, निषिद्ध उपसारणिक की संख्या कम से कम उतनी ही तीव्रता से बढ़ती है जितनी कि k के वर्गमूल की चरघातांकी होती है। हालांकि, निषिद्ध उपसारणिक के आकार और संख्या पर ज्ञात ऊपरी सीमाएं इस निचली सीमा से बहुत अधिक हैं।

कलन विधि

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

यह निर्धारित करने के लिए एनपी-पूर्ण है। किसी दिए गए आलेख G में किसी दिए गए चर k पर ट्रीविड्थ है या नहीं है।

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

एक बड़ी संख्या में क्षेत्रों में ट्रीविड्थ की भूमिकाओं के कारण, आलेख के ट्रीविड्थ की गणना करने वाले विभिन्न व्यावहारिक और सैद्धांतिक कलन विधि विकसित की गई थी। आवेदन के आधार पर, कोई उन्नत सन्निकटन अनुपात, या इनपुट के आकार या ट्रीविड्थ से चलने वाले समय में उन्नत निर्भरता पसंद कर सकता है। नीचे दी गई तालिका में कुछ ट्रीविड्थ की कलन विधि का अवलोकन किया गया है। जहाँ k ट्रीविड्थ है और n एक इनपुट आलेख G के शीर्षों की संख्या है।

प्रत्येक कलन विधि समय में f(k) ⋅ g(n) अनुमानित स्तम्भ में दी गई चौड़ाई का अपघटन करता है। उदाहरण लिए, समय 2^O(k3)⋅n में बोडलैंडर (1996) की कलन विधि या तो अधिकतम k पर चौड़ाई के इनपुट आलेख G के ट्री अपघटन का निर्माण या विवरण करता है कि G की ट्रीविड्थ k से अधिक है। इसी प्रकार, बोडलैंडर एट अल (2016) समय 2^O(k)⋅n में या तो अधिकतम 5k + 4 चौड़ाई के इनपुट आलेख G के ट्री अपघटन का निर्माण या विवरण करता है कि G की ट्रीविड्थ k से अधिक है, कोरहोनेन (2021) ने समान संचालन समय में इसे सुधार कर 2k + 1 कर दिया है।

सन्निकटन	f(k)	g(n)	संदर्भ
यथार्थ	O(1)	O(nk+2)	अर्नबोर्ग, कॉर्नियल & प्रोस्कुरोव्स्की (1987)
4k + 3	O(33k)	O(n2)	रॉबर्टसन & सेमुर (1995)
8k + 7	2O(k log k)	n log2 n	लेगरग्रेन (1996)
5k + 4 (or 7k + 6)	2O(k log k)	n log n	रीड (1996)
यथार्थ	2O(k3)	O(n)	बोडलैंडर (1996)
$O\left(k\cdot {\sqrt {\log k}}\right)$	O(1)	nO(1)	फीज, हजियाघयी & ली (2008)
4.5k + 4	23k	n2	आमिर (2010)
11/3k + 4	23.6982k	n3 log4n	आमिर (2010)
यथार्थ	O(1)	O(1.7347n)	फोमिन, टोडिंका & विलंगेर (2015)
3k + 2	2O(k)	O(n log n)	बोडलैंडर et al. (2016)
5k + 4	2O(k)	O(n)	बोडलैंडर et al. (2016)
k2	O(k7)	O(n log n)	फोमिन et al. (2018)
5k + 4	28.765k	O(n log n)	बेलबासी & फ्यूरर (2021a)
2k + 1	2O(k)	O(n)	कोरहोनेन (2021)
5k + 4	26.755k	O(n log n)	बेलबासी & फ्यूरर (2021b)
यथार्थ	2O(k2)	n4	कोरहोनेन & लोकशतानोव (2022)
(1+$\varepsilon$)k	kO(k/$\varepsilon$)	n4	कोरहोनेन & लोकशतानोव (2022)

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

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

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

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

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

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

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

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

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

Main article: कौरसेल की प्रमेय

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

• तर्क संचालन, जैसे $\wedge ,\vee ,\neg ,\Rightarrow$
• सदस्यता परीक्षण, जैसे e ∈ E, v ∈ V
• शीर्षों, किनारों, शीर्षों के समुच्चयों और/या किनारों के समुच्चयों पर परिमाणीकरण, जैसे ∀v ∈ V, ∃e ∈ E, ∃I ⊆ V, ∀F ⊆ E
• निकटता परीक्षण (u का समापन बिंदु e है), और कुछ विस्तारण जो अनुकूलीकरण जैसी चीज़ों की अनुमति देते हैं।

उदाहरण, आलेख के लिए तीनों रंगों की समस्या पर विचार करें। एक आलेख G = (V, E) के लिए, यह समस्या है कि क्या तीनों रंगों के प्रत्येक शीर्ष v ∈ V को निर्दिष्ट करना संभव है, ताकि कोई भी दो आसन्न शीर्षों को एक ही रंग में निर्दिष्ट न किया जा सके। इस समस्या को एक अक द्वितीय-क्रम तर्क में निम्नानुसार व्यक्त किया जा सकता है:

$\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₁, W₂, W₃ तीनों रंगों में से प्रत्येक शीर्षों के उपसमुच्चय का प्रतिनिधित्व करते हैं।

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

संबंधित मापदण्ड

पाथविड्थ

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

संजाल उपसारणिक आकार

क्योंकि एक n × n संजाल आलेख की ट्रीविड्थ n है, आलेख G की ट्रीविड्थ सदैव G के सबसे बड़े श्रेणी संजाल आलेख के आकार से बड़ी या उसके बराबर होती है। दूसरी दिशा में, नील रॉबर्टसन और पॉल सीमोर के द्वारा संजाल उपसारणिक की प्रमेय को दर्शाया जाता है कि एक असीमित फलन f उपस्थित है जैसे कि सबसे बड़े वर्ग संजाल उपसारणिक का आकार कम से कम f(r) है जहां r ट्रीविड्थ है। f पर ज्ञात सर्वोत्तम सीमाएँ हैं कि और कुछ निश्चित स्थिरांक d > 0 के लिए, f को कम से कम Ω(r^d) होना चाहिए।

$O\left({\sqrt {r/\log r}}\right).$

निचले परिबद्ध में Ω संकेतन के लिए , बिग ओ संकेतन देखें। प्रतिबंधित आलेख श्रेणीयों के लिए घनिष्ठ सीमाएँ हैं, जिससे द्विविमता के सिद्धांत के माध्यम से श्रेणीयों पर कई आलेख अनुकूलन समस्याओं के लिए कुशल कलन विधि की ओर अग्रसर करता है।

हैलिन की संजाल प्रमेय अनंत आलेख के लिए ट्रीविड्थ और संजाल उपसारणिक आकार के मध्य संबंध का एक तुल्यरूप प्रदान करती है।

व्यास और स्थानीय ट्रीविड्थ

एक उप-आलेख के अंतर्गत अवरुद्ध किए गए आलेख की एक श्रेणी को कहा जाता है कि स्थानीय ट्रीविड्थ, या व्यास-ट्रीविड्थ गुण से घिरा हुआ है, यदि श्रेणी में आलेख की ट्रीविड्थ उनके व्यास के एक फलन द्वारा ऊपरी सीमाबद्ध है। यदि आलेख उपसारणिको के अंतर्गत कक्षा को भी अवरुद्ध माना जाता है, तो F ने स्थानीय ट्रीविड्थ को बाध्य कर देता है और यदि केवल F के लिए निषिद्ध उपसारणिको में से एक शीर्ष आलेख है। इस परिणाम के मूल प्रमाणों से ज्ञात होता है कि शीर्ष-उपसारणिक-मुक्त आलेख श्रेणी में ट्रीविड्थ व्यास के फलन के रूप में सबसे अधिक दोगुनी घातीय रूप से बढ़ती है; पश्चात इसे एकल घातांक और अंत में एक रैखिक सीमा तक कम कर दिया जाता है।

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

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

हैडविगर संख्या और एस-फलन

हैलिन (1976) आलेख मापदण्ड के एक श्रेणी को परिभाषित करता है जिसे S-फलन कहा जाता है, जिसमें ट्रीविड्थ सम्मिलित है। आलेख से लेकर पूर्णांक तक के कार्यों को बिना किनारों वाले आलेख पर शून्य होना आवश्यक है, लघु-एकदिष्ट होने के लिए (फलन f को "लघु-एकदिष्ट" के रूप में संदर्भित किया जाता है यदि, जब भी H, G का उपसारणिक हो, तो एक के पास किसी के पास f(H) ≤ f(G) होता है), और जब एक नया शीर्ष जोड़ा जाता है जो पिछले सम्पूर्ण शीर्षों के निकट होता है, और एक गुट्ट विभाजक के दोनों ओर दो उप-आलेख से बड़ा मान लेने के लिए है। इस तरह के सम्पूर्ण कार्यों का समुच्चय तत्ववार न्यूनीकरण और अधिकतमकरण के संचालन के अंतर्गत एक सम्पूर्ण जालक बनाता है। इस जालक में शीर्ष तत्व ट्रीविड्थ है, और नीचे का तत्व हैडविगर संख्या है, जो दिए गए आलेख में सबसे बड़े पूर्ण उपसारणिक का आकार है।

संदर्भ

• 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].