Grafos

1.- SEA EL GRAFO NO DIRIGIDO G DE LA FIG.

[pic]

A) DESCRIBIR G = (V, A)

Una grafica G consta de dos conjuntos: V(G) y A(G). El primero de ellos está formado porelementos llamados nodos o vértices, mientras que el segundo conjunto está formado por arcos o aristas. Por lo tanto, podemos denotar una gráfica como: G = (V, A)
Donde: Vsimboliza el conjunto de vértices y a el conjunto de aristas. Si no se hace ninguna especificación, los conjuntos V y A son finitos.
Cada arista está especificada por un único par denodos del conjunto de vértices, el cual puede estar o no ordenado.
V = F, H, J, L,R,T)
G = ( J, H) (J, F) (H, T) (F, R) (F, L)

2.- SEA EL GRAFO DIRIGIDO

[pic]

A)DESCRIBIR EL GRAFO EN TERMINOS G = (V,A)

(D, K) , (D, L), (K, T), (K, M), (M, L), (M ,D), (L, K) (L, T)

3.- SEA EL GRAFO DE LA FIG.

[pic]

A) ENCONTRAR TODOS LOS CAMINOSSIMPLES DEL NODOS “A” AL “F”.

(A, C, P, S, D, F)
(A,C,P,S,B,S,D,F)

B) DETERMINAR EL CAMINO MAS CORTO
(A, C, P, S, D, F)

4.- DISEÑAR LOS GRAFOSPARA LAS SIGIENTES MATRICES

0 1 0 1 0 1
1 0 0 1 0 0
A = 0 1 1 1 0 0
0 0 0 0 0 1
0 1 0 0 0 0
1 0 1 0 1 0

0 1 1 0 1 0 0
1 0 1 0 1 0 0
B = 1 0 1 0 1 0 0
01 0 1 1 1 0
1 0 0 1 1 0 0

5.- ELABORAR LAS LISTAS DE ADYACENCIA PARA LOS GRAFOS PUNTO “4”

HEAD

| |
| |
| |
| |
||
| |

HEAD

| |
| |
| |
| |
| |
| |

-----------------------
[pic]

[pic]

A
BC
D
E

E

F

B

D

C

D

A

F

D

C

B

E

F

B

F

B

A
B
C
D
E

E

F

E

C

A

E

C

A

E

D

B

E

D

A