Maximum cut
ग्राफ के लिए, एक अधिकतम कट एक कट है जिसका आकार कम से कम किसी अन्य कट के आकार का होता है। अर्थात्, यह ग्राफ के शीर्षों का दो पूरक सेटों में विभाजन है और, जैसे कि और के बीच किनारों की संख्या यथासंभव बड़ी हो। इस तरह के कट को ढूंढना मैक्स-कट समस्या के रूप में जाना जाता है। समस्या को सरलता से इस प्रकार कहा जा सकता है। कोई भी शीर्ष समूह का एक उपसमुच्चय चाहता है जैसे कि और पूरक उपसमुच्चय के बीच किनारों की संख्या यथासंभव बड़ी हो। समान रूप से, जितना संभव हो उतने किनारों के साथ ग्राफ का एक द्विदलीय उपलेख चाहिए। समस्या का एक अधिक सामान्य संस्करण है जिसे भारित अधिकतम-कटौती कहा जाता है, जहां प्रत्येक किनारा एक वास्तविक संख्या, उसके वजन से जुड़ा होता है, और इसका उद्देश्य किनारों की संख्या के बजाय किनारों और उसके पूरक के बीच के कुल वजन को अधिकतम करना है। सकारात्मक और नकारात्मक दोनों भारों की अनुमति देने वाली भारित अधिकतम-कटौती समस्या को सभी भारों में संकेत को फ़्लिप करके एक भारित न्यूनतम कटौती समस्या में परिवर्तित किया जा सकता है। निचली सीमा एडवर्ड्स ने शीर्ष और किनारों वाले ग्राफ पर मैक्स-कट के लिए निम्नलिखित दो निचली सीमा प्राप्त की ((ए) मनमाना है, लेकिन (बी) में यह जुड़ा हुआ है): (ए) (बी) बाउंड (बी) को अक्सर एडवर्ड्स-एर्डोस बाउंड कहा जाता है जैसा कि एर्डोस ने अनुमान लगाया था। एडवर्ड्स ने एडवर्ड्स-एर्डोस को संभावित विधि का उपयोग करके बाध्य साबित किया; क्राउस्टन एट अल। रैखिक बीजगणित और छद्म-बूलियन कार्यों के विश्लेषण का उपयोग करके सीमा को साबित किया। क्राउस्टन एट अल का प्रमाण। हमें हस्ताक्षरित ग्राफ पर संतुलित उपग्राफ समस्या (बी. एस. पी.) से बंधे एडवर्ड्स-एर्डोस का विस्तार करने की अनुमति देता है, अर्थात। ग्राफ जहाँ प्रत्येक किनारे को + या-सौंपा गया है। सबसेट में विभाजन के लिए और, एक किनारे को संतुलित किया जाता है यदि दोनों और और एक ही सबसेट में हैं, या और और अलग-अलग सबसेट हैं। बी. एस. पी. का लक्ष्य संतुलित किनारों की अधिकतम संख्या के साथ एक विभाजन खोजना है। एडवर्ड्स-एर्डोस प्रत्येक जुड़े हुए हस्ताक्षरित ग्राफ के लिए एक निचली सीमा देता है। ग्राफ के विशेष वर्गों के लिए बाउंड (ए) में सुधार किया गया थाः त्रिभुज-मुक्त ग्राफ, दिए गए अधिकतम डिग्री के ग्राफ,-मुक्त ग्राफ, आदि, उदाहरण के लिए देखें। पोलजाक और तुर्जिक ने एडवर्ड्स-एर्डोस को भारित मैक्स-कट तक विस्तारित कियाः कहाँ और कहाँ हैं और इसका न्यूनतम वजन फैला हुआ पेड़ है। हाल ही में, गुतिन और येओ ने भारित मैक्स-कट के लिए कई निचली सीमाएँ प्राप्त कीं, जो भारित ग्राफ के विशेष वर्गों के लिए मनमाने भारित ग्राफ और सीमाओं के लिए पोलजाक-तुर्जिक को विस्तारित करती हैं। कम्प्यूटेशनल जटिलता अधिकतम कटौती से संबंधित निम्नलिखित निर्णय समस्या का सैद्धांतिक कंप्यूटर विज्ञान में व्यापक रूप से अध्ययन किया गया हैः एक ग्राफ जी और एक पूर्णांक के को देखते हुए, यह निर्धारित करें कि क्या जी में कम से कम के आकार में कटौती है। इस समस्या को एनपी-पूर्ण माना जाता है। यह देखना आसान है कि समस्या एन. पी. में हैः एक बड़ा पर्याप्त कटौती प्रस्तुत करके हाँ उत्तर को साबित करना आसान है। उदाहरण के लिए, समस्या की एन. पी.-पूर्णता को अधिकतम 2-संतुष्टि (अधिकतम संतुष्टि समस्या का प्रतिबंध) से घटाकर दिखाया जा सकता है। निर्णय समस्या का भारित संस्करण कार्प की 21 एन. पी.-पूर्ण समस्याओं में से एक था; कार्प ने विभाजन समस्या से कमी करके एन. पी.-पूर्णता दिखाई। उपरोक्त निर्णय समस्या के विहित अनुकूलन संस्करण को आमतौर पर अधिकतम-कटौती समस्या या अधिकतम-कटौती के रूप में जाना जाता है और इसे इस प्रकार परिभाषित किया जाता हैः ग्राफ जी को देखते हुए, अधिकतम कटौती का पता लगाएं। अनुकूलन संस्करण एन. पी.-हार्ड के रूप में जाना जाता है। इसके विपरीत समस्या, न्यूनतम कटौती खोजने की समस्या को फोर्ड-फुल्करसन एल्गोरिदम के माध्यम से कुशलता से हल करने योग्य माना जाता है। एल्गोरिदम बहुपद-समय एल्गोरिदम चूंकि अधिकतम-कट समस्या एन. पी.-कठोर है, सामान्य ग्राफ में अधिकतम-कट के लिए कोई बहुपद-समय एल्गोरिदम ज्ञात नहीं हैं। हालांकि, समतल ग्राफ में, अधिकतम-कटौती समस्या मार्ग निरीक्षण समस्या के लिए दोहरी है (एक सबसे छोटा दौरा खोजने की समस्या जो कम से कम एक बार एक ग्राफ के प्रत्येक किनारे पर जाता है), इस अर्थ में कि जो किनारे एक ग्राफ जी के अधिकतम कट-सेट से संबंधित नहीं हैं, वे किनारों के दोहरे हैं जो जी के दोहरे ग्राफ के इष्टतम निरीक्षण दौरे में दोगुने हो जाते हैं। इष्टतम निरीक्षण दौरा एक स्व-छेदक वक्र बनाता है जो तल को दो उपसमुच्चय में अलग करता है, बिंदुओं का उपसमुच्चय जिसके लिए वक्र की घुमावदार संख्या सम है और उपसमुच्चय जिसके लिए घुमावदार संख्या विषम है; ये दो उपसमुच्चय एक कटौती बनाते हैं जिसमें सभी किनारे शामिल होते हैं जिनके दोहरे दिखाई देते हैं। मार्ग निरीक्षण समस्या को बहुपद समय में हल किया जा सकता है, और यह द्वैतता समतल ग्राफ के लिए बहुपद समय में अधिकतम कटौती समस्या को भी हल करने की अनुमति देती है। हालांकि अधिकतम-विभाजन समस्या एन. पी.-हार्ड के रूप में जानी जाती है। सन्निकटन एल्गोरिदम अधिकतम-कटौती समस्या ए. पी. एक्स.-कठोर है, जिसका अर्थ है कि कोई बहुपद-समय सन्निकटन योजना (पी. टी. ए. एस.) नहीं है, जो मनमाने ढंग से इष्टतम समाधान के करीब है, जब तक कि पी = एन. पी. न हो। इस प्रकार, प्रत्येक ज्ञात बहुपद-समय सन्निकटन एल्गोरिथ्म एक से सख्ती से कम सन्निकटन अनुपात प्राप्त करता है। एक सरल यादृच्छिक 0.5-approximation एल्गोरिथ्म हैः प्रत्येक शीर्ष के लिए एक सिक्के को यह तय करने के लिए फ़्लिप करें कि विभाजन के किस आधे हिस्से को इसे निर्दिष्ट करना है। उम्मीद में, आधे किनारों को काट दिया जाता है। इस एल्गोरिथ्म को सशर्त संभावनाओं की विधि के साथ विकृत किया जा सकता है; इसलिए एक सरल नियतात्मक बहुपद-समय 0.5-approximation एल्गोरिथ्म भी है। ऐसा एक एल्गोरिथ्म दिए गए ग्राफ के शीर्षों के मनमाने विभाजन के साथ शुरू होता है और बार-बार विभाजन के एक तरफ से दूसरे तरफ एक शीर्ष को स्थानांतरित करता है, प्रत्येक चरण में समाधान में सुधार करता है, जब तक कि इस प्रकार का कोई और सुधार नहीं किया जा सकता है। पुनरावृत्तियों की संख्या अधिक से अधिक है क्योंकि एल्गोरिथ्म प्रत्येक चरण में कम से कम एक किनारे से कटौती में सुधार करता है। जब एल्गोरिथ्म समाप्त हो जाता है, तो प्रत्येक शीर्ष पर आने वाले किनारों का कम से कम आधा हिस्सा कट से संबंधित होता है, अन्यथा शीर्ष को स्थानांतरित करने से कट में सुधार होगा। इसलिए, कटौती में कम से कम किनारे शामिल होते हैं। मैक्स-कट के लिए बहुपद-समय सन्निकटन एल्गोरिथ्म सबसे प्रसिद्ध सन्निकटन अनुपात के साथ गोमैन और विलियमसन द्वारा अर्ध-परिमित प्रोग्रामिंग और यादृच्छिक गोल का उपयोग करने वाली एक विधि है जो एक सन्निकटन अनुपात प्राप्त करती है जहां यदि अद्वितीय खेल अनुमान सही है, तो यह अधिकतम कटौती के लिए सबसे अच्छा संभव सन्निकटन अनुपात है। इस तरह की अप्रमाणित धारणाओं के बिना, अनुमान अनुपात के साथ अधिकतम-कटौती मूल्य का अनुमान लगाना एन. पी.-कठिन साबित हुआ है। ओपन-सोर्स कार्यान्वयन सहित इस समस्या के लिए 10 ह्यूरिस्टिक्स का एक विस्तारित विश्लेषण है। मानकीकृत एल्गोरिदम और कर्नेलाइजेशन हालांकि यह साबित करना तुच्छ है कि कम से कम आकार (पैरामीटर) k का एक कट खोजने की समस्या फिक्स्ड-पैरामीटर ट्रैक्टेबल (FPT) है, यह तय करने की समस्या के लिए फिक्स्ड-पैरामीटर ट्रैक्टेबिलिटी दिखाना बहुत कठिन है कि क्या एक ग्राफ G में कम से कम एडवर्ड्स-एर्डोस लोअर बाउंड (ऊपर निचली सीमा देखें) प्लस (पैरामीटर) k. क्राउस्टन एट अल। यह साबित किया कि समस्या को समय पर हल किया जा सकता है और आकार की एक गुठली स्वीकार करता है। क्राउस्टन एट अल। बैलेंस्ड सबग्राफ प्रॉब्लम (बी. एस. पी., ऊपर निचली सीमा देखें) के लिए निश्चित-पैरामीटर ट्रैक्टेबिलिटी परिणाम का विस्तार किया और कर्नेल के आकार में सुधार किया (बी. एस. पी. के लिए भी)। Etscheid और Mnich ने बी. एस. पी. के लिए निश्चित-पैरामीटर ट्रैक्टेबिलिटी परिणाम और शीर्षों के लिए कर्नेल-आकार परिणाम में सुधार किया। अनुप्रयोग मशीन लर्निंग इसके नोड्स को विशेषताओं के रूप में और इसके किनारों को दूरी के रूप में मानते हुए, अधिकतम कट एल्गोरिथ्म एक ग्राफ को दो अच्छी तरह से अलग किए गए उपसमुच्चय में विभाजित करता है। दूसरे शब्दों में, इसे स्वाभाविक रूप से द्विआधारी वर्गीकरण करने के लिए लागू किया जा सकता है। अधिक सामान्य वर्गीकरण एल्गोरिदम की तुलना में, इसे एक सुविधा स्थान की आवश्यकता नहीं है, केवल भीतर के तत्वों के बीच की दूरी। सैद्धांतिक भौतिकी सांख्यिकीय भौतिकी और अव्यवस्थित प्रणालियों में, मैक्स कट समस्या एक स्पिन ग्लास मॉडल के हैमिल्टनियन को न्यूनतम करने के बराबर है, सबसे सरल रूप से आइसिंग मॉडल। ग्राफ जी पर आइसिंग मॉडल के लिए और केवल निकटतम-पड़ोसी अंतःक्रियाओं के लिए, हैमिल्टनियन है यहाँ ग्राफ का प्रत्येक शीर्ष i एक स्पिन साइट है जो एक स्पिन मान ले सकता है एक स्पिन विन्यास विभाजन दो सेटों में, स्पिन अप के साथ और स्पिन डाउन के साथ हम किनारों के सेट के साथ दर्शाते हैं जो दो सेटों को जोड़ते हैं। फिर हम हैमिल्टनियन को फिर से लिख सकते हैं क्योंकि इस ऊर्जा को कम करना न्यूनतम-कटौती समस्या के बराबर है या ग्राफ भार को अधिकतम-कटौती समस्या के रूप में निर्धारित करना है। सर्किट डिजाइन अधिकतम कटौती समस्या के वी. एल. एस. आई. डिजाइन में अनुप्रयोग हैं। न्यूनतम कट न्यूनतम के-कट विषम चक्र पारगमन भी देखें, जो सबसे बड़े द्विदलीय प्रेरित उपग्राफ गैर-अनुकूल विभाजन के लिए पूछने के बराबर है, जो अनंत ग्राफ नोट्स संदर्भों के लिए एक संबंधित अवधारणा है। .. अधिकतम कटौती (अनुकूलन संस्करण) परिशिष्ट बी (पृष्ठ 399) में एन. डी. 14 समस्या है। .. .. .. .. .. .. .. .. .. अधिकतम कटौती (निर्णय संस्करण) परिशिष्ट ए2.2 में समस्या एन. डी. 16 है। अधिकतम द्विदलीय उपलेख (निर्णय संस्करण) परिशिष्ट ए1.2 में समस्या जी. टी. 25 है। .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. बाहरी लिंक पियरलुइगी क्रेसेंज़ी, विगो कन्न, मैग्नस हेल्डोर्सन, मारेक कार्पिंस्की, गेरहार्ड वोजिंगर (2000), "मैक्सिमम कट", "एनपी अनुकूलन समस्याओं का एक संग्रह" में। एंड्रिया कैसिनी, निकोला रिबाग्लियाटी (2012), "मैक्स कट को हल करने के लिए एक पायथन पुस्तकालय" ग्राफ सिद्धांत ने संयोजन अनुकूलन एन. पी.-पूर्ण समस्याओं को ग्राफ सिद्धांत में कम्प्यूटेशनल समस्याओं के रूप में प्रस्तुत किया।