• Author / Uploaded
• Jorge Franco Ibañez

Citation preview

EJERCICIOS PARA EL TALLER DE GRAFOS 1- Sea el grafo

G = ( ({v1 , v 2 , v3 , v 4 , v5 , v6 }, {v1 v 2 , v1 v3 , v1v 4 , v1v6 , v 2 v3 , v 2 v 4 , v 2 v 6 , v3 v 4 , v3 v6 , v 4 v5 , v5 v6 }) a) b) c) d)

Haga un esquema del mismo, Determine un camino simple v1 a v5 de longitud 5. Escriba un ciclo simple de v5 a v5, con la mayor longitud posible. Determine si es euleriano. Justifique su respuesta e) Encuentre un circuito euleriano. (Si es necesario defina un subgrafo para dicho circuito). f) Escriba una matriz de adyacencia para el grafo. 2- Dado el grafo cuya representación ofrecemos a continuación: a) ¿ Es un grafo conexo?. Justifique b) Utilice al algoritmo de Dijkstra para determinar el camino más corto entre los vértices a y e. Debe quedar escrito el desarrollo de los pasos del algoritmo para determinar dicho camino.

8

3- Dado el grafo cuya representación ofrecemos a continuación: a) ¿ Es un grafo conexo?. Justifique. b) Utilice al algoritmo de Dijkstra para determinar el camino más corto entre los vértices a y z. Debe quedar escrito el desarrollo de los pasos del algoritmo para determinar dicho camino.

5

4- Sea el grafo G = (V,A) con: V = {a, b, c, d, e, f, g, h, i, j, k } A = {ab, ai, bc, bd, bi, bj, bk, cd, de, df, ef, fg, fk, gh, gj, gk, hi, ij, jk } a) b) c) d) e) f) g)

Haga un esquema del mismo, ¿Cuál es la valencia del vértice b? Determine un camino simple a a f de longitud 7. Escriba un ciclo simple de k a k, con la mayor longitud posible. Determine si es euleriano. Justifique su respuesta Encuentre un circuito euleriano. (Si es necesario defina un subgrafo para dicho circuito). Escriba una matriz de adyacencia para el grafo.