Ejercicios de grafos

EJERCICIOS GRAFOS
1. Sea el grafo no dirigido G de la figura

a) Describir G formalmente en términos de su conjunto V de nodos y de su conjuntoA de aristas. b) Encontrar el grado de cada nodo. 2. Sea el grafo dirigido de la figura

a) Describir el grafo formalmente en términos de suconjunto V de nodos y de su conjunto A de aristas. b) Encontrar el grado de entrada y el grado de salida de cada vértice. c) Encontrar los caminossimples del vértice M al vértice T. 3. Sea el grafo G de la figura.

a) Encontrar todos los caminos simples del nodo A al nodo F. b) Encontrar elcamino más corto de C a D. c) ¿Es un grafo conexo? 4. Dado el grafo valorado de la figura

a) Encontrar la matriz de pesos del grafo b)Representar el grafo mediante listas de adyacencia 5. Un grafo G consta de los siguientes nodos V={A, B, C, D, E} y la matriz de adyacencia:

a) Dibujar elgrafo correspondiente. b) Representar el grafo mediante listas de adyacencia. c) Realizar el recorrido del grafo en profundidad partiendo del nodoC. d) Realizar el recorrido del grafo en anchura partiendo del nodo C. 6. Un grafo dirigido acíclico (GDA) es un grafo dirigido sin ciclos. Dadoslos siguientes grafos:

indicar si son GDAs. En caso de no serlo, escribir los ciclos. 7. Dado el grafo de la figura:

encontrar lascomponentes fuertemente conexas. 8. Dado el grafo G de la figura:

a) Escribe la matriz de adyacencia de G. b) Escribe la matriz de caminos de G.