Pr12 ej3

Pr12 ej3

de Valentina Chagas Bas -
Número de respuestas: 7

Buenas!! 

Estaba haciendo este ejercicio y me surgieron dudas de como hacerlo. Según entendí hasta ahora, debo resolver el problema de independent set usando el problema conjunto diverso transformando el problema original de forma polinomial. 

Entonces me dan un grafo G=(V,E) y debo encontrar un independent set usando conjunto diverso, por lo que debería hacer la tabla A que usa este problema. 

Primero pensé que a cada nodo lo considero un cliente y los uno si compraron algo en común. Pero luego al hacer la tabla llego al problema de que no sabría como "inventar" los productos ya que en el ejemplo que nos dan el grafo serían 3 nodos donde uno está conectado a los otros dos pero los otros dos entre ellos no, por lo que tendrían que haber más de un producto, y puedo hacer la tabla pero podría ser muy complicado ya que tendría que ver que coincida y no creo que sea así.

Alguna ayuda? 

Gracias!!!!

En respuesta a Valentina Chagas Bas

Re: Pr12 ej3

de Guillermo Dufort -
Buenas,

Estás en el camino correcto. Para probar que Independet Set (IS) se reduce en tiempo polinomial a Conjunto Diverso (CD), tenés que mostrar que se puede obtener la solución a una instancia de IS mediante una cantidad polinomial de pasos (usualmente usados para transformar una instancia de IS en una de CD) y una cantidad polinomial de llamadas a una caja negra que resuelve CD (usualmente es una única llamada).

Dado que una instancia de IS está definida por un grafo G={V, E} y un k, tendrías que ver cómo transformar el grafo y k en una instancia de CD definida por clientes, productos, y las cantidades compradas (es decir la tabla A).
Tu idea de crear un cliente por cada nodo es correcta. Ahora, en tu siguiente frase decís "los uno si compraron algo en común". Vos acá estás asumiendo que los nodos compraron algo y eso claramente no está definido. Tu sos quien tiene que definir los productos, y qué cliente compró qué producto. Para esto la clave está en ver cómo transformar la información de las aristas E en productos y cantidades compradas.

Si tenés alguna duda más volvé a consultar.

Saludos,
Guillermo
En respuesta a Guillermo Dufort

Re: Pr12 ej3

de Santiago Imelio Viera -
Buenas, quería saber si esta solución es correcta.

En respuesta a Santiago Imelio Viera

Re: Pr12 ej3

de Javier Baliosian -

hola Santiago:

la equivalencia que demostras es correcta, y es lo que esta en el fondo de la demostración de que IS <=p CD, pero no es exactamente lo que pide el ejercicio. Lo que hay que probar, tal mcomo comentaba Guillermo antes, es que podes transformar (reducir) una instancia de IS a una de CD "mediante una cantidad polinomial de pasos (usualmente usados para transformar una instancia de IS en una de CD) y una cantidad polinomial de llamadas a una caja negra que resuelve CD (usualmente es una única llamada)". Entonces tenes que asumir que el grafo ya existe porque es parte de la instancia de IS y, a partir de el, debes construir es una instancia de CD, es decir una de sus tablas de clientes y productos. 

saludos!

Javier



En respuesta a Javier Baliosian

Re: Pr12 ej3

de Nicolas Grosso San Roman -
Hola, estaría bien si al transformar las aristas a productos en la tabla, marco con 1 ó 0 como cantidades? Porque entiendo que no importa cuántas cantidades compró un cliente, lo que me interesa es saber si compró o no.
En respuesta a Guillermo Dufort

Re: Pr12 ej3

de Valentina Chagas Bas -
Hola!! Llegue a pensar esto. Es correcto? Y completo?
Saludos!!!

En respuesta a Valentina Chagas Bas

Re: Pr12 ej3

de Javier Baliosian -
hola Valentina:

la solución está, en lo fundamental, bien.
cosas que le mejoraría:
- más que poner en la primer fila y primer columna a los productos y los clientes (lo cual te dejaría con una matriz de n+1 por m+1), lo que haces es representar con cada columna las compras de cada cliente.
- en la prueba IS true => CD true, me parece que se te despista un poco el argumento, sobre todo revisaría la frase que empieza con "Al crear la matriz, estos k nodos no tendrán ninguna arista en común, por lo que si hay un 1 en una fila..."

saludos!
Javier