A continuación se presentan un conjunto de problemas que se deberán resolver utilizando lo visto en clase.

Cada
ejercicio tiene una cantidad de puntos determinada los cuales se asignarán sólo si el ejercicio es correcto y completo.

1. (4 puntos) Para cada grafos de la Figura 1, utiliza una lista de adyacencia para la representación computacional.

(a) G1 (b) G2 (c) G3

Vértice Vértices de Vértice Vértices de Vértice Vértices de

Adyacencia Adyacencia Adyacencia
a b, c, d a b, d a a, b, c, d
b a, d b a, d, e b d
c a, d c d, e c a, b
d a, b, c d a, b, c d b, c, d
e b, c

(d) G4

Figura 1: G1 - G4
Vértice Vértices de
Adyacencia
a b, d
b a, c, d, e
c b, c
d a, e
e c, e

2. (4 puntos) Representa cada grafo de la Figura 1, mediante una matriz de adyacencia.

1.
a b c d
a 0 1 1 1
b 1 0 0 1
c 1 0 0 1
d 1 1 1 0

2.
a b c d e
a 0 1 0 1 0
b 1 0 0 1 1
c 0 0 0 1 1
d 1 1 1 0 0
e 0 1 1 0 0

3.
a b c d
a 1 1 1 1
b 0 0 0 1
c 1 1 0 0
d 0 1 1 1

4.
a b c d e
a 0 1 0 1 0
b 1 0 1 1 1
c 0 1 1 0 0
d 1 0 0 0 1
e 0 0 1 0 1

3. (4 puntos) Representa cada uno de los siguientes grafos mediante una matriz de adyacencia.
1. K4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
2. K1,4
0 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
3. K2,3
0 0 1 1 1
0 0 1 1 1
1 1 0 0 0
1 1 0 0 0
1 1 0 0 0
4. C4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
5. W4
0 1 0 1 1
1 0 1 0 1
0 1 0 1 1
1 0 1 0 1
1 1 1 1 0
6. Q3
0 1 1 0 1 0 0 0
1 0 0 1 0 1 0 0
1 0 0 1 0 0 1 0
0 1 1 0 0 0 0 1
1 0 0 0 0 1 1 0
0 1 0 0 1 0 0 1
0 0 1 0 1 0 0 1
0 0 0 1 0 1 1 0

4. (4 puntos) Dadas las matrices de adyacencia 1a, 1b y 1c, dibuje el grafo correspondiente.

0 1 0
1 0 1 (1a)
0 1 0

0 0 1 1
0 0 1 0
1 1 0 1
1 1 1 0
(1b)
 0 0 1 1
0 0 1 0 (1c)
1 1 0 1
1 1 1 0

5. (4 puntos) Por cada grafo de la Figura 2, represente cada uno de ellos utilizando una matriz de adyacencia.

(a) G5 (b) G6 (c) G7

Figura 2: G5 - G7
a b c d a b c d
a 0 0 1 0 a b c d
a 0 3 0 1
b 0 0 1 2 a 1 0 2 1
b 3 0 1 0
c 1 1 0 1 b 0 1 1 2
c 0 1 0 3
d 0 2 1 0 c 2 1 1 0
d 1 0 3 0
d 1 2 0 1

6. (4 puntos) Dadas las matrices de adyacencia 2a, 2b y 2c, dibuje el grafo no dirigido correspondiente.
1 3 3
3 0 4 (2a)
2 4 0

1 2 0 1
2 0 3 0 (2b)
0 3 1 1
1 0 1 0

0 1 3 0 4
⎡12 1 3 0⎤⎥
⎢
⎢31 1 0 1⎥(2c)
⎢03 0 0 2⎥
⎣40 1 2 3⎦
 Teoría de Grafos Actividad 3 - Page of 10 Fecha: 2 de febrero de 2022

7. (4 puntos) Para cada grafo de la Figura 3, halla la matriz de adyacencia del multigafo dirigido correspondiente.

(a) G8 (b) G9 (c) G10

a b c d
a 0 1 0 0
Figura 3: G8 - G10
b 0 1 1 0
c 0 1 1 1 a b c d
a b c d
d 1 0 0 0 a 1 1 2 1
a 1 1 1 1
b 1 0 0 2
b 0 1 0 1
c 1 0 1 1
c 1 0 1 0
d 0 2 1 0
d 1 1 1 1
8. (4 puntos) Dadas las matrices de adyacencia 3a, 3b y 3c, dibuje el grafo correspondiente.

1 0 1
0 0 1 (3a)
1 1 1

1 2 1
2 0 0 (3b)
0 2 2

0 2 3 0
1 2 2 1 (3c)
2 1 1 0
1 0 0 2

9. (4 puntos) ¿Es cualquier matriz booleana cuadrada y simétrica con ceros en la diagonal la matriz de adyacencia
de algún grafo simple?
Sí, debido a que en un grafo dirigido, el grado de salida de un vértice V es el número de aristas con V como vértice
inicial, se deduce que la suma de las entradas en la fila de la matriz de adyacencia de un grafo dirigido representa el
grado de salida del vértice V
10. (4 puntos) Utiliza una matriz de incidencia para representar los grafos G5, G6 y G7.
G5