Les nombres optimisés de variables et de clauses pour coder un problème de coloriage graphique dans CNF

Question

Déclaration de problème

Étant donné un graphique fini $ G = langle v, e Hangle $, composé de vertic $ V $ et set de bord $ E $, et un ensemble fini de couleurs $ C $, une instance de problème de Coloriage du graphique est d'attribuer chaque sommet $ v in v $ un $ text {couleur} (v) en c $ tel que $ forall langle v, w marche. Maintenant nous encoder Une instance de problème de coloriage graphique dans un CNF (formule normale conjonctive) $ F $.

Remarque: Le mot «Encoder» signifie que nous connaîtrons un problème de coloriage de graphique si un CNF est donné, et connaîtra également un CNF si un problème de coloriage graphique est donné.

• Quel est le nombre minimal de variables propositionnelles dans $ F $?
• Quel est le nombre minimal de clauses dans $ F $?

Version originale

Une solution à un Coloriage du graphique Le problème est une affectation de couleurs aux sommets de sorte qu'aucun sommet adjacent n'a la même couleur. Formellement, un graphique fini $ G = langle v, e Hangle $ se compose de sommets $ V = {v_1, cdots, v_n } $ et les bords $ E = { langle v_ {i_1}, w_ {i_1} rangle, cdots, Langle v_ {i_k}, w_ {i_k} rangle } $. L'ensemble fini de couleurs est donné par $ C = {c_1, cdots, c_m } $. Une instance de problème est donnée par un graphique et un ensemble de couleurs: le problème est d'attribuer chaque sommet $ v in v $ un $ text {couleur} (v) en c $ de tel que pour chaque bord $ langle V, w Hangle in e $, $ text {couleur} (v) not = text {couleur} (w) $. De toute évidence, tous les cas n'ont pas de solutions.

Montrez comment coder une instance d'un problème de coloriage graphique dans une formule PL $ F $. $ F $ devrait être satisfait si une coloration graphique existe.

1. Décrivez un ensemble de contraintes dans PL affirmant que chaque sommet est coloré. Étant donné que les ensembles de sommets, de bords et de couleurs sont tous finis, utilisez une notation telle que «$ text {couleur} (v) = c $«Pour indiquer ce sommet $ v $ a de la couleur $ c $. Réalisez qu'une telle affirmation est encodable comme une seule variable propositionnelle $ P ^ c_v $.
2. Décrivez un ensemble de contraintes dans PL affirmant que chaque sommet a au plus une seule couleur.
3. Décrivez un ensemble de contraintes dans PL affirmant qu'aucun sommet connecté n'a la même couleur.
4. Identifiez une optimisation significative dans ce codage. Astuce: des contraintes peuvent-elles être supprimées? Pourquoi?
5. Si les contraintes ne sont pas déjà dans CNF, spécifiez-les dans CNF maintenant. Pour$ N $ sommets, $ K $ bords, et $ M $ Couleurs, combien de variables le codage optimisé nécessite-t-il? Combien de clauses?

---

Comme suggéré par @ dw ♦, je copie le problème d'origine ici (ci-dessus est la version simplifiée par moi). Cette version originale est Exercice 1.6 de:

Bradley, A. et Manna, Z. (2007). Le calcul de calcul. Dordrecht: Springer, p.34.

Mon analyse

Le CNF optimisé dans ma capacité est d'utiliser une variable propositionnelle $ P_v ^ c $ Pour indiquer que $ text {couleur} (v) = c $. Ici, nous ne pouvons utiliser qu'au plus $ | V | $ Les couleurs de toutes les couleurs, c'est-à-dire, le nombre de couleurs dans notre conception de variables propositionnelles est $ | V | min (| v |, | c |) $. Ensuite, nous pouvons construire un CNF: $$ f_0 = bigwedge_ {v in v} ( bigvee_ {c in c} p_v ^ c) wedge bigwedge_ {v in v} ( bigvee_ {c_1 not = c_2 in c} ( nég p_v ^ {c_1} vee neg p_v ^ {c_2})) land bigwedge_ {c in c langle v, w marche ^ c) $$

Dans cette variable, il y a $ | V | min (| v |, | c |) $ variables propositionnelles et 2 $ | V | + | C || e | $ clauses.

Je n'ai pas prouvé $ F_0 $ est le CNF sans les moindres variables propositionnelles ni les moindres clauses. Y a-t-il un autre CNF $ F '$ avec moins de variables propostionnelles ou moins de clauses? Comment trouver le nombre minimal de variables propositionnelles et de clauses des CNF légaux?