grafos _representacion_matricial

Vista previa del material en texto

UNSL MATEMATICA DISCRETA 2018
TRABAJO PRACTICO
Grafos
Representación Matricial
1. Calcular las matrices de adyacencia e incidencia de cada uno de los grafos de la figura 1
a
b
cd
e(b)
a b c d
e f g h
i
j
(a)
a b c
d e f g
(d)
a b
c
d
e
(c)
Figura 1
2. Calcular las matrices de adyacencia e incidencia de cada uno de los siguientes grafos
(a) C4.
(b) P4.
(c) K5.
(d) K2,4.
(e) Sea X � t1, 2, 3, 4, 5u y G � pV,Eq donde V � ttx, yu | x, y P X ^ x � yu y E �
ttta, bu, tc, duu | a, b, c, d P X ^ ta, bu X tc, du � ∅u.
3. Sea A la matriz de adyacencia para el grafo del ejercicio 1(b).
(a) ¿Cuál es entrada correspondiente a la fila a y columna d de A3? Responder sin calcular el
producto matricial,
(b) ¿Cuántas trayectorias de longitud 4 hay entre los vértices a y d? Responder prescindiendo del
dibujo.
4. Dado el grafo G � pV,Eq con V � tv1, v2, v3, v4, v5, v6u y E � ttv1, v2u, tv1, v3u, tv1, v4u, tv1, v5u,
tv2, v4u, tv5, v6u, tv2, v5u, tv3, v6u, tv4, v6u, tv3, v4uu.
(a) Representarlo.
(b) Decir cuántas caminatas de longitud 2, 3 y 4 hay del vértice v1 al v5.
(c) Decir cuántas caminatas de longitud 2, 3 y 4 tiene G.
(d) Calcular la matriz de adyacencia de G.
(e) Calcular las potencias adecuadas de la matriz de adyacencia de G para responder los items
anteriores.
5. Dibujar el grafo G representado por las siguientes matrices de adyacencia. En cada caso el conjunto
de vértices es V pGq � t1, 2, . . . , nu, donde n es el tamaño de la matriz de adyacencia.
(a) ApGq es de tamaño 7 x 7 y ApGqi,j � 1 si i�1 divide a j�1 o j�1 divide a i�1 y ApGqi,j � 0
en cualquier otro caso.
(b) ApGq es de tamaño 4 x 4 y ApGqi,j � 1 si y sólo si j � k es par.
(c) ApGq es de tamaño 5 x 5 y ApGqi,j � 1 si y sólo si j � k es impar.
(d) ApGq es de tamaño 7 x 7 y ApGqi,j � 1 si y sólo si jk es par.
(e) ApGq es de tamaño 7 x 7 y ApGqi,j � 1 si y sólo si jk es impar.
(f) ApGq es de tamaño 5 x 5 y ApGqi,j � 1 si y sólo si j � k es divisible por 3.
1
UNSL MATEMATICA DISCRETA 2018
(g)
�
�����
0 0 0 1 0
0 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 0 0
�
����� (h)
�
�����
0 1 0 0 0
1 0 0 0 0
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
�
�����
6. Dibujar el grafo G representado por las siguientes matrices de incidencia
(a)
�
�������
0 0 1 0 0 1
0 0 0 1 1 0
1 0 0 0 0 1
0 1 0 0 1 0
0 1 0 1 0 0
1 0 1 0 0 0
�
�������
(b)
�
�������
1 0 0 0 0 1
1 1 0 0 0 0
0 1 1 0 0 0
0 0 1 1 0 0
0 0 0 1 1 0
0 0 0 0 1 1
�
�������
7. Calcular el número de caminatas de longitud 4 entre cualquier par de vértices del grafo K5 usando
la matriz de adyacencia.
8. Sea n P N y sea A la matriz de adyacencia de K5. Explicar por qué todos los elementos en la
diagonal de An son iguales entre śı y, por otro lado, todos los elementos fuera de la diagonal son
iguales entre śı.
9. (a) En A � ApK5q, sean dn el valor común de los elementos de la diagonal de A
n y an el valor
común de los elementos fuera de la diagonal. Hallar una relación de recurrencia que exprese
los valores de estas entradas.
(b) Extender el resultado anterior a la matriz de adyacencia del grafo Kn.
(c) Deducir resultados similares a los del ı́tem anterior para la matriz ApKp,qq.
10. (a) ¿Qué puede decirse de un grafo simple G si algúna fila de ApGq tiene sólo ceros?
(b) ¿Qué puede decirse de un grafo simple G si algúna fila de QpGq tiene sólo ceros?
11. Sea G un grafo simple y sean A y Q sus matrices de adyacencia e incidencia, respectivamente.
(a) ¿Qué valor tiene la suma de las entradas de cualquier fila de la matriz A?
(b) ¿Qué valor tiene la suma de las entradas de cualquier columna de la matriz A?
(c) ¿Qué valor tiene la suma de las entradas de cualquier fila de la matriz Q?
(d) ¿Qué valor tiene la suma de las entradas de cualquier columna de la matriz Q?
12. Considerar una matriz M subdividida en 4 submatrices A,B,C,D:
M �
�
A B
C D
�
Denotando con O una matriz de cierto tamaño cuyas entradas son todas nulas,
(a) ¿qué se puede decir acerca de G, si en su matriz de adyacencia M , son A � O y D � O?
(b) ¿qué se puede decir acerca de G, si en su matriz de adyacencia M , son B � O y C � O?
(c) ¿qué se puede decir acerca de G, si en su matriz de incidencia M , son A � O y B � O?
(d) ¿qué se puede decir acerca de G, si en su matriz de incidencia M , son B � O y C � O?
13. Sea A la matriz de adyacencia de un grafo G de orden n y sea Y �
°n�1
k�1 A
k. Si alguna entrada de
Y , no perteneciente a la diagonal es cero, ¿qué se puede decir del grafo G?
14. (a) Sea Q la matriz de incidencia del ejercicio 6(a), sea A la matriz de adyacencia del grafo
representado por Q y sea D la matriz diagonal de grados del grafo (i.e., para cada v P V pGq :
Dv,v � degpvq). Verificar que QQ
t � D �A.
(b) Demostrar que para un grafo simple G con A � ApGq y Q � QpGq se tiene que QQt � D�A
2
UNSL MATEMATICA DISCRETA 2018
15. Dado un grafo G, sea A � ApGq y sean u, v P V pGq distintos. Se define Aru, vs �
�
Au,u Au,v
Av,u Av,v
�
.
Probar que u y v son adyacentes si y sólo si detpAru, vsq es no nulo.
16. Dado un grafo G, sea A � ApGq y sean x, y, z P V pGq distintos. Definir
Arx, y, zs �
�
Ax,x Ax,y Ax,z
Ay,x Ay,y Ay,z
Az,x Az,y Az,z
�
.
Probar que x, y, z forman un triángulo en G si y sólo si detpArx, y, zsq es no nulo.
17. Sea G un grafo de orden n y sea A � ApGq; demostrar que
¸
IPFpV pGq,3q
detpArIsq � 2 veces número de triángulos de G.
donde FpV pGq, 3q es la familia de subconjutos de V pGq de cardinalidad 3.
3