[Noti-TC] varios

[Jorge D'elia]

[24-06-10, 09:00] Varios:
    * Listado parcial de algoritmos:
          o Todos los vistos en la teoría, en la práctica y en las Sec. del libro del temario.
          o Dijkstra.
          o Arbol de expansión: por búsqueda a lo ancho y por búsqueda en profundidad.
          o Arbol de expansión mínimo: algoritmos de Prim y de Kruskal.
          o Los tres recorridos recursivos de un árbol ordenado y orientado.
          o Los tres recorridos recursivos de un árbol binario.
          o Todo otro que resulte de aplicación inmediata de las definiciones y propiedades de los grafos y árboles, e.g. todos_par (A,n), es_grafo_completo (A,n), es_grafo_ciclo (A,n), es_grafo_estrella (A,n), es_grafo_rueda (A.n), etc.,
    * Demostracion del algoritmo de Prim (pp. 644): omitirlo.
    * Observaciones sobre la cola "Q" en el algoritmo de búsqueda a lo ancho dada en la teoría. Lo que en la teoría se le dió el nombre de "cola" Q, Rosen en su algoritmo 2 lo denomina "lista" L. No obstante la diferencia de nombres, Rosen hace trabajar la lista L como una cola, esto es, en dicho algoritmo escribe "borrar el PRIMER vértice v de la lista L", "añadir el vértice w AL FINAL de la lista L", operaciones que corresponden al funcionamiento de una cola Q.
    * Algoritmo pendiente de ayer. Enunciado: dado un grafo G = (V,E) a través de su matriz de incidencia A de tamaño n = |V|, escriba la función bool es_rueda (A,n) que devuelve True si G representa un grafo tipo "rueda" (siguiendo la definición dada en el Rosen) y False en otro caso. Solución:

bool es_grafo_rueda (A,n) { 
   if ( es_grafo_ciclo (A,n-1) and A (n,n) == 0) then 
      for i = 1, (n-1) // revisa las (n-1) primeras filas de la columna n de A 
         if (A (i,n) != 1) then 
             return False 
      return True 
   else 
      return False 
} 

Notar que la función es_grafo_ciclo (A,n-1), vista en la teoría, significa chequear sólo las primeras (n-1) filas y (n-1) columnas de la matriz de incidencia de A para decidir si corresponden (o no) a un grafo tipo ciclo (siguiendo la definición del Rosen).
--