6.8: Ejercicio
- Page ID
- 110614
Habilidades
1. Para entregar correo en un barrio en particular, el transportista postal necesita caminar por cada una de las calles con casas (los puntos). Crear una gráfica con bordes que muestren dónde debe caminar el transportista para entregar el correo.
2. Supongamos que un pueblo tiene 7 puentes como se muestra a continuación. Crea una gráfica que podría ser utilizada para determinar si hay un camino que cruza todos los puentes una vez.
3. La siguiente tabla muestra los tiempos aproximados de manejo (en minutos, sin tráfico) entre cinco ciudades del área de Dallas. Cree una gráfica ponderada que represente estos datos.
\ (\ begin {array} {|l|l|l|l|l|}
\ hline &\ texto {Plano} &\ texto {Mesquite} &\ texto {Arlington} &\ texto {Arlington} &\ texto {Denton}
\\ hline\ texto {Fort Worth} & 54 & 52 & 19 & 42
\\ hline\ texto {Plano} & & 38 & 53 y 41\\
\ hline\ text {Mesquite} & & & & 43 & 56\
\\ hline\ text {Arlington} & & & & 50\
\ hline
\ end {array}\)
4. En la siguiente tabla se muestran las tarifas aéreas de ida entre 5 ciudades [1]. Crea una gráfica que muestre estos datos.
\ (\ begin {array} {|l|l|l|l|l|}
\ hline &\ text {Honolulu} &\ text {Londres} &\ text {Moscú} &\ text {Cairo}
\\\ hline\ text {Seattle} &\ $159 &\ $370 &\ $654 &\ $684
\\ hline\ text {Honolulu} &\ $830 & $854 &\ $801\\
\ hline\ text {Londres} & & &\ $245 &\ $323\
\ hline\ texto {Moscú} & & & &\ $329\
\ hline
\ end {array}\)
5. Encuentra el grado de cada vértice en la gráfica a continuación.
6. Encuentra el grado de cada vértice en la gráfica a continuación.
7. ¿Cuáles de estas gráficas están conectadas?
8. ¿Cuáles de estas gráficas están conectadas?
9. Los tiempos de viaje en tren para un segmento del sistema Eurail se muestran a continuación con tiempos de viaje en horas y minutos [2]. Encuentre la ruta con el tiempo de viaje más corto de Berna a Berlín aplicando el algoritmo de Dijkstra.
10. Usando la gráfica del problema anterior, encuentra la ruta con el tiempo de viaje más corto de París a München.
11. ¿Cada una de estas gráficas tiene un circuito de Euler? Si es así, encuéntralo.
12. ¿Cada una de estas gráficas tiene un circuito de Euler? Si es así, encuéntralo.
13. Euleriza esta gráfica usando la menor cantidad posible de duplicaciones de bordes. Después, encuentra un circuito de Euler.
14. Euleriza esta gráfica usando la menor cantidad posible de duplicaciones de bordes. Después, encuentra un circuito de Euler.
15. El personal de mantenimiento de un parque de diversiones necesita patrullar las principales pasarelas, que se muestran en la gráfica de abajo, recolectando basura. Encuentra una ruta de patrulla eficiente encontrando un circuito de Euler. Si es necesario, eulerizar la gráfica de manera eficiente.
16. Después de una tormenta, la tripulación de la ciudad inspecciona si hay árboles o maleza que bloqueen la carretera. Encuentra una ruta eficiente para el vecindario a continuación encontrando un circuito de Euler. Si es necesario, eulerizar la gráfica de manera eficiente.
17. ¿Cada una de estas gráficas tiene al menos un circuito hamiltoniano? Si es así, encuentra uno.
18. ¿Cada una de estas gráficas tiene al menos un circuito hamiltoniano? Si es así, encuentra uno.
19. Una empresa necesita entregar el producto a cada una de sus 5 tiendas alrededor del área de Dallas, TX. A continuación se muestran las distancias de manejo entre las tiendas. Encuentre una ruta para que el conductor siga, regresando al centro de distribución en Fort Worth:
- Uso de Vecino más cercano comenzando en Fort Worth
- Uso del vecino más cercano repetido
- Uso de bordes ordenados
\ (\ begin {array} {|l|l|l|l|l|}
\ hline &\ texto {Plano} &\ texto {Mesquite} &\ texto {Arlington} &\ texto {Arlington} &\ texto {Denton}
\\ hline\ texto {Fort Worth} & 54 & 52 & 19 & 42
\\ hline\ texto {Plano} & & 38 & 53 y 41\\
\ hline\ text {Mesquite} & & & & 43 & 56\
\\ hline\ text {Arlington} & & & & 50\
\ hline
\ end {array}\)
20. Un vendedor necesita viajar de Seattle a Honolulu, Londres, Moscú y El Cairo. Usa la tabla de costos de vuelo del problema #4 para encontrar una ruta para que esta persona siga:
- Usando Neighbor Nearest comenzando en Seattle
- Uso del vecino más cercano repetido
- Uso de bordes ordenados
21. Al instalar fibra óptica, algunas compañías instalarán un anillo sonet; un bucle completo de cable que conecta múltiples ubicaciones. Esto se utiliza para que si alguna parte del cable se daña no interrumpa el servicio, ya que hay una segunda conexión al hub. Una empresa cuenta con 5 edificios. A continuación se muestran los costos (en miles de dólares) para tender cables entre pares de edificios. Encuentra el circuito que minimizará el costo:
- Uso del vecino más cercano a partir del edificio A
- Uso del vecino más cercano repetido
- Uso de bordes ordenados
22. Un turista quiere visitar 7 ciudades de Israel. A continuación se muestran las distancias de manejo, en kilómetros, entre las ciudades [3]. Encuentra una ruta para que la persona siga, regresando a la ciudad de salida:
- Usando Neighbor Nearest comenzando en Jerusalén
- Uso del vecino más cercano repetido
- Uso de bordes ordenados
\ (\ begin {array} {|l|l|l|l|l|l|l|l|}
\ hline &\ text {Jerusalén} &\ text {Tel Aviv} &\ text {Haifa} &\ text {Tiberíades} &\ texto {Cerveza Sheba} &\ texto {Eilat}
\\\ hline\ texto {Jerusalén} &\ _ & & & &
\ hline\ texto { Tel Aviv} & 58 &\ _ & & & & &\
\\ hline\ text {Haifa} & 151 & 95 &\ _ &\ _ & &
\\ hline\ texto {Tiberias} & 152 & 134 & 69 &\ _ & &\
\ hline\\ texto {Cerveza Sheba} & 81 & 105 & 197 & 233 &\ _ &\\
\ hline\ texto {Eilat} & 309 & 346 & 438 & 405 & 241 &\ _\
\ hline\ texto {Nazaret} & 131 & 102 & 35 & 29 & 207 & 488\
\ hline
\ end {array}\)
23. Encuentre un árbol de expansión de costos mínimos para la gráfica que creó en el problema #3
24. Encuentre un árbol de expansión de costos mínimos para la gráfica que creó en el problema #22
25. Encuentre un árbol de expansión de costo mínimo para la gráfica del problema #21
Conceptos
26. ¿Puede una gráfica tener un vértice con grado impar? Si no, ¿hay otros valores que no son posibles? ¿Por qué?
27. Una gráfica completa es aquella en la que hay un borde que conecta cada vértice con cada otro vértice. ¿Para qué valores de n la gráfica completa con n vértices tiene un circuito de Euler? ¿Un circuito hamiltoniano?
28. Crea una gráfica dibujando n vértices en una fila, luego otros n vértices por debajo de esos. Dibuja un borde desde cada vértice de la fila superior hasta cada vértice de la fila inferior. Un ejemplo cuando n=3 se muestra a continuación. ¿Para qué valores de n una gráfica creada de esta manera tendrá un circuito de Euler? ¿Un circuito hamiltoniano?
29. Eulerizar esta gráfica de la manera más eficiente posible, considerando los pesos de los bordes.
30. Eulerizar esta gráfica de la manera más eficiente posible, considerando los pesos de los bordes.
31. Eulerizar esta gráfica de la manera más eficiente posible, considerando los pesos de los bordes.
32. Eulerizar esta gráfica de la manera más eficiente posible, considerando los pesos de los bordes.
Exploraciones
33. Las redes sociales como Facebook y LinkedIn se pueden representar usando gráficas en las que los vértices representan a las personas y los bordes se dibujan entre dos vértices cuando esas personas son “amigas”. En la siguiente tabla se muestra una tabla de amistad, donde una X muestra que dos personas son amigas.
34.
- Crea una gráfica de esta tabla de amistad
- Encuentra el camino más corto de A a D. La longitud de este camino se suele llamar los “grados de separación” de las dos personas.
- Extensión: Dividir en grupos. Cada grupo elegirá 10 o más películas, y buscará a sus actores principales (www.imdb.com es una buena fuente). Crea una gráfica con cada actor como vértice, y bordes conectando a dos actores en una misma película (anote el nombre de la película en el borde). Encuentra caminos interesantes entre actores, y prueba a los otros grupos para ver si pueden adivinar las conexiones.
35. Un corrector ortográfico en un programa de procesamiento de textos hace sugerencias cuando encuentra una palabra que no está en el diccionario. Para determinar qué palabras sugerir, trata de encontrar palabras similares. Una medida de similitud de palabras es la distancia Levenshtein, que mide el número de sustituciones, adiciones o eliminaciones que se requieren para cambiar una palabra por otra. Por ejemplo, las palabras escupir y punto están a una distancia de 1; cambiar asador a punto requiere una sustitución (i por o). De igual manera, el asador está a la distancia 1 del hoyo ya que el cambio requiere una eliminación (las s). La palabra despecho también es distancia 1 de escupir ya que requiere una adición (la e). La palabra hollín es la distancia 2 de escupir ya que se requerirían dos sustituciones.
- Crea una gráfica usando palabras como vértices, y bordes conectando palabras con una distancia Levenshtein de 1. Usa la palabra mal escrita “moke” como centro e intenta encontrar al menos 10 palabras del diccionario conectadas. ¿Cómo podría un corrector ortográfico usar esta gráfica?
- Mejore el método desde arriba asignando un peso a cada borde en función de la probabilidad de realizar la sustitución, adición o eliminación. Puedes basar los pesos en cualquier enfoque razonable: proximidad de teclas en un teclado, errores comunes de lenguaje, etc. Usa el algoritmo de Dijkstra para encontrar la longitud del camino más corto de cada palabra a “moke”. ¿Cómo podría un corrector ortográfico usar estos valores?
36. La siguiente gráfica contiene dos vértices de grado impar. Para eulerizar esta gráfica, es necesario duplicar aristas que conectan esos dos vértices.
- Usa el algoritmo de Dijkstra para encontrar la ruta más corta entre los dos vértices con grado impar. ¿Esto produce la eulerización más eficiente y resuelve el problema del cartero chino para esta gráfica?
- Supongamos que una gráfica tiene vértices\(n\) impares. Usando el enfoque de la parte a, ¿cuántos caminos más cortos necesitarían considerarse? ¿Este enfoque va a ser eficiente?
[1] Tarifas más baratas encontradas al ser recuperadas Sept 1, 2009 para viajar Sept 22, 2009
[2] De www.eurail.com/eurail-railway-map
[3] De http://www.ddtravel-acc.com/Israel-c...s-distance.htm