Soluciones Ejercicios Capítulo 9.4 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 5, encuentre el árbol de expansión mínima dado por el algoritmo 9.4.3 para cada gráfica.


 
 



 
 

 
 

 
 


6. Demuestre que el algoritmo 9.4.3 examina (n3) aristas en el peor caso.
 
 
Los ejercicios 7 al 9 se refieren a la versión alternativa del algoritmo de Prim (algoritmo 9.4.6).
Algoritmo 9.4.6
Versión alternativa del algoritmo de Prim
Este algoritmo encuentra un árbol de expansión mínima en un gráfica G conexa ponderada. En cada paso, algunos vértices tienen etiquetas temporales y otros tienen etiquetas permanentes. La etiqueta de un vértice i se denota por Li. Entrada: Gráfica conexa ponderada con vértices 1, . . . , n y vértice inicial s. Si (i, j) es una arista, w(i, j) es igual al peso de (i, j); si (i, j) no es una arista, w(i, j) es igual a ∞ (un valor mayor que cualquier peso real) Salida: Árbol de expansión mínima T


7. Muestre la manera en que el algoritmo 9.4.6 encuentra un árbol de expansión mínima para las gráficas de los ejercicios 1 al 5.


8. Demuestre que el algoritmo 9.4.6 examina (n2) aristas en el peor caso.


9. Pruebe que el algoritmo 9.4.6 es correcto; es decir, al terminar el algoritmo, T es un árbol de expansión mínima.


10. Sea G una gráfica conexa ponderada, sea v un vértice en G y sea e la arista con peso mínimo incidente en v. Demuestre que e está contenida en algún árbol de expansión mínima.


11. Sea G una gráfica conexa ponderada y sea v un vértice en G. Suponga que los pesos de las aristas incidentes en v son distintos. Sea e la arista con peso mínimo incidente en v. ¿Debe e estar contenida en todo árbol de expansión mínima?


12. Demuestre que cualquier algoritmo que encuentra un árbol de expansión mínima en Kn, cuando todos los pesos son iguales, debe examinar toda arista en Kn.


13. Demuestre que si todos los pesos en una gráfica conexa G son diferentes, G tiene un árbol de expansión mínima.


En los ejercicios 14 al 16, decida si la afirmación es falsa o verdadera. Si es verdadera, pruébela; de otra manera, dé un contraejemplo. En cada ejercicio, G es una gráfica conexa y ponderada.

14. Si todos los pesos en G son distintos, los árboles de expansión de G diferentes tienen pesos diferentes.


15. Si e es una arista en G cuyo peso es menor que el peso de cada tercera arista, e está en todo árbol de mínima expansión de G.


16. Si T es un árbol de expansión mínima de G, existe un etiquetado de los vértices de G de manera que el algoritmo 9.4.3 produce T.

 17. Sea G una gráfica conexa ponderada. Demuestre que si, mientras sea posible, se elimina una arista de G con peso máximo y cuya eliminación no desconecta a G, el resultado es un árbol de expansión mínima para G.

18. Escriba un algoritmo que encuentre un árbol de expansión mínima en una gráfica conexa ponderada.


19. Pruebe que su algoritmo del ejercicio 18 es correcto. El algoritmo de Kruskal encuentra un árbol de expansión mínimo en una gráfica G conexa ponderada que tiene n vértices como sigue. La gráfica Tinicialmente consiste en los vértices de G y ninguna arista. En cada iteración, se agrega una arista e a Tcon peso mínimo que no completa un ciclo en T. Cuando T tiene n −1 aristas, se detiene.
 

20. Establezca formalmente el algoritmo de Kruskal.
 

21. Muestre cómo el algoritmo de Kruskal encuentra árboles de expansión mínima para las gráficas de los ejercicios 1 al 5.


22. Demuestre que el algoritmo de Kruskal es correcto; es decir, al terminar el algoritmo de Kruskal, T es un árbol de expansión mínima.


23. Sea V un conjunto de n vértices y sea s una “función de disimilitud” en V×V (vea el ejemplo 8.1.7). Sea G la gráfica ponderada completa que tiene vértices V y pesos w(vi, vj) =s(vi, vj). Modifique el algoritmo de Kruskal de manera que agrupe datos en clases. Esta modificación se conoce como método del vecino más cercano (vea [Gosel]).
 

Los ejercicios 24 al 30 se refieren a la siguiente situación. Suponga que tenemos timbres de varias denominaciones y queremos elegir el mínimo número de timbres para completar una cantidad dada de importe postal. Considere un algoritmo ambicioso que selecciona timbres escogiendo todos los que puede de la denominación más grande, después todos los que puede de la denominación siguiente más grande, y así sucesivamente.


24. Demuestre que si las denominaciones disponibles son 1, 8 y 10 centavos, el algoritmo no siempre produce el menor número de timbres para completar un importe postal dado.


25. Demuestre que si las denominaciones disponibles son 1, 5 y 25 centavos, el algoritmo produce el menor número de timbres para completar un importe dado.


26. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, no siempre produce el menor número de timbres para completar el importe postal.


27. Encuentre enteros positivos a1 y a2 tales que a1 > 2a2 > 1, a2 no divide a a1 y el algoritmo, con denominaciones disponibles 1, a1, a2, produce el menor número de timbres para completar cualquier importe postal dado. Pruebe que sus valores en realidad dan una solución óptima.


28. Suponga que las denominaciones disponibles son
1=a1 < a2 < ···< an.
Demuestre, dando un contraejemplo, que la condición
ai ≥2ai−1 −ai−2,3 ≤i ≤n,

no es necesaria ni suficiente para que el algoritmo ambicioso sea óptimo.


29. Demuestre que el algoritmo ambicioso es óptimo para las denominaciones
1=a1 < a2 < ···< am

si y sólo si ese algoritmo es óptimo para todas las denominaciones menores que am−1+am. (Este resultado se debe a William Seaman).


30. Demuestre que la cota am−1 + am en el ejercicio 29 no puede ser menor.
 
 

Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.3 Matemáticas Discretas Johnsonbaugh 6 ed

1. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices hgfedcba para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.

2. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices hfdbgeca para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


3. Use la búsqueda a lo ancho (algoritmo 9.3.6) con el orden de vértices chbgadfe para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


4. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices hgfedcba para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


5. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices hfdbgeca para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.


6. Use la búsqueda a profundidad (algoritmo 9.3.7) con el orden de vértices dhcbefag para encontrar un árbol de expansión para la gráfica G de la figura 9.3.1.

En los ejercicios 7 al 9, encuentre un árbol de expansión para cada gráfica.












 
 
10. Demuestre que no hay solución a los problemas de dos y tres reinas.


11. Encuentre una solución a los problemas de cinco y seis reinas.


12. ¿Falso o verdadero? Si G es una gráfica conexa y T es un árbol de expansión para G, existe un orden de los vértices de G tal que el algoritmo 9.3.6 produce T como una árbol de expansión. Si es verdadero, pruébelo; de otra manera, proporcione un contraejemplo.


13. ¿Falso o verdadero? Si G es una gráfica conexa y T es un árbol de expansión para G, existe un orden de los vértices de G tal que el algoritmo 9.3.7 produce T como un árbol de expansión. Si es verdadero, pruébelo; de otra manera, proporcione un contraejemplo.


14. Muestre, mediante un ejemplo, que el algoritmo 9.3.6 puede producir árboles de expansión idénticos para una gráfica conexa G a partir de dos ordenamientos de los vértices de G.
 

 15. Muestre, mediante un ejemplo, que el algoritmo 9.3.7 puede producir árboles de expansión idénticos para una gráfica conexa G a partir de dos ordenamientos de los vértices de G.


16. Pruebe que el algoritmo 9.3.6 es correcto.


17. Pruebe que el algoritmo 9.3.7 es correcto.


18. ¿En qué condiciones una arista en una gráfica conexa G está contenida en todos los árboles de expansión de G?


19. Sean T y T dos árboles de expansión de una gráfica conexa G. Suponga que una arista x está en T pero no en T . Demuestre que existe una arista y en T pero no en T tal que (T − {x})∪{y} y (T −{y}) ∪ {x}) son árboles de expansión de G.


20. Escriba un algoritmo basado en la búsqueda a lo ancho que encuentre la longitud mínima de cada trayectoria en una gráfica no ponderada de un vértice fijo v a todos los demás.


21. Sea Guna gráfica ponderada en la que el peso de cada arista es un entero positivo. Sea G la gráfica obtenida de G al sustituir cada arista




