Grafos

Question 1

Describir alguna versión del Algoritmo BFS de recorrido de grafos dando su pseudocódigo. Dar su complejidad computacional justificando las afirmaciones realizadas.

Question 2

Definir el concepto de “grafo conexo” y explicar cómo se puede utilizar el Algoritmo BFS para determinar si un grafo es conexo.

Question 3

Explicar cómo se compara con el Algoritmo DFS en términos del problema que resuelve la solución que entrega y su complejidad computacional.

Question 4

Describir alguna versión del Algoritmo DFS de recorrido de grafos dando su pseudocódigo. Dar su complejidad computacional justificando las afirmaciones realizadas.

Question 5

Definir el concepto de “grafo conexo” y explicar cómo se puede utilizar el Algoritmo DFS para determinar si un grafo es conexo.

Question 6

Explicar cómo se compara con el Algoritmo BFS en términos del problema que resuelve la solución que entrega y su complejidad computacional.

Question 7

Explicar las representaciones de digrafos por medio de matrices y de listas de adyacencia y dar la complejidad computacional de las principales operaciones en cada representación.

Question 8

Definir el concepto de “orden topológico”. Dar un ejemplo de un digrafo con un único orden topológico y un ejemplo de un digrafo que admita más de un orden topológico.

Question 9

Dar un algoritmo para encontrar un orden topológico en un digrafo. dar su pseudocódigo. demostrar que es correcto y dar su complejidad computacional para alguna de las representaciones de digrafos mencionadas en el primer punto justificando las afirmaciones realizadas.

Question 10

Definir el problema de AGM (qué datos toma y qué resultados se esperan).

Question 11

Explicar Prim. dar su pseudocódigo y demostrar que es correcto y dar su complejidad.

Question 12

Mencionar un ejemplo práctico de un problema que se resuelva con AGM. Explicar cómo se compara con Kruskal. dar el pseudocódigo.

Question 13

Kruskal: Describir el problema que resuelve este algoritmo. Describir el algoritmo dando su pseudocódigo y explicando informalmente la idea del algoritmo. Demostrar que es correcto y dar su complejidad computacional justificando las afirmaciones realizadas.

Question 14

Dar un ejemplo de un problema que se pueda modelar con el problema que resuelve el Algoritmo de Kruskal. explicando la motivación del problema y la complejidad del procedimiento resultante.

Question 15

Explicar cómo se compara Kruskal con el Algoritmo de Prim en términos del problema que resuelve. la solución que entrega y su complejidad computacional.

Question 16

Definir los problemas de camino mínimo en grafos vistos en clase (qué datos toman y qué resultados se esperan).

Question 17

Describir el Algoritmo de Dijkstra para el problema de camino mínimo. dar su pseudocódigo. demostrar que es correcto y dar su complejidad computacional justificando las afirmaciones realizadas.

Question 18

Explicar cómo se compara con el Algoritmo de Floyd-Warshall en términos del problema que resuelve la solución que entrega y su complejidad computacional.

Question 19

Describir el Algoritmo de Bellman-Ford para el problema de camino mínimo. dar su pseudocódigo. demostrar que es correcto y dar su complejidad computacional justificando las afirmaciones realizadas.

Question 20

Explicar cómo se compara con el Algoritmo de Dijkstra en términos del problema que resuelve. la solución que entrega y su complejidad computacional. Dar una aplicación donde convenga aplicar uno sobre otro.

Question 21

Explicar cómo se puede modelar algún otro problema como un problema de camino mínimo en grafos.

Question 22

Describir el Algoritmo de Floyd-Warshall para el problema de camino mínimo. dar su pseudocódigo. demostrar que es correcto y dar su complejidad computacional justificando las afirmaciones realizadas.

Question 23

Explicar cómo se compara con el Algoritmo de Dijkstra en términos del problema que resuelve la solución que entrega y su complejidad computacional.