Buenas,
Tuvimos la siguiente idea, de la cual tuvimos muchísimas dudas porque nos parecía bastante fácil e intuitivo. Arrancamos a dudar cuando vimos una solución (imagenes), en la cual la construcción del grafo es bastante distinta a la nuestra. Nosotros planteamos lo siguiente:
Modelamos el ejercicio como un grafo G, tal que cada nodo representa a un cliente.
Creamos una arista (vi, wj) si el cliente vi compró al menos un mismo producto que otro cliente wi.
De esta forma es bastante trivial demostrar que independent set responde afirmativamente <-> existe un conjunto diverso. (Demostrar si y solo si)
Es correcto?
De la idea anterior, la principal duda que tenemos es, a la hora de la construcción del grafo de la forma en la que lo planteamos, puede tener un tiempo de ejecución bastante alto y por eso lo construyen de la siguiente forma?