en G con peso k por k aristas no ponderadas en serie:




 Demuestre que el algoritmo de Dijkstra para encontrar la longitud mínima de cada trayectoria en la gráfica ponderada G desde un vértice fijo v a todos lo demás (algoritmo 8.4.1) y realizar la búsqueda a lo ancho en una gráfica no ponderada G comenzando en el vértice v son, de hecho, el mismo proceso.
 

22. Sea Tun árbol de expansión para una gráfica G. Demuestre que si una arista en G, pero no en T, se agrega a T, se produce un ciclo único. Un ciclo como el descrito en el ejercicio 22 se llama ciclo fundamental. La matriz del ciclo fundamental de una gráfica G tiene renglones indexados según los ciclos fundamentales de G respecto a un árbol de expansión Tpara G y sus columnas indexadas según las aristas de G. El elemento ij es 1 si la arista j está en el i-ésimo ciclo fundamental y 0 de otra manera. Por ejemplo, la matriz del ciclo fundamental de la gráfica G de la figura 9.3.1 relativa al árbol de expansión mostrado en la figura 9.3.1 es









Encuentre la matriz del ciclo fundamental de cada gráfica. El árbol de expansión que se usará está dibujado con línea continua.







 



 


26. Escriba un algoritmo de búsqueda a profundidad para probar si una gráfica es conexa.


27. Escriba un algoritmo de búsqueda a profundidad para probar si una gráfica es conexa.
 

28. Escriba un algoritmo de búsqueda a lo largo para encontrar todas las soluciones al problema de las cuatro reinas.
 
 
Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.2 Matemáticas Discretas Johnsonbaugh 6 ed

Responda las preguntas en los ejercicios 1 al 6 para el árbol en la figura 9.2.1.

1. Encuentre el padre de Poseidón.

2. Encuentre los ancestros de Eros.

3. Encuentre los hijos de Urano.

4. Encuentre los descendientes de Zeus.

5. Encuentre los hermanos de Ares.

6. Dibuje el subárbol con raíz en Afrodita.
 
Responda las preguntas en los ejercicios 7 al 15 para el siguiente árbol.


 


7. Encuentre los padres de c y h.
 

8. Encuentre los ancestros de c y j.
 

9. Encuentre los hijos de d y e.

10. Encuentre los descendientes de c y e.

11. Encuentre los hermanos de f y h.


12. Encuentre los vértices terminales.


13. Encuentre los vértices internos.
 

14. Dibuje el subárbol con raíz en j.
 

15. Dibuje el subárbol con raíz en e.
 

16. Responda a las preguntas en los ejercicios 7 al 15 para el siguiente árbol.












17. ¿Qué puede decir de dos vértices en un árbol con raíz que tienen el mismo padre?
 

18. ¿Qué puede decir de dos vértices en un árbol con raíz que tienen los mismos ancestros?


19. ¿Qué puede decir de un vértice en un árbol que no tiene ancestros?


20. ¿Qué pude decir de dos vértices en un árbol con raíz que tienen un descendiente en común?

21. ¿Qué puede decir de un vértice en un árbol con raíz que no tiene descendientes?



En los ejercicios 22 al 26, dibuje una gráfica que tenga las propiedades indicadas o explique por qué no existe tal gráfica.

22. Seis aristas; ocho vértices
 

23. Acíclica; cuatro aristas, seis vértices
 

24. Árbol; todos los vértices de grado 2

25. Árbol; seis vértices que tienen 1, 1, 1, 1, 3, 3 grados


26. Árbol; cuatro vértices internos, seis vértices terminales


27. Explique por qué, si se permiten ciclos de longitud 0, una gráfica que consiste en un solo vértice y ninguna arista no es acíclica.


28. Explique por qué, si se permite que los ciclos repitan aristas, una gráfica que consiste en una sola arista y dos vértices no es acíclica.

29. La gráfica conexa mostrada tiene una trayectoria simple única de cualquier vértice a cualquier otro, pero no es un árbol. Explique por qué.



Un bosque es una gráfica simple sin ciclos.


30. Explique por qué un bosque es una unión de árboles.


31. Si un bosque F  consiste en m árboles y tiene n vértices, ¿cuántas aristas tiene F?
 

32. Si P1=(v0, . . . , vn) y P2=(w0, . . . , wm) son dos trayectorias simples de a a b diferentes, en una gráfica simple G, ¿es

(v0, ..., vn =wm, wm−1, ..., w1, w0)

necesariamente un ciclo? Explique su respuesta. (Este ejercicio es relevante para el último párrafo de la demostración del Teorema 9.2.3).


