Hola.
Para esta semana tenemos planificado empezar a trabajar sobre el capítulo específico para grafos. En realidad van a ver que los grafos nos van a acompañar durante todo el curso.
Mañana martes vamos a destinarlo a consultar dudas y tengo pensado hacer algún comentario adicional sobre el ejercicio que resolvimos el jueves pasado. Les dejo a continuación algunas preguntas sobre el tema de esta semana.
La bibliografía sobre grafos no siempre es consistente en las definiciones y notaciones que se usan en diferentes libros y artículos. Por ejemplo, la definición de grafo presentada en nuestro libro de referencia excluye la posibilidad de que un vértice esté conectado a sí mismo a través de una arista, y también la posibilidad de que dos nodos estén conectados entre sí por más de una arista (orientadas en el mismo sentido, en el caso de grafos dirigidos). Otros autores siguen criterios diferentes.
Si admitiéramos este tipo de grafos más generales, ¿hay otras definiciones en el capítulo 3 del libro que debieran modificarse? ¿Qué pasa con las estructuras de datos que se proponen y discuten para la representación de grafos?
Hablando de estas estructuras..: un algoritmo que cuenta la cantidad de aristas de un grafo arbitrario ¿cuánto tiempo requiere, asintóticamente, para el caso particular de grafos sin aristas con cada una de estas representaciones?
Saludos,
Álvaro