search

AsLogd / Problemes-Ampliaci-Algorismia

Solucions a alguns problemes de l'assignatura Ampliació a la Algorismia. FIB (UPC))
0 stars 1 forks source link

Hilo-Examen1 #1

Open klooner opened 6 years ago

klooner commented 6 years ago

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.

AsLogd commented 6 years ago

Exacto, esa es la duda exactamente que tenia. Envio un mail a la profe a ver si me dice algo? creo que esta suficientemente justificado

klooner commented 6 years ago

Sip, teniendo en cuenta que lo que pone no se cumple, a lo mejor hay algo que no estamos entiendo como se debe de la expresión, o que hay algún error.