Grafos

El grafo de la siguiente figura representa las distancias entre los distintos edificios de una universidad y los caminos entre ellos:





a. ¿Qué tipo de grafo es? Es dirigido y etiquetadob. Decidir si un vigilante puede salir de A, recorrer todos los edificios una sola vez y volver al punto de partida. ¿Y desde B? Si, desde A Y B se puede recorrer todos los edificios y volver al puntode partida.
c. Encontrar un recorrido de longitud mínima que visite todos los edificios y regrese al punto de partida. Es el de A,B,C,D,E y A
La red de transporte entre tiendas de una cadena serepresenta por el siguiente grafo, incluye el costo de cada envío entre dos tiendas (en miles de pesos)



a. ¿Qué tipo de grafo es? Es grafo dirigido y etiquetado
b. ¿Cual es la ruta de transportede costo mínimo entre A y G? Es la q va hacia A,B,D y G
c. En el caso de que las aristas no estuvieran dirigidas ¡Cual sería el camino de costo mínimo? La de A,B,F y G.

Queremos conectar 6ordenadores en red usando 9 cables, de manera que cada ordenador este conectado a otros 3. ¿Es posible? ¿Se puede hacer de varias formas? ¿Y 7 ordenadores usando 10 cables?





Ilustrar larepresentación gráfica del siguiente grafo:

G = (V,A)
V = {1,2,3,4,5,6}
A= {{1,2},{1,5},{1,6},{2,3},{2,4},{2,5},{3,4},{3,6}{4,5},{5,6}}



1. Del grafo anterior ¿Cuáles nodos son adyacentes o vecinos?Ninguno por que no hay arco que los conecte
2. ¿Cuántos caminos de longitud 3 encuentra en la estructura representada en el punto 1? (Describirlos)
3. Existe algún ciclo en el grafo del punto 1? ¿Encaso de existir cual? No







Representar el siguiente grafo. Considere que en este grafo las aristas están dirigidas

G = (V,A)
V = {1,2,3,4,5,6}
A={{1,2},{1,4},{2,3},{2,5},{3,4},{3,5},{4,6},{5,3},{6,2},{6,5}}






1. Del grafo representado en el punto 5. ¿Cuántos caminos existen entre los nodos 3 y 6 y de que longitudes? Existen 3 con longitud de 2

2. Del grafo...