Grafos

Que representa la variable $n$

• tamaño de la entrada en bits

• tamaño de la entrada en palabras del computador

• cantidad de nodos y aristas en el grafo

• otra respuesta

• no tengo idea

Que representa la variable \(m\)

• tamaño de la entrada en bits

• tamaño de la entrada en palabras del computador

• cantidad de nodos y aristas en el grafo

• otra respuesta

• no tengo idea

Cuanto cuesta checkear si \(A\) y \(B\) estan conectados en una representación en \texttt{listas de adjacencia}?

• en \(O(n)\)

• en \(O(m)\)

• en \(O(\min(n,m))\)

• otra respuesta

• no tengo idea

Cuanto espacio (en bits) toma la representacion en \texttt{listas de adjacencia}?

• \(n+m\), por definicion

• \(2n\lg m\)

• \(2m\lg n\)

• otra respuesta

• no tengo idea

Cuanto cuesta checkear si \(A\) y \(B\) estan conectados en una representacion en una \texttt{matriz de adjacencia}?

• en \(O(n)\)

• en \(O(m)\)

• en \(O(\min(n,m))\)

• otra respuesta

• no tengo idea

Cuanto espacio (en bits) toma la representación de un grafo de \(n\) vertices y \(m\) aristas en una \texttt{matriz de adjacencia}?

• \(n+m\), por definicion

• \(n\lg m\)

• \(m\lg n\)

• otra respuesta

• no tengo idea

Que problema resuelve el algoritmo de \texttt{Prim}

• Arbol cobertor de peso minimo

• Arbol cobertor de distancias minimas de un punto a todos

• Arbol cobertor de distancias minimas de todos los puntos a todos

• Distancias minimas de todos los puntos a todos

• no tengo idea

Que problema resuelve el algoritmo de \texttt{Dijkstra}

• Arbol cobertor de peso minimo

• Arbol cobertor de distancias minimas de un punto a todos

• Arbol cobertor de distancias minimas de todos los puntos a todos

• Distancias minimas de todos los puntos a todos

• Otro problema

Que problema resuelve el algoritmo de \texttt{Kruskal}

• Arbol cobertor de peso minimo

• Arbol cobertor de distancias minimas de un punto a todos

• Arbol cobertor de distancias minimas de todos los puntos a todos

• Distancias minimas de todos los puntos a todos

• Otro problema

Que problema resuelve el algoritmo de \texttt{Floyd}

• Arbol cobertor de peso minimo

• Arbol cobertor de distancias minimas de un punto a todos

• Arbol cobertor de distancias minimas de todos los puntos a todos

• Distancias minimas de todos los puntos a todos

• Otro problema