aslogd / problemes-ampliaci-algorismia Goto Github PK

Yey! Tinc el primer problema resolt aquí. Hi ha una part que no tinc molt clara la demostració (per no dir que me la he patillat bastant), la he marcat entre ######. Si algú se li acut com demostrar-ho m'alegrarà el problema jajajajaja

En el problema 3, si lo he entendido bien, se pide resolver una especie de vertex cover, donde tenemos dos tipos de vertices:
-los vertices que representan un equipo de vigilancia (T) (con coste c, el precio de contratar al equipo)
-los vertices que representan una localizacion (L)
Para el equipo t de T con una camara en la localizacion l de L, hay una arista (t,l)
Tenemos que seleccionar un subconjunto de T minimo que cubra todo L.

En el apartado a, la expresión la entiendo como: (usando la notación del ejercicio)
Para todo subconjunto S de (V - {r}), el numero de aristas que forman el spanning tree del grafo y perteneces a delta(S) tiene que ser como mínimo 1 si S tiene algun vertice que forme parte del spanning tree (si no puede tener cualquier numero de vertices).
Por consecuente, el único caso en el que no cumpliría sería en el que algún subconjunto S tenga algún vertice y ninguna arista en delta(S).
El problema es que, por ejemplo, un 3-Clique (con un vertice r cualquiera) cumple también con esto y no es un árbol.

Mi propuesta para el apartado (a)

He començat també el problema 2. L'apartat b) està demostrat sense problemes, però tinc una idea d'algoritme per al a) sense puta idea de com trobar el ratio jajajajaja
El pdf aquí.

Para facilitar el proceso haremos un issue por cada problema y ahi colgaremos todos los pdfs (no hace falta el latex). Asi tenemos toda la info de un mismo problema junta. Y en ese mismo issue se revisa y se comentan las cosas. De esta forma tambien podemos ver que problemas se estan comentando y cuales no

test.pdf

Arnau:
Estoy haciendo la segunda parte del problema 8 y no tengo claro como define el problema. Dice que contemos los paths entre dos vértices y que en estos paths pueden haber nodos repetidos. No tengo claro si también se pueden repetir edges (ya que no lo prohibe explicitamente) y tampoco si pueden salir repetidos los nodos de inicio y destino en alguno de los nodos intermedios del path. Vosotros qué entendéis?

La idea es esta:

Por ahora de latex hay esto (pdf), Toni dice que él se encarga de redactar la demostración.

Del problema 5 com enteneu que l'amplada i l'alçada dels rectangles és en binari? No veig en que pot ajudar a part d'indicar que són de tamanys enters.