¿Es este un problema conocido en la teoría del gráfico?

Question

Mi problema básico incluye un gráfico donde cada nodo $ i $ está asociado con un peso $ c_i $ , y el problema es encontrar un conjunto independiente ponderado mínimo (o máximo) con una cardinalidad fija $ P $ . Esto es, creo que un problema bien conocido en la teoría del gráfico que está bien estudiada para diferentes tipos de gráficos.

Ahora, supongamos que estoy tratando con una forma generalizada del problema de seguida. El peso de cada nodo puede tomar $ p $ diferentes valores, es decir, cada nodo está asociado con $ P $ Pesos diferentes. El objetivo es nuevamente para encontrar un conjunto independiente ponderado mínimo (o máximo) con una cardinalidad fija $ P $ , sin embargo, cada tipo de peso se puede seleccionar solo una vez. Precisamente, si el tipo de peso $ j $ se selecciona para el nodo $ i $ , es decir, seleccionamos el peso $ c_ {ij} $ , entonces los otros nodos seleccionados no pueden tomar un peso del tipo $ j $ .

Mi pregunta es que, ¿esto sigue siendo un problema de teoría del gráfico? ¿Es una generalización conocida en los problemas de la teoría del gráfico?

Se aprecia cualquier ayuda y / o referencia.

Answer 1

Si $ g= (v, e) $ , con $ v={v_1, v_2, .. ., v_n \} $ y pesas $ \ {C_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., P \} $ es el gráfico dado, entonces podemos construir el Producto fuerte (finalmente encontré el nombre de la operación) $ g \ boxtimes k_p $ de $ G $ y $ k_p $ , donde $ k_p $ es el completa gráfico con $ P $ vértices. Esta es la gráfica con vértices $ \ {v_ {i, j}, i= 1,2, ..., n, j= 1,2, ..., p \ } $ y bordes $ \ {v_ {a, b}, v_ {c, d} \} $ cualquiera:

1. $ a= C $ ,
2. $ b= d $ o
3. $ \ {v_a, v_c \} \ in e $ . (La condición real del producto fuerte se reduce a esto, ya que en $ k_p $ todos los vértices son adyacentes).

Damos el vértice $ v_ {i, j} $ el peso $ C_ {I, J} $ < / span>, para $ i= 1,2, ..., n $ y $ j= 1,2, ..., p $ .

El problema en $ g $ es equivalente al problema conjunto independiente ponderado (máximo) en la $ g \ boxtimes k_p $ . Si un vértice $ v_ {i, j} $ de la nueva gráfica se elige esto corresponde a la elección de vértice $ V_I $ < / SPAN> del gráfico original y usando el $ j $ -th ithight $ C_ {i, J} $ correspondiente a ello.

El conjunto de bordes de $ g \ boxtimes k_p $ son exactamente aquellos que evitan las opciones correspondientes en $ G $ para usar vértices adyacentes o reutilizar pesos con el mismo índice:

• condición $ 1 $ define los bordes en el producto sólido que evita el equivalente al uso de dos pesos del mismo vértice original.
• condición $ 2 $ evita el uso de los pesos con el mismo índice de diferentes vértices del gráfico original.
• condición $ 3 $ evita que se seleccionen dos vínculos en el gráfico original.

Ejemplo:

Si $ g $ es el gráfico



y $ p= 2 $ , luego $ g \ boxtimes k_2 $ sería el gráfico < / p>



Imágenes creadas con esta herramienta .