Redução da 3-coloração problema para trio de representantes

Question

Um grupo de estudantes é dividido em trios - grupos de 3 membros.Cada estudante pode ser atribuído a mais do que o trio.Queremos atribuir seus representantes, escolhendo exatamente um membro de cada trio.É que tal atribuição é possível?

Meu objetivo é usar em tempo polinomial reduções para transformar 3-coloração de um grafo para este problema.No entanto, eu estou preso na correta representação.

• Se cada vértice é uma estudante e arestas representam a estar no mesmo trio, como posso separar os trios?

• Se cada nó representa um trio, o que poderia ser uma boa significado das bordas?

Eu suspeito que, desde 4-panelinha não tem adequada 3-coloração (o que também pode significar que os 4 trios com os mesmos três membros têm nenhuma possibilidade de representante de atribuição), a última opção poderia ser mais sensato, mas eu não tenho certeza sobre como proceder com esta redução prova.

Answer 1

Deixe $G = (V,E)$ ser uma instância de $3$ colorir.Construir uma instância $\phi$ de 3-SAT como segue.

• Para cada vértice $v \V$ criar $3$ variáveis $v_a, v_b, v_c$ representando o $3$ caminhos possíveis para a cor de $v$.
• Para cada vértice $v \V$ criar as cláusulas $(v_a \vee v_b \vee v_c) \cunha (\overline{v_a} \vee \overline {v_b}) \cunha (\overline{v_b} \vee \overline {v_c}) \cunha (\overline{v_c} \vee \overline {v_a})$.Esta codifica o fato de que $v$ deve ser colorido por exatamente uma cor.
• Para cada aresta $(u,v) \in E$ criar as cláusulas $( \overline{v_a} \vee \overline{u_a} ) \cunha ( \overline{v_b} \vee \overline{u_b} ) \cunha ( \overline{v_c} \vee \overline{u_c} )$.Isso garante que u $$ e $v$ não pode ser dada a mesma cor.

Claramente acima de redução pode ser realizada em poylnomial tempo e garante que não é satisfazer a atribuição de $\phi$ iff há uma 3-Coloração para $G$.

Agora, transformar a instância $\phi$ 3-SENTOU-se em um equivalente de instância $\phi'$ de 1 para 3 SAT (ver aqui para a definição de 1 em 3 sat e a redução de 3-SAT).

Temos, portanto, demonstrado que a 3-a Coloração é em tempo polinomial redutível a 1-no-3 SAT.Acontece que 1 em 3 SAT é exatamente o seu problema:o conjunto de estudantes é o conjunto de variáveis e, para cada cláusula $\{x_i, x_j, x_k\}$ você criar um grupo com os alunos $x_i$, $x_j$, e $x_k$.A definição de uma variável para true corresponde a selecção da correspondente aluno como um líder.