En los ejercicios 1 al 9, diga si la trayectoria indicada en la gráfica es
a) una trayectoria simple,
b) un ciclo,
c) un ciclo simple.
1.(b, b)
2. (e, d, c, b)
3. (a, d, c, d, e)
4. (d, c, b, e, d)
5. (b, c, d, a, b, e, d, c, b)
6. (b, c, d, e, b, b)
7. (a, d, c, b, e)
8. (d)
9. (d, c, b)
En los ejercicios 10 al 18, dibuje una gráfica que tenga las propiedades
indicadas o explique por qué no existe esa gráfica.
10. Seis vértices cada uno de grado 3
11. Cinco vértices cada uno de grado 3
12. Cuatro vértices cada uno de grado 1
13. Seis vértices; cuatro aristas
14. Cuatro aristas; cuatro vértices de grados 1, 2, 3, 4
15. Cuatro vértices con grados 1, 2, 3, 4
16. Gráfica simple; seis vértices con grados 1, 2, 3, 4, 5, 5
17. Gráfica simple; cinco vértices con grados 2, 3, 3, 4, 4
18. Gráfica simple; cinco vértices con grados 2, 2, 4, 4, 4
19. Encuentre todas las trayectorias simples en la siguiente gráfica
20. Encuentre todas las trayectorias simples de a a e en la gráfica del
ejercicio 19.
21. Encuentre todas las subgráficas conexas de la siguiente gráfica,
que contengan todos los vértices de la gráfica original y tengan tan
pocas aristas como sea posible. ¿Cuáles son trayectorias simples?
¿Cuáles son ciclos? ¿Cuáles son ciclos simples?
Encuentre el grado de cada vértice para las siguientes gráficas.
En los ejercicios 24 al 27, encuentre todas las subgráficas que tienen
al menos un vértice de la gráfica dada.
Get 8.2.24 exercise solution
En los ejercicios 28 al 33, decida si las gráficas tienen un ciclo de Euler.
Si lo tienen, muestre uno.
28. Ejercicio 21
29. Ejercicio 22
30. Ejercicio 23
31. Figura 8.2.4
34. La siguiente gráfica se continúa hasta una profundidad finita, arbitraria.
¿Contiene la gráfica un ciclo de Euler? Si la respuesta es
afirmativa, describa uno.
35. Una gráfica completa Kn, ¿cuándo contiene un ciclo de Euler?
36. Una gráfica bipartita Km,n, ¿cuándo contiene un ciclo de Euler?
37. ¿Para qué valores de m y n una gráfica contiene un ciclo de Euler?
38. ¿Para qué valores de n, el cubo-n contiene un ciclo de Euler?
En los ejercicios 39 y 40, verifique que hay un número par de vértices
de grado impar en la gráfica.
41. Para la gráfica del ejercicio 39, encuentre una trayectoria sin aristas
repetidas de d a e que contenga todas las aristas.
42. Sea G una gráfica conexa con cuatro vértices v1, v2, v3 y v4 de grado
impar. Demuestre que existen trayectorias sin aristas repetidas
de v1 a v2 y de v3 a v4 tales que cada arista en G está exactamente
en una de las trayectorias.
43. Ilustre el ejercicio 42 usando la siguiente gráfica.
44. Establezca y pruebe una generalización del ejercicio 42 donde hay
un número arbitrario de vértices de grado impar.
En los ejercicios 45 y 46, diga si cada afirmación es falsa o verdadera.
Si es falsa dé un contraejemplo y si es verdadera, explique.
45. Sea G una gráfica y sean v y w vértices distintos. Si hay una trayectoria
de v a w, existe una trayectoria simple de v a w.
46. Si una gráfica contiene un ciclo que incluye todas las aristas, se
trata de un ciclo de Euler.
47. Sea G una gráfica conexa. Suponga que una arista e está en un ciclo.
Demuestre que G con e eliminada sigue siendo conexa.
48. Dé un ejemplo de una gráfica conexa tal que la eliminación de
cualquier arista produzca una gráfica no conexa. (Suponga que
eliminar una arista no implica eliminar los vértices).
49. ¿Puede un caballo moverse en un tablero de ajedrez y regresar a
su posición original haciendo cada movimiento exactamente una
vez? (Un movimiento se considera hecho cuando se mueve en
cualquiera de las dos direcciones).
50. Demuestre que si G es una subgráfica conexa de una gráfica G,
entonces G está contenida en una componente.
51. Demuestre que si se hace una partición de un gráfica G en subgráficas
conexas de manera que cada arista y cada vértice en G pertenezca
a una de las subgráficas, las subgráficas son componentes.
52. Sea G una gráfica dirigida y sea G la gráfica no dirigida que se obtiene
de G si se ignora la dirección de las aristas. Suponga que G es
conexa. Si v es un vértice en G, se dice que la paridad de v es par
si el número de aristas de la forma (v, w) es par; la paridad impar
se define de manera similar. Pruebe que si v y w son vértices en G
que tienen paridad impar, es posible cambiar la orientación de ciertas
aristas en G de manera que v y w tengan paridad par y la paridad
de todos los otros vértices en G permanezca inalterable.
53. Demuestre que el número máximo de aristas en una gráfica simple,
no conexa con n vértices es (n − 1)(n − 2)/2.
54. Demuestre que el número máximo de aristas en una gráfica bipartita
simple con n vértices es n2/4 .
Un vértice v en una gráfica conexa G es un punto de articulación si la
eliminación de v y todas las aristas incidentes en v desconecta a G.
55. Dé un ejemplo de una gráfica con seis vértices que tenga exactamente
dos puntos de articulación.
56. Dé un ejemplo de una gráfica con seis vértices que no tenga puntos
de articulación.
57. Demuestre que un vértice v en una gráfica conexa G es un punto
de articulación si y sólo si existen vértices w y x en G que tengan
la propiedad de que toda trayectoria de w a x pasa por v.
Sea G una gráfica dirigida y sea v un vértice en G. El grado de entrada
a v, in(v), es el número de aristas de la forma (w, v). El grado de salida
de v, out(v), es el número de aristas de la forma (v, w). Un ciclo
de Euler dirigido en G es una sucesión de aristas de la forma
(v0, v1), (v1, v2), . . . , (vn−1, vn),
donde v0
= vn, cada arista en G ocurre exactamente una vez, y todos
los vértices aparecen.
58. Demuestre que una gráfica dirigida G contiene un ciclo de Euler
dirigido si y sólo si la gráfica no dirigida que se obtiene al ignorar
la dirección de las aristas de G es conexa y además in(v) = out(v)
para todo vértice v en G.
Una sucesión de Bruijn para n (en ceros y unos) es una sucesión
a1, . . . , a2n
de 2n bits que tiene la propiedad de que si s es una cadena de bits de
longitud n, para alguna m,
s = amam+1 · · · am+n−1.
En (8.2.2), se define para i = 1, . . . , 2n − 1.
59. Verifique que 00011101 es una sucesión de Bruijn para n = 3.
60. Sea G una gráfica dirigida con vértices correspondientes a todas
las cadenas de bits de longitud n − 1. Existe una arista dirigida del
vértice x1
· · · xn−1 a x2
· · · xn. Demuestre que un ciclo de Euler dirigido
corresponde a la sucesión de Bruijn.
61. Demuestre que existe una sucesión de Bruijn para cada n = 1, 2, . . . .
62. Una trayectoria cerrada es una trayectoria de v a v. Demuestre
que una gráfica conexa G es bipartita si y sólo si toda trayectoria
cerrada en G tiene longitud par.
63. ¿Cuántas trayectorias de longitud k ≥ 1 hay en Kn?
64. Demuestre que hay
trayectorias cuyas longitudes están entre 1 y k, inclusive, en Kn, n > 2.
65. Sean v y w vértices distintos en Kn. Sea pm el número de trayectorias
de longitud m de v a w en Kn, 1 ≤ m ≤ n.
a) Derive una relación de recurrencia para pm.
b) Encuentre una fórmula explícita para pm.
66. Sean v y w vértices distintos en Kn, n ≥ 2. Demuestre que el número
de trayectorias simples de v a w es
67. [Requiere cálculo] Demuestre que hay trayectorias
simples en Kn. (e = 2.71828. . . es la base del logaritmo natural).
68. Sea G una gráfica. Defina una relación R en el conjunto V de vértices
de G como vRw si hay una trayectoria de v a w. Pruebe que
R es una relación de equivalencia en V.
69. Pruebe que una gráfica conexa con uno o dos vértices, cada uno
con grado par, tiene un ciclo de Euler.
Sea G una gráfica conexa. La distancia entre los vértices v y w en G,
dist(v, w), es la longitud de una ruta más corta de v a w. El diámetro
de G es
d(G) = máx{dist(v, w) | v y w son vértices en G}.
70. Encuentre el diámetro de la gráfica de la figura 8.2.10.
71. Encuentre el diámetro del cubo-n. En el contexto de computación
en paralelo, ¿qué significa este valor?
72. Encuentre el diámetro de Kn, la gráfica completa de n vértices.
73. Demuestre que el número de trayectorias en la siguiente gráfica de
v1 a v1 de longitud n es igual al (n + 1)-ésimo número de Fibonacci
fn+1.
74. Sea G una gráfica simple con n vértices cada uno con grado k y
Demuestre que G es conexa.
Un ciclo en una gráfica dirigida simple [es decir, una gráfica dirigida
que tiene cuando mucho una arista de la forma (v, w) y ninguna arista
de la forma (v, v)] es una sucesión de tres vértices o más
(v0, v1, . . . , vn)
en la que (vi−1, vi) es una arista para i = 1, . . . , n y v0
= vn. Una gráfica
acíclica dirigida (gad) es una gráfica dirigida simple sin ciclos.
75. Demuestre que una gad tiene el menos un vértice sin aristas que
salen [es decir, hay al menos un vértice v tal que no tiene aristas
de la forma (v, w)].
76. Demuestre que el número máximo de aristas en una gad de n vértices
es n(n − 1)/2.
77. Un conjunto independiente en una gráfica G es un subconjunto S
de los vértices de G que tienen la propiedad de que hay dos vértices
adyacentes en S. (Observe que ∅ es un conjunto independiente
para cualquier gráfica). Pruebe el siguiente resultado que se
debe a [Prodinger].
Sea Pn la gráfica que consiste en una trayectoria simple con n
vértices. Pruebe que el número de conjuntos independientes en Pn es
igual a fn+2, n = 1, 2, . . . , donde {fn} es la sucesión de Fibonacci.
78. Sea G una gráfica. Suponga que para cada par de vértices distintos
v1 y v2 en G, existe un vértice único w en G tal que v1 y w son
adyacentes y v2 y w son adyacentes.
a) Pruebe que si v y w son vértices no adyacentes en G, entonces
δ(v) = δ(w).
b) Pruebe que si existe un vértice con grado k > 1 y no hay vértices
adyacentes a los otros vértices, entonces el grado de cada
vértice es k.