33. Demuestre que una gráfica Gcon nvértices y menos de n−1 aristas no es conexa.


34. Pruebe que T es un árbol si y sólo si T es conexa y cuando se agrega una arista entre cualesquiera dos vértices, se crea exactamente un ciclo.


35. Demuestre que si G es un árbol, todo vértice de grado 2 o más es un punto de articulación. (“Punto de articulación” se definió en el ejercicio 55, de la sección 8.2).


36. Dé un ejemplo para demostrar que el inverso del ejercicio 35 es falso, incluso si se supone que G es conexa.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 9.1 Matemáticas Discretas Johnsonbaugh 6 ed

¿Cuáles gráficas en los ejercicios 1 al 4 son árboles? Explique.



 






 
 



5. ¿Para qué valores de m y n la gráfica bipartita completa sobre m y n vértices es un árbol?


6. ¿Para qué valores de n la gráfica completa sobre n vértices es un árbol?


7. ¿Para qué valores de n es el cubo-n un árbol?
 

8. Encuentre el nivel de cada vértice en el árbol que sigue.

 
 

9. Encuentre la altura del árbol del ejercicio 8.


10. Dibuje el árbol T de la figura 9.1.5 como un árbol con raíz en a. ¿Cuál es la altura del árbol obtenido?
 

11. Dibuje el árbol T de la figura 9.1.15 como un árbol con raíz en b. ¿Cuál es la altura del árbol obtenido?


12. Dé un ejemplo similar al ejemplo 9.1.5 de un árbol que se usa para especificar relaciones de jerarquía.


13. Dé un ejemplo diferente al ejemplo 9.1.5 de un árbol de definición jerárquica. Decodifique cada cadena de bits que usa el código Huffman dado.



 

14. 011000010


15. 01110100110
 

16. 01111001001110
 

17. 1110011101001111

Codifique cada palabra usando el código Huffman anterior.
18. DEN

19. NEED

20. LEADEN

21. PENNED
 
 
22. ¿Qué factores además de la cantidad de memoria usada deben considerarse cuando se elige un código, como ASCII o Huffman, para representar caracteres en una computadora?

23. ¿Qué técnicas además del uso de códigos Huffman se puede usar para ahorrar memoria cuando se almacena texto?



24. Construya un código Huffman óptimo para el conjunto de letras en la tabla.







 



25. Construya un código de Huffman óptimo para el conjunto de letras en la tabla


 

26. Use el código desarrollado en el ejercicio 25 para codificar las siguientes palabras (que tienen frecuencias consistentes con la tabla del ejercicio 25):
BUS,   CUPS,   MUSH,   PUSS,   SIP,   PUSH, CUSS,   HIP,   PUP,   PUPS,   HIPS.

27. Construya dos árboles de codificación de Huffman óptimos para la tabla del ejercicio 24, de diferentes alturas.


28. Construya un código Huffman óptimo para el conjunto de letras en la tabla.







 
Get 9.1.28 exercise solution
 

29. El profesor Gig A. Byte necesita almacenar texto formado con los caracteres A, B, C, D, E, que ocurren con las siguientes frecuencias:


El profesor Byte sugiere usar los códigos de longitud variable


los cuales, asegura, almacenan texto en menos espacio que el usado por un código Huffman óptimo. ¿Está en lo correcto el profesor? Explique su respuesta.


30. Demuestre que cualquier árbol con dos vértices o más tiene un vértice de grado 1.
 

31. Demuestre que un árbol es una gráfica plana.


32. Demuestre que un árbol es una gráfica bipartita.


33. Demuestre que los vértices de un árbol se pueden colorear con dos colores de manera que cada arista incida en vértices de diferentes colores. La excentricidad de un vértice v en un árbol T es la longitud máxima de una trayectoria simple que comienza en v.


34. Encuentre la excentricidad de cada vértice en el árbol de la figura 9.1.5. Un vértice v en un árbol T es un centro para T si la excentricidad de v es mínima.


35. Encuentre el centro o centros del árbol de la figura 9.1.5.


36. Demuestre que un árbol tiene uno o dos centros.
 

37. Demuestre que si un árbol tiene dos centros, éstos son adyacentes.


38. Defina el radio r de un árbol usando los conceptos de excentricidad y centro. El diámetro d de una gráfica se definió en el ejercicio 70, sección 8.2. ¿Es cierto siempre, de acuerdo con su definición de radio, que 2r=d? Explique su respuesta.


