Grafos

Taller de Grafos.

1. Represente los siguientes grafos en forma de conjuntos y en su forma matricial.



2. Construye la la matriz de adyacencia de los dos grafos siguientes.3. En cada una de las 5 torres de Wormtown está encerrada una hija del rey Marschall Desde la torre de la princesa Dignata (D) no se ve la torre de Consumata (C), aunque sí lasotras tres. Las princesas Adelhata (A), Zebedea (Z) y Omata (O) también ven solamente tres torres cada una. Consumata sólo ve dos torres. Construye la tabla de listas de adyacencia y lamatriz de adyacencia de un grafo que tenga como vértices las torres, y tal que dos vértices estén conectados por una arista cuando desde la torre correspondiente a uno de ellos se pueda verla torre correspondiente al otro. Dibuja el grafo.

4. Para el siguiente grafo hacer:

a. Hallar el grado interior y exterior.
b. La matriz de adyacencia.
c. Exprese el grafo ennotación de conjuntos.

5. 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 conjunto A de aristas.
b. Encontrar elgrado de cada nodo.
c. Encuentre el camino más corto que recorra todos los nodos. Use el algoritmo de PRIM.

6. Sea el grafo dirigido de la figura

a. Describir el grafoformalmente en términos de su conjunto V de nodos y de su conjunto A de aristas.
b. Encontrar el grado interior y exterior de cada vértice.
c. Encontrar la matriz que representa el grafo.7. Utilice el algoritmo de Prim para encontrar un camino que recorra todos los nodos una sola vez al menor costo posible.

8. Para los siguientes grafos dirigidos, hallar
a.Represente el grafo en forma matricial.
b. El camino de mínimo coste para ir desde 1 hasta 3. (Para el último grafo, el camino de 1 a 9).
c. El semigrado interior y exterior para cada vértice.