Cutwidth
ग्राफ सिद्धांत में, एक दिशाहीन ग्राफ की कटविड्थ निम्नलिखित गुण के साथ सबसे छोटा पूर्णांक हैः ग्राफ के शीर्षों का एक क्रम होता है, जैसे कि शीर्षों को क्रम के पहले और बाद के उपसमुच्चय में विभाजित करके प्राप्त प्रत्येक कट को अधिकांश किनारों से पार किया जाता है। अर्थात्, यदि शीर्षों को क्रमांकित किया जाता है, तो प्रत्येक के लिए, और के साथ किनारों की संख्या अधिक से अधिक है। ग्राफ की कटविड्थ को इसकी तह संख्या भी कहा जाता है। कटविड्थ उत्पन्न करने वाले शीर्ष क्रम और इस क्रम और कटविड्थ की गणना करने की समस्या दोनों को न्यूनतम कट रैखिक व्यवस्था कहा गया है। अन्य मापदंडों से संबंध कटविड्थ ग्राफ के कई अन्य चौड़ाई मापदंडों से संबंधित है। विशेष रूप से, यह हमेशा कम से कम उसी ग्राफ की त्रि-चौड़ाई या पथ-चौड़ाई जितना बड़ा होता है। हालाँकि, यह अधिक से अधिक पथ चौड़ाई से गुणा किया जाता है, या त्रि चौड़ाई से गुणा किया जाता है जहाँ अधिकतम डिग्री है और शीर्षों की संख्या है। यदि आलेखों के एक परिवार ने अधिकतम डिग्री को सीमित किया है, और इसके आलेखों में असीमित आकार के पूर्ण द्विआधारी पेड़ों के उपखंड नहीं हैं, तो परिवार में आलेखों ने कटविड्थ को सीमित किया है। सबक्यूबिक ग्राफ (अधिकतम डिग्री तीन के ग्राफ) में, कटविड्थ पथविड्थ प्लस एक के बराबर होती है। कटविड्थ किसी भी ग्राफ की न्यूनतम द्विभाजन संख्या से अधिक या उसके बराबर होती है। समान आकार के दो उपसमुच्चय में शीर्षों के विभाजन के लिए एक तरफ से दूसरी तरफ किनारों की यह न्यूनतम संभव संख्या है (या जितना संभव हो उतना बराबर)। ग्राफ का कोई भी रैखिक लेआउट, अपनी इष्टतम कटविड्थ प्राप्त करते हुए, समान संख्या में किनारों के साथ एक द्विभाजन भी प्रदान करता है, जो लेआउट को उसके पहले और दूसरे हिस्सों में विभाजित करके प्राप्त किया जाता है। कटविड्थ ग्राफ बैंडविड्थ द्वारा गुणा की गई अधिकतम डिग्री से कम या उसके बराबर होती है, इस मात्रा को कम करने के लिए चुनी गई रैखिक व्यवस्था में किसी भी किनारे के अंतिम बिंदुओं को अलग करने वाले चरणों की अधिकतम संख्या। बैंडविड्थ के विपरीत, कटविड्थ तब अपरिवर्तित रहती है जब किनारों को एक से अधिक किनारों के पथों में विभाजित किया जाता है। यह "टोपोलॉजिकल बैंडविड्थ" से निकटता से संबंधित है, न्यूनतम बैंडविड्थ जिसे किसी दिए गए ग्राफ के किनारों को उपविभाजित करके प्राप्त किया जा सकता है। विशेष रूप से, किसी भी पेड़ के लिए यह टोपोलॉजिकल बैंडविड्थ और थोड़ी बड़ी संख्या के बीच सैंडविच किया जाता है। एक अन्य पैरामीटर, जिसे एक ग्राफ में कटौती में फैले किनारों की संख्या के संदर्भ में कटविड्थ के समान परिभाषित किया गया है, नक्काशी की चौड़ाई है। हालांकि, शीर्षों के एक रैखिक क्रम और कटौती के एक रैखिक अनुक्रम का उपयोग करने के बजाय, जैसा कि कटविड्थ में होता है, नक्काशी की चौड़ाई शीर्षों के एक पदानुक्रमित समूह से प्राप्त कटौती का उपयोग करती है, जिससे यह तीन चौड़ाई या शाखा चौड़ाई से अधिक निकटता से संबंधित होती है और पथ चौड़ाई या बैंडविड्थ जैसे रैखिक क्रम वाले अन्य चौड़ाई मापदंडों के समान होती है। कटविड्थ का उपयोग ग्राफ ड्राइंग के अध्ययन में उत्पन्न होने वाले एक अन्य पैरामीटर, क्रॉसिंग नंबर पर निचली सीमा प्रदान करने के लिए किया जा सकता है। ग्राफ की पार करने की संख्या किनारों के जोड़े की न्यूनतम संख्या है जो एक दूसरे को काटते हैं, समतल में ग्राफ के किसी भी चित्र में जहां प्रत्येक शीर्ष केवल उन किनारों को छूता है जिनके लिए यह एक अंतिम बिंदु है। बाउंडेड डिग्री के ग्राफ में, क्रॉसिंग संख्या हमेशा कम से कम कटविड्थ के वर्ग के समानुपाती होती है। एक अधिक सटीक सीमा, उन ग्राफों पर लागू होती है जहां डिग्री सीमित नहीं हैं, यह हैः यहाँ, सुधार शब्द, वर्ग डिग्री के योग के समानुपाती, समतल ग्राफों के अस्तित्व के लिए आवश्यक है जिनकी वर्ग कटविड्थ इस मात्रा के समानुपाती है लेकिन जिनकी पार करने की संख्या शून्य है। ग्राफ ड्राइंग की एक अन्य शैली में, पुस्तक एम्बेडिंग, शीर्षों को एक रेखा पर व्यवस्थित किया जाता है और किनारों को इस रेखा पर मिलने वाले अलग-अलग अर्ध-समतल पृष्ठों में पार किए बिना व्यवस्थित किया जाता है। एक ही शीर्ष क्रम का उपयोग करते हुए, एक पुस्तक एम्बेडिंग की पृष्ठ चौड़ाई को किसी भी पृष्ठ की सबसे बड़ी कटविड्थ के रूप में परिभाषित किया गया है। कम्प्यूटेशनल जटिलता कटविड्थ पाई जा सकती है, और शीर्षों के पेड़ के लिए समय पर इष्टतम चौड़ाई का एक रैखिक लेआउट बनाया जा सकता है। अधिक सामान्य ग्राफ के लिए, यह एन. पी.-हार्ड है। समतल ग्राफ के लिए भी यह एन. पी.-कठोर बना रहता है, और समस्या का एक भारित संस्करण (एक रैखिक व्यवस्था के किसी भी कट में किनारों के वजन को कम करना) एन. पी.-कठोर होता है, तब भी जब इनपुट एक वृक्ष होता है। कटविड्थ इष्टतम रैखिक व्यवस्था की कई समस्याओं में से एक है जिसे गतिशील प्रोग्रामिंग का उपयोग करके हेल्ड-कार्प एल्गोरिदम द्वारा ठीक समय पर हल किया जा सकता है। समय के साथ एक तेज क्वांटम एल्गोरिथ्म भी जाना जाता है। इसके अतिरिक्त, यह निश्चित-पैरामीटर ट्रैक्टेबल हैः के किसी भी निश्चित मूल्य के लिए, यह परीक्षण करना संभव है कि क्या एक ग्राफ में अधिक से अधिक कटविड्थ है, और यदि ऐसा है तो रैखिक समय में इसके लिए एक इष्टतम शीर्ष क्रम खोजें। अधिक सटीक रूप से, दोनों के संदर्भ में और, इस एल्गोरिथ्म का चलने का समय है। एक वैकल्पिक मानकीकृत एल्गोरिथ्म, ग्राफ के लिए अधिक उपयुक्त है जिसमें कुछ शीर्षों में उच्च डिग्री होती है (कटविड्थ बड़ी होती है) इसके बजाय समय बहुपद में समस्या का समाधान करता है जब ग्राफ में सीमित आकार का एक शीर्ष आवरण होता है, इसे कुछ चर और चर मूल्यों पर बहुपद सीमाओं के साथ एक पूर्णांक प्रोग्रामिंग समस्या में बदलकर। यह खुला रहता है कि क्या समस्या को बंधे हुए त्रि-चौड़ाई के ग्राफ के लिए कुशलता से हल किया जा सकता है, जो कटविड्थ और वर्टेक्स कवर नंबर द्वारा दोनों मापदंडों को शामिल करेगा। कटविड्थ में घने ग्राफों के लिए एक बहुपद-समय सन्निकटन योजना है, लेकिन उन ग्राफों के लिए जो घने नहीं हो सकते हैं, ज्ञात सबसे अच्छा सन्निकटन अनुपात है। यह टॉम लीटन और सतीश राव की एक विधि से आता है, जिसमें शीर्षों को क्रमबद्ध करने के लिए पुनरावर्ती द्विभाजन का उपयोग करके अनुमानित कटविड्थ को न्यूनतम द्विभाजन संख्या में कम किया जाता है, जिससे अनुमानित अनुपात में एक कारक खो जाता है। न्यूनतम द्विभाजन संख्या का अनुमान लगाने के लिए संजीव अरोड़ा, राव और उमेश वजीरानी की एक अन्य विधि के साथ इस पुनरावर्ती द्विभाजन विधि का संयोजन, बताए गए सन्निकटन अनुपात को देता है। लघु समुच्चय विस्तार परिकल्पना के तहत, एक स्थिर सन्निकटन अनुपात प्राप्त करना संभव नहीं है। अनुप्रयोग कटविड्थ के लिए एक प्रारंभिक प्रेरक अनुप्रयोग में वी. एल. एस. आई. डिजाइन में चैनल रूटिंग शामिल है, जिसमें एक एकीकृत परिपथ के आयताकार क्षेत्र के ऊपर और नीचे की ओर व्यवस्थित घटकों को कंडक्टरों द्वारा जोड़ा जाना चाहिए जो घटकों से जुड़े जोड़े पिन को जोड़ते हैं। यदि घटकों को अलग-अलग बाएँ-से-दाएँ क्रम में व्यवस्थित करने के लिए स्वतंत्र हैं, लेकिन प्रत्येक घटक के पिन सन्निहित रहने चाहिए, तो इसे प्रत्येक घटक के लिए एक शीर्ष और प्रत्येक पिन-से-पिन कनेक्शन के लिए एक किनारे के साथ ग्राफ की एक रैखिक व्यवस्था चुनने की समस्या में अनुवादित किया जा सकता है। ग्राफ की कटविड्थ सर्किट को रूट करने के लिए आवश्यक चैनलों की संख्या को नियंत्रित करती है। प्रोटीन इंजीनियरिंग में, एक धारणा कि एक संबंधित ग्राफ ने कटविड्थ को सीमित कर दिया है, का उपयोग एम. आर. एन. ए. अनुक्रमों की खोज को तेज करने के लिए किया गया है जो एक साथ दिए गए प्रोटीन अनुक्रम के लिए कोड करते हैं और एक दी गई माध्यमिक संरचना में मोड़ते हैं। निर्देशित एसाइक्लिक ग्राफ पर लागू होने वाली समस्या का एक भारित संस्करण, और केवल ग्राफ किनारों के अभिविन्यास के अनुरूप रैखिक क्रम की अनुमति देता है, कम्प्यूटेशनल कार्यों के एक अनुक्रम को इस तरह से निर्धारित करने के लिए लागू किया गया है जो अनुसूची में आवश्यक स्मृति की अधिकतम मात्रा को कम करता है, दोनों कार्यों के लिए और कार्य-से-कार्य संचार के लिए उपयोग किए जाने वाले डेटा को बनाए रखने के लिए। डेटाबेस सिद्धांत में, कटविड्थ समस्या की एन. पी.-कठोरता का उपयोग यह दिखाने के लिए किया गया है कि जॉइन करते समय डिस्क और मुख्य मेमोरी के बीच डेटा के ब्लॉकों के हस्तांतरण को निर्धारित करना भी एन. पी.-कठिन है, ताकि मुख्य मेमोरी की सीमित मात्रा के भीतर गणना को फिट करते हुए एक ही ब्लॉक के बार-बार हस्तांतरण से बचा जा सके। ग्राफ ड्राइंग में, साथ ही संख्या को पार करने के लिए निचली सीमा में लागू किया जा रहा है, एक विशिष्ट प्रकार के त्रि-आयामी ग्राफ ड्राइंग के अध्ययन में कटविड्थ लागू की गई है, जिसमें किनारे को अधिकतम एक मोड़ के साथ असंबद्ध बहुभुज श्रृंखलाओं के रूप में दर्शाया जाता है, शीर्षों को एक रेखा पर रखा जाता है, और सभी शीर्षों और मोड़ बिंदुओं में पूर्णांक निर्देशांक होने चाहिए। इस प्रकार के चित्रों के लिए, रेखाचित्र के बाउंडिंग बॉक्स की न्यूनतम मात्रा कम से कम कटविड्थ को शीर्षों की संख्या से गुणा करने के समानुपाती होनी चाहिए। इस आयतन के साथ हमेशा एक रेखाचित्र मौजूद रहता है, जिसमें शीर्षों को एक अक्ष-समानांतर रेखा पर रखा जाता है। संदर्भ ग्राफ अपरिवर्तनीय