• Author / Uploaded
• Stefan Fayad Puche

Citation preview

TALLER 3 Temática: Grados, lista y matriz de adyacencia e incidencia.

1. Aplicar los teoremas de la suma de grados para cada uno de los grafos G1 y G2. a) Teorema de la suma de grados para el grafo G1 σ ( a )=2 σ ( b )=4 σ ( c )=4 σ ( d )=1 σ ( e )=3 σ ( f )=4 σ ( g )=0

∑ σ ( v i )=2| A| 2+4 +4 +1+3+4 +0=2|9| 18=18 b) Teorema de la suma de grados para el grafo G2 +¿=4 ¿ σ (a ) −¿=2 ¿ σ (a ) +¿=0 ¿ σ ( b) −¿=2 ¿ σ (b ) +¿=2 ¿ σ (c ) −¿=3 ¿ σ (c )

+¿=2 ¿ σ (d ) −¿=1 ¿ σ (d ) +¿=3 ¿ σ (e ) −¿=3 ¿ σ ( e) +¿=0 ¿ σ (f ) −¿=0 ¿ σ (f )

σ ( v i )−¿=|A| +¿=¿ ∑ ¿ σ ( v i )¿ ∑¿ 4 +0+2+2+3+ 0=2+2+3+1+3+ 0=11 11=11=11

2. Construir la lista de adyacencia y matriz de adyacencia para los grafos G1 y G2. a) Lista de adyacencia y Matriz de adyacencia para G1 Lista de adyacencia. a b c d e f g

(b, null) (a, null) (b, null) (c, null) (b, null) (a, null) |

(f, null) (c, null) (d, null) (c, null) (b, null)

(e, null) (e, null) (f, null) (c, null)

(f, null) (f, null) (e, null)

Matriz de adyacencia. a b c d e f g

a b c 0 1 ∞ 1 0 1 ∞ 1 0 ∞ ∞ 1 ∞ 1 1 1 1 1 ∞ ∞ ∞

d e f g ∞ ∞ 1 ∞ ∞ 1 1 ∞ 1 1 1 ∞ 0 ∞ ∞ ∞ ∞ 0 1 ∞ ∞ 1 0 ∞ ∞ ∞ ∞ 0

b) Lista de adyacencia y Matriz de adyacencia para G2 Lista de adyacencia. a b c d e f

(a, null) | (b, null) (c, null) (a, null) |

(b, null)

(c, null) (e, null) (d, null)

(c, null) (e, null)

(e, null)

Matriz de adyacencia. a b c d e f

a b c d e f 1 1 1 ∞ 1 ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ 1 1 ∞ ∞ ∞ ∞ ∞ 1 0 1 ∞ 1 ∞ ∞ 1 1 ∞ ∞ ∞ ∞ ∞ ∞ 0

3. Construir la matriz de incidencia para el grafo no dirigido G3.

Matriz de incidencia. 1 2 3 4 5 6

a 1 2 0 0 0 0

b 0 1 1 0 0 0

c 0 1 0 1 0 0

d 0 0 1 1 0 0

e 0 0 1 0 1 0

f 0 0 0 1 1 0

g 0 0 0 1 0 1

h 0 0 1 0 0 1