Redução de uma m-coloração para uma partição m

Question

Defina uma partição M como: Dado um gráfico não direcionado g= (v, e) e um inteiro j.Existe uma partição dos vértices em m partes {v1, v2, ..., vm} tal que pelo menos J das bordas tem seus pontos de extremidade em diferentes partes da partição?

Eu comecei a particionar o gráfico em K Partes: Cada partição representa 1 coloração do gráfico.De lá, pensei em reverter todas as bordas: então convertendo todas as bordas em não-bordas e vice-versa.Estou preso aqui.Estou no caminho certo?Obrigado.

Answer 1

Por definição, uma $ m $ -coloring é uma função $ F: v \ to {1, \ pontos, m \} $ tal que $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ não \ em e $ . Isso significa que pelo menos $ | e | $ bordas tem seus pontos de extremidade em diferentes conjuntos da partição $ \ {v_1, \ Pontos, v_m \} $ de $ v $ com $ v_i={v \ in v: f (v)= i \} $ .

Pelo contrário, se houver uma partição $ {v_1, \ pontos, v_m \} $ de $ V $ tal que pelo menos $ | e | $ bordas tem seus pontos de extremidade em diferentes conjuntos, depois a função $ f: v \ to \ \ \ \ {1, \ pontos, k \} $ , onde $ f (u) $ é o índice exclusivo $ i_u \ in {1, \ Dots, m \} $ tal que $ u \ in a_ {i_u} $ , satisfaz $ \ forall u, v \ in v \; f (u)= f (v) \ implica (u, v) \ não \ em e $ .

O acima mostra que a instância $ g= (v, e) $ de $ m $ -Coração pode ser reduzida (Reduções do Wrt Karp) para a instância $ \ langle g, | e | \ Rangle $ de $ m $ -partition.