venció al Tuna una vez, el Nieve venció al Rascacielos dos veces, los
Faisanes vencieron al Tuna una vez y los Faisanes vencieron al Rascacielos
una vez. En los ejercicios 1 al 4, use una gráfica para modelar
el torneo. Los equipos son los vértices. Describa el tipo de gráfica usada
(no dirigida, dirigida, simple).
1. Hay una arista entre los equipos si los equipos jugaron.
2. Hay una arista entre los equipos para cada juego jugado.
3. Hay una arista del equipo ti al equipo tj si ti venció a tj al menos
una vez.
4. Hay una arista del equipo ti al equipo tj por cada victoria de ti sobre
tj.
Explique por qué ninguna gráfica en los ejercicios 5 al 7 tiene una trayectoria
del vértice a al vértice a que pasa por cada arista justo una
vez.
del vértice a al vértice a que pasa por cada arista justo una vez, encontrando
la trayectoria por inspección.
Para cada gráfica G = (V, E) en los ejercicios 11 al 13, encuentre V, E,
todas las aristas paralelas, lazos, vértices aislados, y diga si G es una
gráfica simple. Además, diga sobre qué vértices incide la arista e1.
de esta sección. Especifique los conjuntos ajenos de vértices.
Determine qué gráficas en los ejercicios 17 al 23 son bipartitas. Si la
gráfica es bipartita, especifique los conjuntos ajenos de vértices.
21. Ejercicio 11
22. Ejercicio 12
23. Ejercicio 13
24. Dibuje K2,3 y K3,3.
25. Encuentre una fórmula para el número de aristas en Km,n.
26. Muchos autores requieren que V1 y V2 sean no vacíos en la definición 8.1.11. Según estos autores, ¿cuáles gráficas en los ejemplos 8.1.12 a 8.1.14 son bipartitas?
En los ejercicios 27 al 29, encuentre una trayectoria de longitud mínima
de v a w en la gráfica de la figura 8.1.7 que pase por cada vértice
exactamente una vez.
27. v = b, w = e
29. v = a, w = b
30. Paul Erdo´´s (1913−1996) fue uno de los matemáticos más prolíficos
de todos los tiempos. Fue autor o coautor en cerca de 1500 artículos.
Se dice que los matemáticos que trabajaron en un artículo
con Erdo´´s tienen un número de Erd´o´s de uno. Los matemáticos que
no son coautores con Erdo´´s pero que publicaron con un matemático
que tiene número de Erdo´´s de uno, tienen un número de Erd´o´s
de dos. Los números de Erdo´´s mayores se definen de manera similar.
Por ejemplo, el autor de este libro tiene un número de Erdo´´s de
cinco. Johnsonbaugh es coautor de un artículo con Tadao Murata,
quien es coautor con A. T. Amin; Amin es coautor con Peter J. Slater;
Slater es coautor con Frank Harary; y Harary es coautor de un
artículo con Erdo´´s. Desarrolle un modelo de gráficas para los números
de Erdo´´s. En su modelo, ¿qué es un número de Erdo´´s?
31. El modelo de gráficas para los números de Bacon (vea el ejemplo
8.1.6), ¿es una gráfica simple?
32. Dibuje la gráfica de similitud que se obtiene al hacer S = 40 en el
ejemplo 8.1.7. ¿Cuántas clases hay?
33. Dibuje la gráfica de similitud que se obtiene al hacer S = 50 en el
ejemplo 8.1.7. ¿Cuántas clases hay?
34. En general, ¿“es similar a” es una relación de equivalencia?
35. Sugiera propiedades adicionales para el ejemplo 8.1.7 que resulten
útiles al comparar programas.
36. ¿Cómo se puede automatizar la selección de S para agrupar datos
en clases usando un gráfica de similitud?
construye un cubo-3 a partir de dos cubos-2.
39. Pruebe que la construcción recursiva en el ejemplo 8.1.8 de hecho
lleva a un cubo-n.
40. ¿Cuántas aristas inciden en un vértice en un cubo-n?
41. ¿Cuántas aristas hay en un cubo-n?
42. ¿De cuántas maneras pueden etiquetarse los vértices de un cubon
como 0, . . . , 2n − 1, de forma que haya una arista entre dos vértices
si y sólo si la representación binaria de sus etiquetas difiere
exactamente en un bit.
[Bain] inventó un algoritmo para dibujar el cubo-n en el plano. En el
algoritmo, todos los vértices están en el círculo de unidad en el plano
xy. El ángulo de un punto es el ángulo desde el lado positivo del eje x
en sentido contrario a las manecillas del reloj hasta el rayo que va del
origen al punto. La entrada es n.
1. Si n = 0, se coloca un vértice sin etiqueta en (−1, 0) y se detiene.
2. Se invoca recursivamente este algoritmo con entrada n − 1.
3. Se mueve cada vértice para que su nuevo ángulo sea la mitad
del actual, manteniendo las aristas conectadas.
4. Se refleja cada vértice y arista respecto al eje x.
5. Se conecta cada vértice arriba del eje x con su imagen de espejo
abajo del eje x.
6. Se antepone 0 a las etiquetas de cada vértice arriba del eje x,
y 1 a las etiquetas de los vértices abajo del eje x.
Las siguientes figuras muestran la manera en que el algoritmo dibuja
un cubo-2 y un cubo-3.
43. Muestre cómo el algoritmo construye el cubo-2 a partir del cubo-1.
44. Muestre cómo el algoritmo construye el cubo-3 a partir del cubo-2.
45. Muestre cómo el algoritmo construye el cubo-4 a partir del cubo-3.
Los ejercicios 46 al 48 se refieren a la siguiente gráfica. Los vértices
representan oficinas. Una arista conecta dos oficinas si hay un enlace
de comunicación entre las dos. Observe que cualquier oficina se puede
comunicar con cualquier otra con un enlace de comunicación directo
o haciendo que otros pasen el mensaje.
46. Muestre, dando un ejemplo, que la comunicación entre las oficinas
es posible aun cuando se rompan algunos enlaces de comunicación.
47. ¿Cuál es el número máximo de enlaces de comunicación que se pueden
romper teniendo todavía comunicación entre todas las oficinas?
48. Muestre una configuración en la que se rompió el número máximo
de enlaces de comunicación y todavía es posible la comunicación
entre todas las oficinas.
49. En la siguiente gráfica los vértices representan ciudades y los números
sobre las aristas son los costos de construir las carreteras indicadas.
Encuentre el sistema de carreteras menos costoso que
conecte todas las ciudades.
En una gráfica de precedencias, los vértices modelan ciertas acciones.
Por ejemplo, un vértice puede modelar una instrucción en un programa
de computadora. Hay una arista del vértice v al vértice w si la acción
modelada por v debe ocurrir antes que la acción modelada por w.
Dibuje una gráfica de precedencias para cada programa de computadora
en los ejercicios 50 al 52.
50.
x = 1
y = 2
z = x + y
z = z + 1
51.
x = 1
y = 2
z = y + 2
w = x + 5
x = z + w
x = 1
y = 2
z = 3
a = x + y
b = y + z
c = x + z
c = c + 1
x = a + b + c
