hola ezequiel, qué tal?
comento por partes:
a) alg. no es correcto asumir que los nodos v que cuyo indeg(v)!=0 forman un ciclo. p.e. podría pasar que tengas un ciclo en el que algún nodo tiene outdeg=2 y por tanto exista un nodo que no integra el ciclo con indeg=1. todos estos nodos tendrían indeg!=0 pero no forman un ciclo y sería incorrecto devolverlos a todos como integrantes de un ciclo.
lo que sí es cierto, es que en el conjunto de nodos cuyo indeg(v)!=0 existe un ciclo, que el alg debería "descubrirlo" para retornarlo.
b) lo anterior y la prueba de correctitud no pueden ser ambas correctas así que la prueba no es correcta. lo señalo así para que veamos lo importante de realizar pruebas correctas ya que una que no lo sea pude reafirmarnos en el concepto de que nuestro alg es correcto cuando no lo es.
entonces, qué parte de la prueba está mal.
contestando a lo primero que consultás, (=>), la respuesta es que no, no es suficiente (en gral). lo que sí pueden hacer es reutilizar/repetir los mismos argumentos del libro (o los que corresponda) incluyendo propiedades, lemas, teoremas, corolarios, etc sin tener que demostrarlos.
respecto al recíproco (<=), en el primer paso asumís que si no devuelve OT entonces devuelve un ciclo. pero no probás que el conjunto devuelto es un ciclo y allí está el problema. ese enunciado es falso. lo que sigue es correcto pero no implica que el conjunto de vértices defina un ciclo sino algo menos fuerte y es la existencia de un ciclo incluido en ese conjunto.
c) ok
saludos
comento por partes:
a) alg. no es correcto asumir que los nodos v que cuyo indeg(v)!=0 forman un ciclo. p.e. podría pasar que tengas un ciclo en el que algún nodo tiene outdeg=2 y por tanto exista un nodo que no integra el ciclo con indeg=1. todos estos nodos tendrían indeg!=0 pero no forman un ciclo y sería incorrecto devolverlos a todos como integrantes de un ciclo.
lo que sí es cierto, es que en el conjunto de nodos cuyo indeg(v)!=0 existe un ciclo, que el alg debería "descubrirlo" para retornarlo.
b) lo anterior y la prueba de correctitud no pueden ser ambas correctas así que la prueba no es correcta. lo señalo así para que veamos lo importante de realizar pruebas correctas ya que una que no lo sea pude reafirmarnos en el concepto de que nuestro alg es correcto cuando no lo es.
entonces, qué parte de la prueba está mal.
contestando a lo primero que consultás, (=>), la respuesta es que no, no es suficiente (en gral). lo que sí pueden hacer es reutilizar/repetir los mismos argumentos del libro (o los que corresponda) incluyendo propiedades, lemas, teoremas, corolarios, etc sin tener que demostrarlos.
respecto al recíproco (<=), en el primer paso asumís que si no devuelve OT entonces devuelve un ciclo. pero no probás que el conjunto devuelto es un ciclo y allí está el problema. ese enunciado es falso. lo que sigue es correcto pero no implica que el conjunto de vértices defina un ciclo sino algo menos fuerte y es la existencia de un ciclo incluido en ese conjunto.
c) ok
saludos