4. La gráfica de la figura 8.2.2
5. La gráfica completa sobre cinco vértices K5
6. La gráfica completa bipartita K2,3
En los ejercicios 7 al 12, escriba la matriz de incidencia de cada gráfica.
7. La gráfica del ejercicio 1
8. La gráfica del ejercicio 2
9. La gráfica del ejercicio 3
10. La gráfica de la figura 8.2.1
Get 8.5.10 exercise solution
11. La gráfica completa sobre cinco vértices K5
En los ejercicios 13 al 17, dibuje la gráfica representada por cada matriz
de adyacencia.
17. La matriz de 7 × 7 cuyo elemento ij es 1 si i + 1 divide a j + 1 o
j + 1 divide a i + 1, i j; cuyo elemento ij es 2 si i = j, y cuyo
elemento ij es 0 en otros casos.
18. Escriba la matriz de adyacencia de las componentes de las gráficas
dadas por las matrices de adyacencia de los ejercicios 13 al 17.
19. Calcule los cuadrados de las matrices de adyacencia de K5 y las
gráficas de los ejercicios 1 y 3.
20. Sea A la matriz de adyacencia para la gráfica del ejercicio 1. ¿Cuál
es el elemento en el renglón a y la columna d de A5?
21. Suponga que una gráfica tiene una matriz de adyacencia de la forma
donde todos los elementos de las submatrices A y A” son 0. ¿Cómo
se ve la gráfica?
22. Repita el ejercicio 21 con “incidencia” en lugar de “adyacencia”.
23. Sea A una matriz de adyacencia de una gráfica. ¿Por qué An es simétrica
respecto a la diagonal principal para todo entero positivo n?
En los ejercicios 24 y 25, dibuje las gráficas representadas por las matrices
de incidencia.
26. ¿Cómo debe verse una gráfica si algún renglón de su matriz de incidencia
tiene sólo ceros?
27. Sea A la matriz de adyacencia de una gráfica G con n vértices. Sea
Si algún elemento fuera de la diagonal en la matriz Y es cero, ¿qué
se puede decir de la gráfica G?
Los ejercicios 28 al 31 se refieren a la matriz de adyacencia A de K5.
28. Sea n un entero positivo. Explique por qué todos los elementos de
la diagonal de An son iguales y todos los elementos fuera de la diagonal
de An son iguales.
Sea dn el valor común de los elementos de la diagonal de An y sea an el
valor común de los elementos fuera de la diagonal de An.
29. Demuestre que
dn+1 = 4an; an+1 = dn + 3an; an+1 = 3an + 4an−1.
30. Demuestre que
31. Demuestre que
32. Derive resultados similares a los de los ejercicios 29 al 31 para la
matriz de adyacencia A de la gráfica Km.
33. Sea A la matriz de adyacencia de la gráfica Km,n. Encuentre una
fórmula para los elementos de Aj.