39. Dé un ejemplo de un árbol T que no satisface la siguiente propiedad: Si v y w son vértices en T, existe una trayectoria única de v a w.


Etiquetas: , , ,

Soluciones Ejercicios Capítulo 8.8 Matemáticas Discretas Johnsonbaugh 6 ed

Encuentre soluciones a los siguientes juegos de Locura instantánea.

 
 

 









 





7. a) Encuentre todas las subgráficas de la figura 8.8.5 que satisfacen las propiedades (8.8.1) y (8.8.2).
b) Encuentre todas las soluciones del juego de Locura instantánea de la figura 8.8.5.
 

8. a) Represente el juego de Locura instantánea mediante una gráfica



b) Encuentre una solución al juego. c) Encuentre todas las subgráficas de la gráfica en el inciso a) que satisfacen las propiedades (8.8.1) y (8.8.2). d) Use c) para demostrar que el juego tiene una solución única.
 

9. Demuestre que el siguiente juego de Locura instantánea no tiene solución, mediante un argumento para probar que ninguna subgráfica satisface las propiedades (8.8.1) y (8.8.2). Observe que no hay solución aun cuando cada cubo contiene los cuatro colores.



 

10. Dé un ejemplo de un juego de Locura instantánea que satisfaga: a) No tiene solución. b) Cada cubo contiene los cuatro colores. c) Hay una subgráfica que satisface las propiedades (8.8.1) y (8.8.2).


11. Demuestre que hay 24 orientaciones de un cubo.


12. Numere los cubos de un juego de Locura instantánea 1, 2, 3 y 4. Demuestre que el número de maneras en que se apilan los cubos 1, 2, 3 y 4, leyendo de abajo arriba, es 331,776.


13. ¿Cuántas gráficas de Locura instantánea hay; es decir, cuántas gráficas hay con cuatro vértices y 12 aristas, tres de cada uno de los cuatro tipos?


Los ejercicios 14 al 21 se refieren a una versión modificada de Locura instantánea donde una solución se define como un apilado que, al verse desde enfrente, atrás, izquierda o derecha muestra un solo color. (El frente, atrás, izquierda y derecha son de colores diferentes).


14. Dé un argumento que muestre que si se grafica el juego como la Locura instantánea normal, una solución para el juego modificado consiste en dos subgráficas de la forma mostrada en la figura, sin aristas o vértices en común.



 
 
Encuentre soluciones a Locura instantánea modificado para los siguientes juegos.

 
 
 
 












18. Gráfica del ejercicio 6


19. Demuestre que para la figura 8.8.5, Locura instantánea, como se presenta en el texto, tiene una solución, pero la versión modificada no tiene solución.


20. Demuestre que si Locura instantánea modificada tiene una solución, la versión presentada en el texto también debe tener una solución.


21. ¿Es posible que ninguna versión de Locura instantánea tenga una solución aun cuando cada cubo contenga los cuatro colores? Si la respuesta es sí, pruébelo; de otra manera, dé un contraejemplo.



Etiquetas: , ,

Soluciones Ejercicios Capítulo 8.7 Matemáticas Discretas Johnsonbaugh 6 ed

En los ejercicios 1 al 3, demuestre que la gráfica es plana dibujándola de nuevo sin que se crucen las aristas














 
 


 
 


 
En los ejercicios 4 y 5, demuestre que la gráfica no es plana encontrando una subgráfica homomorfa a K5 o K3,3.
 





En los ejercicios 6 al 8, determine si la gráfica es plana. Si lo es, dibújela de nuevo sin que se crucen las aristas; de otra manera, encuentre una subgráfica homomorfa a K5 o bien K3,3.










 
 
 

 
 
9. Una gráfica plana conexa tiene 9 vértices que tienen grados 2, 2, 2, 3, 3, 3, 4, 4 y 5. ¿Cuántas aristas hay? ¿Cuántas caras tiene?
 
10. Demuestre que agregar o eliminar ciclos, aristas paralelas o aristas en serie no afecta el hecho de que una gráfica sea plana.

11. Demuestre que cualquier gráfica que tiene 4 vértices o menos es plana.

12. Demuestre que cualquier gráfica que tiene 5 vértices o menos y un vértice de grado 2 es plana.

13. Demuestre que en cualquier gráfica simple, conexa, plana, e ≤ 3v −6.

