Προβλήματα ΝΡ-πλήρη

Αποδείξτε ότι τα παρακάτω προβλήματα είναι ΝΡ-πλήρη:

A) (Κ,L)-CUT: Δοθέντος ενός γραφήματος G(V,E)  με σύνολο κόμβων V και σύνολο ακμών E, και δύο μη αρνητικών ακεραίων K και L,υπάρχει υποσύνολο κόμβων V’ μεγέθους το πολύ Κ, οι κόμβοι του οποίου να συνδέονται με τουλάχιστον L ακμές με τους κόμβους του V-V’;

B) MAX 3-COLORING: Δοθέντος ενός γραφήματος G(V,E) με σύνολο κόμβων V και σύνολο ακμών E, στο οποίο κάθε κόμβος v_i έχει ένα ακέραιο βάρος w_i, και ενός μη αρνητικού ακεραίου Κ, υπάρχει χρωματισμός (γειτονικοί κόμβοι να μην έχουν ίδιο χρώμα) των κόμβων του G με τρία χρώματα συνολικού βάρους το πολύ Κ; Σε έναν χρωματισμό, κόμβοι ιδίου χρώματος αποτελούν ένα ανεξάρτητο σύνολο. Βάρος ενός ανεξαρτήτου συνόλου S ορίζεται το βάρος του βαρύτερου κόμβου του S. Βάρος του χρωματισμού ορίζεται το άθροισμα των βαρών των ανεξαρτήτων συνόλων που τον αποτελούν.

Υπόδειξη: Για την απόδειξη της ΝΡ-πληρότητας, μπορείτε να χρησιμοποιήσετε τα γνωστά ΝΡ-πλήρη προβλήματα MAXIMUM CUT και GRAPH 3-COLORING