Este é um problema conhecido na teoria do gráfico?

Question

Meu problema básico inclui um gráfico onde cada nó $ i $ está associado a um peso $ c_i $ , e o problema é encontrar um conjunto independente mínimo (ou máximo) ponderado com uma cardinalidade fixa $ P $ . Isto é acredito que um problema bem conhecido na teoria do gráfico que seja bem estudado para diferentes tipos de gráficos.

Agora, suponha que estou lidando com uma forma generalizada do problema como segue. O peso de cada nó pode levar Valores diferentes de $ P $ Cada nó está associado à $ P $ Pesos diferentes. O objetivo é novamente encontrar um conjunto independente mínimo (ou máximo) ponderado com uma cardinalidade fixa $ P $ , no entanto, cada tipo de peso pode ser selecionado apenas uma vez. Precisamente, se o tipo de peso $ J $ é selecionado para o nó $ i $ , ou seja, nós selecionamos o peso $ c_ {ij} $ , então os outros nós selecionados não podem assumir um peso do tipo $ J $ .

Minha pergunta é que, isso ainda é um problema de teoria do gráfico? É uma generalização conhecida na teoria do gráfico?

Qualquer ajuda e / ou referência é apreciada.

Answer 1

Se $ g= (v, e) $ , com $ v= {v_1, v_2, .. ., v_n \} $ e pesos $ \ {c_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \} $ é o gráfico fornecido, então podemos construir o Produto forte (Eu finalmente encontrei o nome da operação) $ g \ boxtimes k_p $ de $ G $ e $ k_p $ , onde $ k_p $ é o gráfico completo com $ P $ vértices. Este é o gráfico com vértices $ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ e bordas $ {v_ {a, b}, v_ {c, d}} $ onde:

.
1. $ a= C $ ,
2. $ b= d $ ou
3. $ {v_a, v_c \} \ em e $ . (A condição real do forte produto reduz para isso, já que na $ k_p $ todos os vértices são adjacentes).

Nós damos a vértice $ v_ {i, j} $ o peso $ c_ {i, j} $ < / span>, para $ i= 1,2, ..., n $ e $ J= 1,2, ..., P $ .

o problema na $ g $ é equivalente ao problema Set independente mínimo (máximo), na $ g \ boxtimes k_p $ . Se um vértice $ v_ {i, j} $ do novo gráfico é escolhido isso corresponde à escolha do vértice $ v_i $ < / span> do gráfico original e usando a $ j $ - peso $ c_ {i, j} $ correspondente a ele.

o conjunto de bordas de $ g \ boxtimes k_p $ são exatamente aqueles que impedem as opções correspondentes na $ g $ para usar vértices adjacentes ou reutilizar pesos com o mesmo índice:

• condição $ 1 $ define bordas no produto forte que impedem o equivalente de usar dois pesos do mesmo vértice original.
• condição $ 2 $ evita usar os pesos com o mesmo índice de diferentes vértices do gráfico original.
• condição $ 3 $ impede que dois vértices que fossem vizinhos no gráfico original são selecionados.

exemplo:

Se $ g $ é o gráfico



e $ p= 2 $ , então $ g \ boxtimes k_2 $ seria o gráfico < / p >.



Imagens criadas com Esta ferramenta .