14. Dé un ejemplo de una gráfica simple, conexa y no plana para la que e ≥ 3v −6.

15. Use el ejercicio 13 para demostrar que K5 no es plana.

16. Demuestre que si una gráfica simple G tiene 11 vértices o más, entonces una de las dos, G o su complemento G , no es plana.

17. Demuestre que si una gráfica plana tiene un ciclo de Euler, tiene un ciclo de Euler sin cruces. Una trayectoria P en una gráfica plana tiene un cruce si un vértice v aparece al menos dos veces en P y P se cruza a sí misma en v; es decir,

P =(..., w1, v, w2, ..., w3, v, w4, ...),

donde los vértices se arreglan de manera que w1, v, w2 cruza a w3, v, w4 en v como en la figura siguiente.


Un coloreado de una gráfica G con los colores C1, C2, . . . , Cn asigna a cada vértice un color Ci de manera que cada vértice tiene un color diferente del de los vértices adyacentes. Por ejemplo, la siguiente gráfica tiene tres colores. El resto de los ejercicios tienen que ver con colorear gráficas.




Un mapa plano es una gráfica plana donde las caras se interpretan como los países, las aristas son las fronteras entre esos países y los vértices representan las intersecciones de las fronteras. El problema de colorear un mapa plano G, de manera que los países con fronteras comunes no tengan el mismo color, se puede reducir al problema de colorear una gráfica construyendo primero la gráfica dual G de G de la siguiente manera. Los vértices de la gráfica dual G consisten en un punto en cada cara de G, incluso en la cara no acotada. Una arista en G conecta dos vértices si las caras correspondientes en G están separadas por una frontera. Colorear el mapa G es equivalente a colorear los vértices de la gráfica dual G .
 
 
18. Encuentre el dual del siguiente mapa.

 
19. Demuestre que el dual de un mapa plano es una gráfica plana.

20. Demuestre que cualquier coloreado del mapa del ejercicio 18, excepto la región no acotada, requiere al menos 3 colores.

21. Coloree el mapa del ejercicio 18, excepto la región no acotada, usando tres colores.

22. Encuentre el dual del siguiente mapa.


 

23. Demuestre que cualquier coloreado del mapa del ejercicio 22, excepto la región no acotada, requiere al menos 4 colores.
 

24. Coloree el mapa del ejercicio 22, excepto la región no acotada, usando 4 colores. Una triangulación de una gráfica G plana simple se obtiene de G conectando el mayor número de vértices posible al tiempo que se mantiene la naturaleza plana al no introducir lazos o aristas paralelas.
 

25. Encuentre una triangulación de la siguiente gráfica.


 
 
26. Demuestre que si una triangulación G de una gráfica G plana simple se puede colorear con n colores, y también G.

27. Demuestre que en una triangulación de una gráfica G plana simple, 3f=2e. Appel y Haken probaron (vea [Appel]) que toda gráfica plana simple se puede colorear con cuatro colores. El problema se planteó a mediados del siglo XIX y durante años nadie tuvo éxito en dar una prueba. Quienes trabajan en el problema de cuatro colores en años recientes han tenido una ventaja sobre sus predecesores: el uso de las computadoras electrónicas rápidas. El siguiente ejercicio muestra cómo comienza la prueba. Suponga que se tiene una gráfica plana simple que requiere más de cuatro colores para colorearla. Entre este tipo de gráficas, existe una con el número mínimo de vértices. Sea G una triangulación de esta gráfica. Entonces G también tiene el número mínimo de vértices y por el ejercicio 26, G requiere más de cuatro colores para colorearla.

28. Si el dual de un mapa tiene un vértice de grado 3, ¿cuál es  la apariencia del mapa original?
 

29. Demuestre que G no tiene un vértice de grado 3.


30. Demuestre que G no tiene un vértice de grado 4.


31. Demuestre que G tiene un vértice de grado 5. La contribución de Appel y Haken fue demostrar que sólo era necesario considerar y analizar un número finito de casos que incluyen el vértice de grado 5, y demostrar que todos se pueden colorear usando 4 colores. La reducción a un número finito de casos se facilitó al usar la computadora para ayudar a encontrar los casos que requieren análisis. De nuevo se usó la computadora para analizar los casos que resultan.


32. Demuestre que cualquier gráfica simple plana se puede colorear usando 5 colores.





Etiquetas:
Suscribirse a: Comentarios (Atom)