Grafos

TALLER DE GRAFOS

1-Sea el grafo G=( {V1, V2, V3, V4, V5, V6,}, { V1V2, V1V3, V1V4, V1V6, V2V3, V2V4, V2V6, V3V6, V4V5, V5V6}):

a) Haga un esquema del mismo
[pic]

b) Determine un camino simple de V1 a V5 de longitud 5.
• (V1, V6, V2, V3, V4, V5)
[pic]

c) Escriba un ciclo simple de V5 a V5, con la mayor longitud posible.
(V5, V6, V1, V2,V3 , V4, V5)). Longitud 6.
[pic]
D)Determine si es euleriano. Justifique su respuesta
Si es euleriano por que todos los vértices tienen valencia par:
[pic](V1)=4
[pic](V2) =4
[pic](V3) =4
[pic](V4)=4
[pic](V5)=2
[pic](V6)=4
[pic]
e) Encuentre un circuito euleriano. (Si es necesario defina un subgrafo para dicho circuito).
V5, V4, V3, V1, V2, V4, V1, V6, V2, V3, V6, V5

f) Escriba una matriz de adyacencia para el grafo.  |V1 |V2 |V3 |V4 |V5 |V6 |[pic]  | |V1 | |1 |1 |1 |0 |1 |4 | |V2 |1 | |1 |1 |0 |1 |4 | |V3 |1 |1 | |1 |0 |1 |4 | |V4 |1 |1 |1 | |1 |0 |4 | |V5 |0 |0 |0 |1 | |1 |2 | |V6 |1 |1 |1 |0 |1 | |4 | |

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)Haga un esquema del mismo
[pic]

b) ¿Cuál esla valencia del vértice b?
[pic](b) = 6

c) Determine un camino simple de a a f de longitud 7.
• A,J,K,H,G,I,E,F

[pic]

• A, I, J, B, C, D, E, F
[pic]
d) Escriba un ciclo simple de k a k, con la mayor longitud posible.
Longitud 11= K,B,C,D,A,I,J,H,G,E,F,K
[pic]
e) Determine si es euleriano. Justifique su respuesta
si es euleriano por que todos los vértices tienenvalencia par:
[pic](a)=2 [pic] (b) =6 [pic] (c) =2 [pic] (d)=4
[pic](e) =2 [pic] (f) =4 [pic] (g) =4 [pic] (h)=2
[pic](i) =4 [pic] (j) =4 [pic] (k)=4

f) Encuentre un circuito euleriano. (Si es necesario defina un subgrafo para dicho circuito).

F.E.D.F,K,B,C,D,B,A,I,B,J,K,G,H,I,J,G,F
[pic]

g) Escriba una matriz de adyacencia para el grafo.

  |A |B |C |D |E |F |G |H |I |J |K |[pic]  ||A |  |1 |0 |0 |0 |0 |0 |0 |1 |0 |0 |2 | |B |1 |  |1 |1 |0 |0 |0 |0 |1 |1 |1 |6 | |C |0 |1 |  |1 |0 |0 |0 |0 |0 |0 |0 |2 | |D |0 |1 |1 |  |1 |1 |0 |0 |0 |0 |0 |4 | |E |0 |0 |0 |1 |  |1 |0 |0 |0 |0 |0 |2 | |F |0 |0 |0 |1 |1 |  |1 |0 |0 |0 |1 |4 | |G |0 |0 |0 |0 |0 |1 |  |1 |0 |1 |1 |4 | |H |0 |0 |0 |0 |0 |0 |1 |  |1 |0 |0 |2 | |I |1 |1 |0 |0 |0 |0 |0 |1 |  |1 |0 |4 | |J |0 |1 |0 |0 |0 |0 |1 |0 |1 | |1 |4 | |K |0 |1 |0 |0 |0 |1 |1 |0 |0 |1 |4 |8 | |

EJERCICIOS ÁRBOLES

1. Dado el árbol binario cuya raíz es x.
[pic]
1.1
a. Escriba el conjunto de los vértices interiores.
VI= (b, c, d, g, h, y)

b. Escriba el conjunto de vértices que son hojas.
H= (a, e, f, t, z)

c. ¿Cuáles son los ancestros de z?
Los ancestros de z: (y, h, g, x)

d. ¿Cuál es la altura del árbol?altura del árbol : 5

e. Escriba el recorrido en preorden.
PREORDEN: X D B F C E A G H Y Z T

f. Señale dos vértices que sean hermanos.
VH= (d, g)
VH= (b, a)
VH= (f, c)
VH= (z, t)

g. ¿Es un árbol completo?. Justifique su respuesta.
Este no es un árbol completo porque no se cumple que para todo vértice o nodo que tenga hijos debe darse que tenga sus hijoscompletos, es decir, que si un nodo va a tener un hijo, no debe tener uno solo sino los dos, tanto el hijo izquierdo como el derecho. Y como podemos ver en nuestro árbol, g es un nodo que tiene un solo hijo, el izquierdo, por lo tanto no se cumple la norma, y como dice que la norma se debe cumplir para todos, el hecho de que uno solo no la cumpla nos permite decir que el árbol no es completo.1.2. A continuación se ofrecen los recorridos en posorden y enorden de un árbol binario. Haga una representación gráfica del árbol a partir de dichos recorridos. Exprese en su esquema la secuencia de pasos realizada.

POSORDEN : Z A Y R S C V N M P U T X
ENORDEN : Z Y A X R C S N V P M T U

[pic]

2. Dado el árbol binario cuya raíz es D.
[pic]
Responda las siguientes preguntas basándote en...