ग्राफ विभाजन समस्या

दूरस्थ कार्य प्रस्ताव। एक ग्राफ विघटन किया जाना चाहिए। अधिकतम-न्यूनतम ग्राफ विभाजन समस्या:
दिया गया
एक अप्रतिम ग्राफ G(V,E,w), जहाँ V एक गैर-खाली सीमित सेट है जो शीर्षकों का है, V={1,...,n}
E={(i,j)∈V×V} किनारों का सेट है
W: E→R एक फ़ंक्शन है जो प्रत्येक किनारे को एक वजन असाइन करता है
(Wij > 0 किनारे (i,j)∈E का वजन है)
खोजें
ग्राफ G का एक द्विभाजन जिसके लिए विभिन्न उपग्राफों से जुड़े कट किनारों का न्यूनतम वजन अधिकतम तक पहुँचता है।