Practico 3, Ejercicio 1, Parte a

Practico 3, Ejercicio 1, Parte a

de Jose Agustin Bizio Piriz -
Número de respuestas: 6

Hola muy buenas, les dejo el algoritmo que propuse y me gustaría saber si cumple con el tipo el tipo de algoritmo que quieren en el curso (en tema de formalidad y especificidad).


void DFSArbol (G, u, T) 

      Marcar u como explorado

      Foreach arista (u,v) incidente a u

          If v no esta explorado

              Añadir a v como hijo de u en Arbol T

              invocar DFSArbol(G, v, T)


V Hay Ciclo (G)

       Sea u nodo de G cualesquiera

       Sea T árbol con solamente el nodo u

       ejecutar DFS(G,u,T)

       if T = G (tienen mismos vértices y aristas)

             retornar \emptyset  (no hay ciclos en G)

      else

           sean x e y vértices adyacentes en G pero no en T

           retornar {x}U{y}U{el conjunto de vértices que están en el camino de x a y en T}


La idea del grafo es suponer que solo hay una componente conexa (en caso que no se ejecuta por cada componente) y que si el grafo tiene mas aristas que T entonces el grafo tiene un ciclo, y ese ciclo se puede formar con esa arista que no esta en T y el camino entre los vértices de esa arista en T.

Mi duda es además, cuando digo "agregar v como hijo de u", estaría suponiendo que el árbol resultante es dirigido? como evito eso

Esta bien? algo que agregar?

Desde ya saludos.
En respuesta a Jose Agustin Bizio Piriz

Re: Practico 3, Ejercicio 1, Parte a

de Alvaro Martin -
Hola.
El nivel de formalidad para expresar el algoritmo en general está bien. Sin embargo, hay pasos que no son nada triviales y que hay que detallar rigurosamente, ya sea en la presentación del algoritmo o en su análisis de complejidad. Por ejemplo, ¿cómo se evalúa si T=G? ¿ Cómo se obtienen vértices x,y adyacentes en G pero no en T? ¿Cómo se obtiene el camino de x a y en T? ¿Cómo se recorren las componentes conexas?

A la hora de analizar la corrección también hay que tener cuidado con pasos del estilo "sea x que cumple tal condición", como por ejemplo "sean x, y vértices adyacentes en G pero no en T"; ¿por qué tienen que existir tales vértices?

Con respecto a la duda concreta del final, si uno escribe "agregar v como hijo de u", eso da a entender que es una arista dirigida. Si no es lo que se quiere, se podría decir por ejemplo "agregar la arista (u,v) a T", que con nuestra convención de denotar aristas como pares ordenados, ya sea para grafos dirigidos o no dirigidos, no indica necesariamente una dirección de la arista.

Saludos,
Álvaro
En respuesta a Alvaro Martin

Re: Practico 3, Ejercicio 1, Parte a

de Jose Agustin Bizio Piriz -
podrías explicar como responder a todas las preguntas del primer párrafo? no tengo ni idea como hacer el algoritmo y nunca tuve un curso similar ni nunca se explico como hacer esto, desde ya gracias
En respuesta a Jose Agustin Bizio Piriz

Re: Practico 3, Ejercicio 1, Parte a

de Alvaro Martin -
La respuesta a algunas de esas preguntas requiere un algoritmo en sí misma. Por ejemplo, encontrar una arista (x,y) que está en G pero no en T podría implementarse recorriendo las aristas de G y verificando, para cada una, si está en T. Poder hacer esta verificación eficientemente requiere usar alguna estructura para representar T que lo habilite. Por ejemplo, si T se representa mediante un arreglo parent[] tal que para cada nodo u (representado como un índice de 1 a n) parent[u] nos da el padre de u en T, esa verificación se puede hacer en tiempo O(1) y la búsqueda de tal arista en tiempo O(m+n).

Para este problema en particular creo que es más sencillo resolver todo durante la recorrida DFS que hacerlo a posteriori a partir del árbol.

Saludos,
Álvaro
En respuesta a Alvaro Martin

Re: Practico 3, Ejercicio 1, Parte a

de Mateo Elisee Lengronne Gilles -
Buenas,
suponiendo que se tiene un algoritmo iterativo de DFS, usando una pila, cuando se hace la búsqueda en los nodos adyacentes al actual, como me podría fijar en ese momento si llegué a un punto donde estoy en presencia de un ciclo? O sea, si llego a un nodo adyacente ya explorado, para poder resolver en ese momento si hay un ciclo, cual tendría que ser la condición?
Por la propiedad 3.7 sabemos que si x-y pertenece a G y no a T, entonces uno es ancestro del otro.

Supongamos u es el nodo del top de la pila, que se toma al principio del while, luego dentro del for de adyacentes, se toma el nodo v(tal que exista arista u-v), si v no fue explorado, entonces se pone en la pila y se pone padre[v]=u, pero si ya fue explorado? No me queda claro ese momento, ni como encontrar el ciclo que contenga la arista que cumple la prop 3.7,
No sé si me expliqué bien, desde ya muchas gracias
En respuesta a Mateo Elisee Lengronne Gilles

Re: Practico 3, Ejercicio 1, Parte a

de Mateo Elisee Lengronne Gilles -
O sea, si v ya fue explorado y no es igual a padre[u], entonces estamos en presencia de un ciclo no? con esa arista u-v siendo la que cumple la propiedad 3.7, de ahí como sería el algoritmo para encontrar el ciclo?
En respuesta a Mateo Elisee Lengronne Gilles

Re: Practico 3, Ejercicio 1, Parte a

de Fernando Fernandez -
Hola Mateo.
Hay un par de cosas que no me quedan claras.
Mencionás un algoritmo iterativo. Pero no está del todo claro cómo es, porque en principio podría haber muchos algoritmos iterativos. ¿Es similar al de la página 93 del libro, manteniendo, como se explica más abajo, el padre de cada vértice?
También hacés referencia a la propiedad 3.7, que es de un algoritmo recursivo. ¿Cómo se relaciona con el iterativo? ¿Cuáles son los x e y?

Aún con estas dudas de cómo es el algoritmo, me parece que, si solo te interesa determinar si existe un ciclo (no mostrar uno de ellos), lo podés saber si padre[v] ya está definido y, como bien decís, no es padre[u].
En cambio, si querés mostrar el ciclo, v debe ser un vértice que, además de no ser padre[u], ya está explorado. Y el ciclo sería v, u, padre[u], padre[padre[u]], ..., v.