Bonjour,
On définie le problème K-part comme ceci :
Données : un graphe G=(X,A)
Question : existe-t-il une partition de X en K sous ensembles X1, X2... tels que tous ces sont graphes soient complets (possèdes toutes les arrêtes possibles)
On admet que 3-part est NP-complet, démontrer à partir de 3-Par que 4-Part est NP-complet.
Alors on prouver que 4-Part est NP pas de problème mais après pour trouver la bonne instance et montrer la conservation de la réponse je ne m'en sors pas
Pouvez-vous m'aider ?
Merci
-----