El Proyecto de teoría de grafos: Starship Troopers incluye varios problemas de teoría de grafos como camino, problema de flujo máximo, asignación.
ETC: 15 horas (fecha límite - 5 clases) 3-4 estudiantes por equipo Tómese su tiempo tanto en la calidad como en el contenido. El profesor asociado y los profesores asistentes no responderán preguntas sobre el proyecto. |
Escala: 50 puntos
- 10 puntos
- 15 puntos
- 10 puntos
- 15 puntos
"La violencia, la fuerza desnuda, ha resuelto más problemas en la historia que cualquier otro factor".
Tarea 1: reubicar la producción
En el siglo XXIII, la Tierra se ha convertido en una civilización espacial. Mientras colonizaban nuevos planetas, los humanos se han encontrado con una especie de insectoide conocida como Arácnidos, y su hogar es el mundo distante Klendathu. Los insectos parecen ser poco más que máquinas de matar salvajes e implacables, aunque hay indicios de que fueron provocados por la intrusión de humanos en sus hábitats.
En un vendedor rico, no es necesario que realice nuestro servicio militar para la Federación. Nuestra riqueza proviene de varias fábricas que producen productos básicos y material para ejércitos. Desde la caída de Klendathu, la guerra se ha intensificado y se ha extendido a toda la galaxia. Nuestras fábricas no están optimizadas; producen todo tipo de cosas cuando cuesta mucho llevar material a los diferentes planetas industriales. Tienes que repensar cómo producir en función de los costos de material y el material necesario para construir cosas (solo usa material basado en el planeta).
Costo de extracción de material por planetas:
Planeta | Material | Dilitio | Duranium | Elemento cero | Tritanio |
Giedi Prime | 1 | 1 | 1 | 0.1 |
Betelgeuse | 0.5 | 0.9 | 1.2 | 0.3 |
Wallach IX | 0.9 | 0.7 | 1.1 | 0.3 |
Lampadas | 1.2 | 0.1 | 1 | 0.2 |
IX | 0.7 | 2 | 0.3 | 0.1 |
Costos en Mg de cada material para construir cosas:
Cosas | Material | Dilitio | Duranium | Elemento cero | Tritanio |
Droideka | 1 | 0.6 | 0.8 | 1.2 |
Luchador buitre | 0.9 | 1 | 0.1 | 1.3 |
T-droide | 0.7 | 1.3 | 1 | 0.5 |
Droide de granizo | 0.5 | 0.3 | 0.1 | 1 |
MagnaGuards | 0.9 | 0.9 | 0.9 | 1.1 |
- Encuentra el precio de cada cosa para cada planeta (1 punto)
- Dibuja una tabla para el problema (5 puntoss)
- Resolver el problema (3 puntoss)
- Dibuja el problema como una gráfica (5 puntoss)
- Resuelve el problema con Excel (3 puntoss)
Tarea 2: Mueve nuestras tropas
Tus fábricas funcionan a toda velocidad. El nuevo equipo permitirá tener ascendencia sobre los arácnidos.
Tiene un stock ilimitado en comparación con las necesidades militares. Si necesitan más, le proporcionarán más fondos. Para limitar sus gastos de combustible como máximo, sus embarcaciones de transporte solo tomarán lo mínimo para hacer el viaje.
El costo en kilogramos de Unobtainium de sus reactores Holtzmann varía según la distancia y la gravedad de los planetas.
Costo de despegue | Giedi Prime (1) | Betelgeuse (2) | Wallach IX (3) | Lampadas (4) | Ix (5) |
– | 3.5e2 | 1.25e2 | 1.75e2 | 2.12e2 | 0.8e2 |
Costo de aterrizaje | Kharak (6) | Klendathu (7) | M6-117 (8) | Tallarn (9) | Dyson (10) | Gea (11) | Ónix (12) | Mundodisco (13) | Htrae (14) |
– | 254 | 89 | 211 | 370 | 50 | 78 | 23 | 89 | 147 |
Dado que la capacidad de su transporte es limitada, no siempre es posible realizar viajes directos entre las fábricas de planetas y el entrenamiento de planetas. Para ello, tienes que pasar por las estaciones orbitales para repostar, por lo que pierdes algo de combustible durante tu escala para poder realizar las maniobras. A continuación se muestra una tabla que representa la pérdida en Unobtainium por una escala en posibles destinos.
Costos de combustible de paso | Kharak (6) | Klendathu (7) | M6-117 (8) | Tallarn (9) | Dyson (10) | Gea (11) | Ónix (12) | Mundodisco (13) | Htrae (14) |
| 200 | 100 | 240 | 500 | 200 | 80 | 70 | 20 | 140 |
Y una tabla que muestra los planetas alcanzables desde cada uno de ellos y el costo del combustible para el camino supra-liminal.
Para | de | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
6 | 58 | 67 | 80 | – | – | – | 24 | – | 31 | 102 | – | – | – | – |
7 | – | 41 | 21 | 50 | – | 24 | – | 45 | 10 | 110 | 90 | – | – | 90 |
8 | – | – | 90 | 50 | 10 | – | 45 | – | – | – | – | 100 | – | 70 |
9 | – | – | – | – | – | 31 | 10 | – | – | 46 | 35 | 15 | 28 | – |
10 | – | – | – | – | – | 102 | 110 | – | 46 | – | 24 | 17 | – | – |
11 | – | – | – | – | – | – | 90 | – | 35 | 24 | – | 7 | – | – |
12 | – | – | – | – | – | – | – | 100 | 15 | 17 | 7 | – | – | 36 |
13 | – | – | – | – | – | – | – | – | 28 | – | – | – | – | 10 |
14 | – | – | – | – | – | – | 90 | 70 | – | – | – | 36 | 10 | – |
Por ejemplo, el caso (i, j) significa que deja el planeta i por el planeta j. El costo de viajar de j a i es el mismo.
- Gráfico sin parada de repostaje
- Dibuje el gráfico donde los costos son iguales al combustible usado (1 punto)
- Encuentra todos los caminos más cortos (5 puntoss)
- Dibuja el árbol de los caminos más cortos (1 punto)
- Gráfico con parada de repostaje
- Dibuje el gráfico donde los costos son iguales al combustible usado (2 puntoss)
- Encuentra todos los caminos más cortos (5 puntoss)
- Dibuja el árbol de los caminos más cortos (1 punto)
Tarea 3: Ataque masivo
Tus ejércitos están listos para lanzar el asalto final. El Estado Mayor de la Federación localizó los últimos baluartes de los Arácnidos. Debes preparar tus tropas con la máxima discreción antes de lanzar el ataque simultáneamente en varios frentes (desde bases lunares).
Los reactores de Holtzmann dejan una pequeña perturbación en el espacio-tiempo durante un viaje. Después de hábiles cálculos, ha determinado el número máximo de naves que pueden atravesar cada ruta interestelar hasta las bases lunares más cercanas.
| Lunar 1 | Lunar 2 | Lunar 3 | Lunar 4 | Lunar 5 | Lunar 6 | Lunar 7 | Lunar 8 | Luna 9 |
10 | 5 | – | 7 | – | – | – | – | – | – |
11 | 10 | – | – | – | – | – | – | – | – |
12 | 6 | 4 | – | 5 | – | – | – | – | – |
13 | – | 8 | – | – | – | – | – | – | – |
14 | – | 4 | – | – | 9 | – | – | – | – |
Lunar 1 | – | 2 | 7 | 8 | – | – | – | – | – |
Lunar 2 | 1 | – | – | 8 | 7 | – | – | – | – |
Lunar 3 | 4 | – | – | 3 | – | 5 | 5 | 2 | – |
Lunar 4 | – | – | 5 | – | 3 | 7 | – | 3 | – |
Lunar 5 | – | – | – | 4 | – | – | – | 1 | 10 |
El caso (i, j) significa que viaja de i a j.
Almacene el número máximo de tropas en Lunar 5 a Lunar 9 (5, 6, 7, 8, 9). ¡Tus ejércitos están listos! ¡Vamos!
- Muestre este problema como un problema de flujo (1 punto)
- Resolver el problema (5 puntos)
- Muestre la solución con una gráfica (5 puntoss)
- Encuentra el min-corte (5 puntoss)
- ¿Qué borde del corte puede aumentar como máximo el flujo global? (5 puntoss)
Tarea 4: ¡Nunca te rindas!
La lucha no va tan bien como se esperaba. La resistencia de los arácnidos es feroz y las pérdidas de la Federación se cuentan en millones de soldados y billones de terrícolas. Tu producción lucha por cubrir las pérdidas y tienes que reorganizar tus pedidos para no perjudicar a un frente.
Tus producciones en un número de tropas (sin distinción) son las siguientes:
Giedi Prime | Betelgeuse | Wallach IX | Lampadas | IX |
600 | 400 | 500 | 450 | 350 |
Y las solicitudes de refuerzos son las siguientes:
Frente 1 | Frente 2 | Frente 3 | Frente 4 | Frente 5 | Frente 6 | Frente 7 |
500 | 300 | 400 | 250 | 250 | 600 | 300 |
Estás financieramente al borde del abismo. Para poder mantener el frente en su lugar el mayor tiempo posible, debes enviar los refuerzos disponibles gastando la menor cantidad de fondo (parte del transporte es financiado por la Federación, las sobras están de tu bolsillo).
Para | De | Giedi Prime | Betelgeuse | Wallach IX | Lampadas | IX |
Frente 1 | 1 | 3 | 5 | 4 | 5 |
Frente 2 | 4 | 6 | 2 | 6 | 1 |
Frente 3 | 5 | 1 | 5 | 3 | 2 |
Frente 4 | 2 | 6 | 3 | 4 | 7 |
Frente 5 | 3 | 4 | 1 | 6 | 7 |
Frente 6 | 5 | 2 | 6 | 5 | 1 |
Frente 7 | 3 | 5 | 4 | 2 | 3 |
Esto no es tan sencillo. Por supuesto, no puedes enviar tropas infinitas de ningún lugar a ningún frente. Las rutas también están definidas por un flujo limitado como se muestra en la siguiente tabla:
Para | De | Giedi Prime | Betelgeuse | Wallach IX | Lampadas | IX |
Frente 1 | 200 | 105 | 135 | 95 | 65 |
Frente 2 | 100 | 200 | 30 | 55 | 80 |
Frente 3 | 125 | 25 | 50 | 75 | 90 |
Frente 4 | 400 | 25 | 80 | 90 | 105 |
Frente 5 | 95 | 120 | 70 | 50 | 110 |
Frente 6 | 60 | 75 | 65 | 140 | 40 |
Frente 7 | 80 | 55 | 140 | 100 | 200 |
- Resuelve el problema del transporte
- Muestre el problema como un gráfico bipartito con costos y flujo (5 puntos)
- Encuentra la matriz (2 puntoss)
- Resuelve el problema con Escalón método (5 puntoss)
- Resuelve el problema de flujo
- Encuentre un algoritmo para resolver el problema (flujo de costo mínimo), explíquelo y muestre el diagrama de flujo (4.5puntos)
- Mostrar una solución (5 puntoss)
ES 
FR 
EN