Teoría de Gráficas - Capítulo 8 PDF

# Capítulo 8 ## TEORÍA DE GRÁFICAS ### 8.1 Introducción #### Trayectorias y ciclos #### Rincón de solución de problemas: gráficas #### Ciclos hamiltonianos y el problema del agente viajero #### Un algoritmo de la ruta más corta #### Representaciones de gráficas #### Isomorfismos de gráficas #### Gráficas planas #### Locura instantánea #### Notas #### Repaso del capítulo #### Autoevaluación del capítulo #### Ejercicios para computadora Bueno, salí de viaje, y fui al norte, a Providence. Conocí al alcalde. ¡El alcalde de Providence! Estaba sentado en el lobby del hotel. ¿Qué dijo? Dijo "Buenos días”, y yo dije: “Tiene una linda ciudad, alcalde". Y después tomó café conmigo. Luego fui a Waterbury, que es una ciudad agradable, una ciudad con un gran reloj, el famoso reloj de Waterbury. Vendí una buena factura ahí. Y después Boston; Boston es la cuna de la revolución. Una hermosa ciudad. Luego un par de pueblos en Massachussets, y seguí a Portland y Bangor y ¡de regreso a casa! DE MUERTE DE UN VENDEDOR Aunque la primera publicación de teoría de gráficas data de 1736 (vea el ejemplo 8.2.16) y varios resultados importantes de teoría de gráficas se obtuvieron en el siglo XIX, no fue sino hasta 1920 que surgió un interés sostenido, amplio e intenso en la teoría de gráficas. En realidad, el primer libro de texto de este tema ([König]) apareció en 1936. Sin duda, una de las razones del reciente interés en la teoría de gráficas es su aplicabilidad en muchos campos, incluyendo ciencias de la computación, química, investigación de operaciones, ingeniería eléctrica, lingüística y economía. En este capítulo, primero se expone cierta terminología básica y ejemplos de gráficas. Después se analizan algunos conceptos importantes en la teoría de gráficas, que incluyen tra- yectorias y ciclos. Luego se presentan dos problemas clásicos, los ciclos hamiltonianos y el problema del agente viajero. Se presenta un algoritmo de la ruta más corta que encuentra con eficiencia la trayectoria más corta entre dos puntos dados. Después de exponer las maneras de representar las gráficas, se estudiará el tema de cuándo dos gráficas son en esencia la mis- ma (es decir, cuándo dos gráficas son isomorfas) y cuándo una gráfica se puede dibujar en el plano sin que sus aristas se crucen. Se concluirá con la presentación de una solución ba- sada en un modelo de gráfica para el juego de Locura instantánea. ### 8.1 Introducción La figura 8.1.1 muestra el sistema de carreteras de Wyoming; cierta persona es responsable de inspeccionar este sistema. En particular, el inspector de carreteras debe recorrerlas y entregar in- † Esta sección se puede omitir sin pérdida de continuidad. #### Figura 8.1.1 Parte del sistema de carreteras de Wyoming. formes de las condiciones de los caminos, la visibilidad de las líneas pintadas, el estado de las señales, etcétera. Como el inspector vive en Greybull, la manera más económica de inspec- cionar todos los caminos sería comenzar en Greybull, recorrer cada carretera exactamente una vez y regresar a Greybull. ¿Es esto posible? ¿Puede decidir antes de seguir leyendo? El problema se puede modelar como una gráfica. De hecho, como las gráficas se di- bujan con puntos y líneas, tienen la apariencia de mapas de carreteras. La figura 8.1.2, con- tiene el dibujo de una gráfica G que modela el mapa de la figura 8.1.1. Los puntos se llaman vértices y las líneas que conectan a los vértices se llaman aristas. (Más adelante en esta sec- ción, se definirán todos los términos con cuidado). Cada vértice se etiquetó con las primeras tres letras de la ciudad correspondiente. Las aristas se etiquetaron e₁,..., e13. Cuando se di- buja una gráfica, la única información de importancia es qué vértices se conectan con qué aristas. Por esta razón, la gráfica de la figura 8.1.2 pudo haberse dibujado como la figura 8.1.3. #### Figura 8.1.2 Modelo de gráficas para el sistema de carreteras de la figura 8.1.1. #### Figura 8.1.3 Modelo de gráficas alternativo, pero equivalente, del sistema de carreteras de la figura 8.1.1. Si se inicia en el vértice v, se viaja por una arista al vértice v₁, por otra arista al vér- tice v₂, etcétera, y con el tiempo se llega al vértice v; este viaje completo recibe el nombre de trayectoria o ruta de vo a v. La trayectoria que comienza en She, va a Buf y termina en Gil corresponde a un viaje en el mapa de la figura 8.1.1 que comienza en Sheridan, va a Buffalo y termina en Gillette. El problema del inspector de carreteras se enuncia de otra manera para el modelo de gráficas G: ¿Existe una ruta del vértice Gre al vértice Gre que pase una vez por todas las aristas? Es posible demostrar que el inspector de carreteras no puede comenzar en Greybull, viajar por cada camino justo una vez y regresar a Greybull. Para poner la respuesta en tér- minos de gráficas, no existe una trayectoria del vértice Gre al vértice Gre en la figura 8.1.2 que recorra todas las aristas una vez. Para ver esto, suponga que existe tal trayectoria y con- sidere el vértice Wor. Cada vez que se llega a Wor por alguna arista, se debe salir de Wor por una arista diferente. Más aún, cada arista que toca Wor se debe usar. Entonces las aris- tas en Wor ocurren en pares. Se concluye que un número par de aristas debe tocar Wor. Co- mo tres aristas tocan a Wor, se tiene una contradicción. Por lo tanto, no existe una trayectoria del vértice Gre al vértice Gre en la figura 8.1.2 que recorra todas las aristas jus- to una vez. El argumento se aplica a una gráfica arbitraria G. Si G tiene una trayectoria del vértice v al vértice v que recorre todas las aristas exactamente una vez, un número par de aristas deben tocar cada vértice. Este problema se estudia con más detalle en la sección 8.2. #### Definición 8.1.1 Por el momento, se dan algunas definiciones formales. Una gráfica (o gráfica no dirigida) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tal que cada arista e ∈ E se asocia con un par no ordenado de vértices. Si existe una arista única e asociada con los vértices u y w, se escribe e = (v, w) o e = (w, v). En este contexto, (v, w) denota una arista entre v y w en una gráfica no di- rigida y no es un par ordenado. Una gráfica dirigida (o digráfica) G consiste en un conjunto V de vértices (o nodos) y un conjunto E de aristas (o arcos) tales que cada arista e ∈ E está asociada con un par or- denado de vértices. Si hay una arista única e asociada con el par ordenado (v, w) de vérti- ces, se escribe e = (v, w), que denota una arista de v a w. Se dice que una arista e en una gráfica (no dirigida o dirigida) que se asocia con el par de vértices v y w es incidente sobre u y w, y se dice que v y w son incidentes sobre e y son vértices adyacentes. Si Ges una gráfica (no dirigida o dirigida) con vértices Vy aristas E, se escribe G = (V, E). A menos que se especifique lo contrario, se supone que los conjuntos E y V son fini- tos y que V es no vacío. En la figura 8.1.2 la gráfica (no dirigida) G consiste en el conjunto de vértices V = {Gre, She, Wor, Buf, Gil, Sho, Cas, Dou, Lan, Mud} #### Ejemplo 8.1.2 y el conjunto de aristas E {e1, 2, ..., 13} #### Ejemplo 8.1.3 La arista e, se asocia con un par no ordenado de vértices {Gre, She}, y la arista e10 se aso- cia con el par no ordenado de vértices {Cas, Dou}. La arista e₁ se denota por (Gre, She) o (She, Gre), y la arista e10 se denota por (Cas, Dou) o (Dou, Cas). La arista e₁ es incidente sobre Wor y Buf, y los vértices Wor y Buf son adyacentes. La figura 8.1.4 muestra una gráfica dirigida. Las aristas dirigidas se indican por flechas. La arista e₁ se asocia con el par ordenado de vértices (v2, v₁) y la arista e, se asocia con el par ordenado de vértices (υς, υ). La arista e₁ se denota (v2, v₁), y la arista e, se deno- ta (υς, υς). #### Figura 8.1.4 Una gráfica dirigida. La definición 8.1.1 permite que diferentes aristas se asocien con el mismo par de vér- tices. Por ejemplo, en la figura 8.1.5, las aristas e, y e₂ se asocian ambas con el par de vér- tices {v1, v2}. Estas aristas se llaman aristas paralelas. Una arista incidente en un mismo vértice se llama lazo. Por ejemplo, en la figura 8.1.5, la arista e3 = (v2, v₂) es un lazo. Un vértice como v₁ en la figura 8.1.5, que no incide en ninguna arista, se llama vértice aisla- do. Una gráfica sin lazos ni aristas paralelas se llama gráfica simple. #### Figura 8.1.5 Una gráfica con aristas paralelas y un lazo. #### Ejemplo 8.1.4 Como la gráfica de la figura 8.1.2 no tiene aristas paralelas ni lazos, es una gráfica simple. Algunos autores no permiten lazos o aristas paralelas cuando definen las gráficas. Se esperaría que si no se ha llegado a un acuerdo acerca de la definición de "gráfica", muchos de los términos en la teoría de gráficas tampoco tendrían definiciones estándar. Sin duda, esto es cierto. Al leer artículos y libros de gráficas, es necesario verificar las definiciones que se emplean. Se dará un ejemplo que muestra cómo se utiliza un modelo de gráficas para analizar un problema de manufactura. #### Ejemplo 8.1.5 Con frecuencia en la manufactura, es necesario hacer agujeros en hojas de metal (vea la figu- ra 8.1.6). Luego se atornillan las componentes a estas hojas de metal. Los agujeros se perfo- ran usando un taladro controlado por computadora. Para ahorrar tiempo y dinero, el taladro debe moverse tan rápido como sea posible. Se modelará la situación como una gráfica. Los vértices de la gráfica corresponden a los agujeros (figura 8.1.7). Cada par de vér- tices se conecta por una arista. En cada arista se escribe el tiempo para mover el taladro en- tre los hoyos correspondientes. Una gráfica con números en las aristas (como en la figura 8.1.7) se llama gráfica **ponderada**. Si la arista e se etiqueta k, se dice que el peso de la #### Figura 8.1.6 Hoja de metal con agujeros para tornillos. #### Figura 8.1.7 Modelo de gráficas de la hoja de metal de la figura 8.1.6. El peso de la arista es el tiempo para mover el taladro. arista e es k. Por ejemplo, en la figura 8.1.7 el peso de la arista (c, e) es 5. En una gráfica ponderada, la longitud de una ruta es la suma de los pesos de las aristas en la ruta. Por ejemplo, en la figura 8.1.7 la longitud de la ruta que comienza en a, visita c y termina en b es 8. En este problema, la longitud de una trayectoria que comienza en el vértice v, y lue- go visita v2, 03, , en este orden, y termina en v representa el tiempo que toma al tala- dro comenzar en el agujero h₁ y luego moverse a h2, h3, ..., en ese orden y terminar en h₁₁, donde el agujero h₁ corresponde el vértice v₁. Una ruta de longitud mínima que visita todos los vértices exactamente una vez representa la ruta óptima que debe seguir el taladro. Suponga que en este problema se requiere que la trayectoria comience en el vértice a y termine en el vértice e. Se puede encontrar la ruta de longitud mínima numerando to- das las rutas posibles de a a e que pasan por todos los vértices justo una vez y eligiendo la menor (vea la tabla 8.1.1). Se ve que la ruta que visita los vértices a, b, c, d, e, en ese or- den, tiene longitud mínima. Por supuesto, un par diferente de vértices de inicio y termina- ción produciría una ruta aún más corta. #### Tabla 8.1.1 Trayectorias en la gráfica de la figura 8.1.7 de a a e que pasan por todos los vértices justo una vez, y sus longitudes. | Trayectoria | Longitud | |---|---| | a, b, c, d, e | 21 | | a, b, d, c, e | 28 | | a, c, b, d, e | 24 | | a, c, d, b, e | 26 | | a, d, b, c, e | 27 | | a, d, c, b, e | 22 | Numerar todas las trayectorias de un vértice v a un vértice w, como se hizo en el ejemplo 8.1.5, es una manera bastante tardada para encontrar la trayectoria de longitud mí- nima de va w que visita todos los vértices una vez. Por desgracia, nadie conoce un méto- do que sea mucho más práctico para gráficas arbitrarias. Este problema es una versión del problema del agente viajero. Se estudiará ese problema en la sección 8.3. #### Ejemplo 8.1.6 ##### Números de Bacon El actor Kevin Bacon ha aparecido en numerosas películas que incluyen Diner y Apollo 13. Se dice que los actores que han aparecido en una película con Bacon tienen un uno de nú- mero Bacon. Por ejemplo, Ellen Barkin tiene un uno de número Bacon porque apareció con Bacon en Diner. Los actores que no hicieron una película con Bacon pero que trabajaron con un actor cuyo número Bacon es uno, se dice que tienen dos de número de Bacon. Los números de Bacon más altos se definen de manera similar. Por ejemplo, Bela Lugosi tiene un número de Bacon de tres. Lugosi actuó en Black Friday con Emmett Vogan, quien es- tuvo en With a Song in My Heart con Robert Wagner y Wagner trabajó en Wild Things con Bacon. Se desarrollará un modelo de gráficas para los números de Bacon. Los vértices denotan actores; se coloca una arista entre dos actores diferentes si apa- recieron juntos en al menos una película (vea la figura 8.1.8). En una gráfica no pondera- da, la longitud de una ruta es el número de aristas en ella. Entonces el número de Bacon de un actor es la longitud de la ruta más corta desde el vértice correspondiente a ese actor has- ta el vértice de Bacon. En la sección 8.4 se analiza el problema general de encontrar la ru- ta más corta en una gráfica. A diferencia de la situación del ejemplo 8.1.5, existen algoritmos eficientes para encontrar la ruta más corta. Es interesante que la mayoría de los actores, incluso aquellos que murieron hace años, tienen números de Bacon de tres o menos. La página de Internet de este libro tiene un enlace a una página que verifica los números de Bacon de actores arbitrarios. Vea en el ejercicio 30 un modelo de gráficas similar. #### Figura 8.1.8 Parte de una gráfica que modela los números de Bacon. Los vértices denotan actores. Existe una arista entre dos actores si aparecieron juntos en al menos una película. Por ejemplo, hay una arista entre Ellen Barkin y Dennis Quaid porque ambos aparecieron en The Big Easy. El número de Bacon de un actor es la longitud de la ruta más corta entre el actor y Bacon. Por ejemplo, el número de Bacon de Bela Lugosi es tres porque la longitud de la ruta más corta entre Lugosi y Bacon es tres. #### Ejemplo 8.1.7 ##### Gráficas de similitud Este ejemplo trata el problema de agrupar objetos "similares" en clases basadas en las pro- piedades de los objetos. Por ejemplo, suponga que cierto número de personas implementan en C++ un algoritmo dado y que se quiere agrupar los programas "parecidos" en clases determinadas por ciertas propiedades de los programas (vea la tabla 8.1.2). Suponga que se seleccionan como propiedades 1. El número de líneas en el programa 2. El número de instrucciones para regresar (return) en el programa 3. El número de llamadas de funciones en el programa #### Tabla 8.1.2 Programas en C++ que implementan el mismo algoritmo | Programa | Número de líneas de programa | Número de instrucciones "return" | Número de llamadas de funciones | |---|---|---|---| | 1 | 66 | 20 | 1 | | 2 | 41 | 10 | 2 | | 3 | 68 | 5 | 8 | | 4 | 90 | 34 | 5 | | 5 | 75 | 12 | 14 | Una gráfica de similitud G se construye como sigue. Los vértices corresponden a los programas. Un vértice se denota por (P1, P2, P3), donde p; es el valor de la propiedad i. Se define una función de disimilitud s como sigue. Para cada par de vértices v = (p1, P22 P3) y w = (91, 92, 93) se establece s(v, w) = |P1-911+P2-92 + P3-931. Si v es el vértice correspondiente al programa i, se obtiene S(V1, V2) = 36, S(V2, V3) = 38, $(v1, 03) = 24, s(v2, v₄) = 76, $(v3, 15) = 20, S(01, 0₄) = 42, s(V2, 05) = 48, $(v1, 25) = 30, ς(υς, υ₄) = 54, $(24, 25) = 46. #### Figura 8.1.9 Una gráfica de similitud correspondiente a los programas de la tabla 8.1.2 con S = 25. Si v y w son vértices correspondientes a dos programas, s(v, w) es una medida de qué tan disímiles son los programas. Un valor grande de s(v, w) indica disimilitud, mientras que un valor pequeño indica similitud. Para un número fijo S, se inserta una arista entre dos vértices v y w si s(v, w) < S. (En general, habrá gráficas de similitud diferentes para valores distintos de S.) Se dice que v y w están en la misma clase si v = wo si hay una trayectoria de v a w. En la figura 8.1.9

Teoría de Gráficas - Capítulo 8 PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue