Contents

## Project Graph Theory: Starship Troopers

The Project graph theory: Starship Troopers includes various graph theory problems as pathfinding, max flow problem, assignment.

 ETC: 15 hours (deadline - 5 classes)3-4 students per teamPlease take your time on both quality and contentsAssociate professor and assistant professors will not answer questions about the project.

Scale: 50 points

1. 10 points
2. 15 points
3. 10 points
4. 15 points

## Task 1: Relocate the production

In the 23rd century, Earth has become a space-faring civilization. While colonizing new planets, humans have encountered an insectoid species known as Arachnids, with their home being the distant world Klendathu. The bugs appear to be little more than savage, unrelenting killing machines, although there are suggestions that they were provoked by the intrusion of humans into their habitats.

At a rich salesman, you don't need to perform our military service for the Federation. Our wealth comes from various factories which produce basics and stuff for armies. Since Klendathu has fallen, the war has intensified and spreads to the whole galaxy. Our factories aren't optimized; they produce all kinds of stuff when it costs a lot to bring material to the different industrial planets. You have to rethink how to produce in function of material costs and material needed to build stuff (only use material based on the planet).

Extraction cost of material by planets:

 Planet | Material Dilithium Duranium Element Zero Tritanium 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

Costs in Mg of each material to build stuff:

 Stuff | Material Dilithium Duranium Element Zero Tritanium Droideka 1 0.6 0.8 1.2 Vulture fighter 0.9 1 0.1 1.3 T-droid 0.7 1.3 1 0.5 Hailfire droid 0.5 0.3 0.1 1 MagnaGuards 0.9 0.9 0.9 1.1

1. Find the price of each stuff for each planet (1 point)
2. Draw a table for the problem (5 points)
3. Solve the problem (3 points)
4. Draw the problem as a graph (5 points)
5. Solve the problem with excel (3 points)

## Task 2: Move our troops

Your factories run at full speed. The brand new equipment will allow having ascendancy on the Arachnids.

You have an unlimited stock compared to military needs. If they need more, they will provide you more funds. In order to limit your fuel expenses at most, your transport vessels will take only the bare minimum to make the journey.

The cost in kilograms of Unobtainium of your Holtzmann reactors varies depending on the distance and gravity of the planets.

 Cost of take-off Giedi Prime (1) Betelgeuse (2) Wallach IX (3) Lampadas (4) Ix (5) – 3.5e2 1.25e2 1.75e2 2.12e2 0.8e2
 Cost of landing Kharak (6) Klendathu (7) M6-117 (8) Tallarn (9) Dyson (10) Gaea (11) Onyx (12) Discworld (13) Htrae (14) – 254 89 211 370 50 78 23 89 147

Since the capacity of your transport is limited, it is not always possible to make direct journeys between planet-factories and planet-training. To do this, you have to go through the orbital stations to refuel, so you lose some of the fuel during your stopover in order to perform the maneuvers. Here is a table representing the loss in Unobtainium for a stopover on possible destinations.

 Stepover fuel costs Kharak (6) Klendathu (7) M6-117 (8) Tallarn (9) Dyson (10) Gaea (11) Onyx (12) Discworld (13) Htrae (14) 200 100 240 500 200 80 70 20 140

And a table showing the reachable planets from each of them and the fuel cost for the supra-liminal path.

 To | from 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 –

For example, case (i, j) means you leave the planet i for the planet j. The cost to travel from j to i is the same.

1. Graph without refueling stop
1. Draw the graph where costs are equal to used fuel (1 point)
2. Find all the shortest paths (5 points)
3. Draw the tree of shortest paths (1 point)
2. Graph with refueling stop
1. Draw the graph where costs are equal to used fuel (2 points)
2. Find all the shortest paths (5 points)
3. Draw the tree of shortest paths (1 point)

## Task 3: Massive attack

Your armies are ready to launch the final assault. The General Staff of the Federation located the last bastions of the Arachnids. You must prepare your troops in the utmost discretion before launching the attack simultaneously on several fronts (from lunar bases).

Holtzmann reactors leave a small disturbance in space-time during a journey. After skillful calculations, you have determined the maximum number of vessels that can pass through each interstellar route to the nearest lunar bases.

 Lunar 1 Lunar 2 Lunar 3 Lunar 4 Lunar 5 Lunar 6 Lunar 7 Lunar 8 Lunar 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

Case (i, j) means you travel from i to j.

Stock the maximal number of troops at Lunar 5 to Lunar 9 (5, 6, 7, 8, 9). Your armies are ready! Let's go!

1. Show this problem as a flow problem (1 point)
2. Solve the problem (5 point)
3. Show the solution with a graph (5 points)
4. Find the min-cut (5 points)
5. Which edge of the cut can increase at most the global flow? (5 points)

## Task 4: Never surrender!

The fighting is not going as well as expected. The Arachnid resistance is fierce and the losses of the Federation are counted in millions of soldiers and trillions of Earthos. Your production struggles to cover the losses and you have to rearrange your orders so as not to disadvantage a front.

Your productions in a number of troops (without distinction) are the following:

 Giedi Prime Betelgeuse Wallach IX Lampadas Ix 600 400 500 450 350

And the requests for reinforcements are the following:

 Front 1 Front 2 Front 3 Front 4 Front 5 Front 6 Front 7 500 300 400 250 250 600 300

You are financially on the edge of the abyss. In order to be able to keep the front in place for as long as possible, you must send reinforcements available by spending the least amount of fund (part of the transport is financed by the Federation, the leftovers is out of your pocket).

 To | From Giedi Prime Betelgeuse Wallach IX Lampadas Ix Front 1 1 3 5 4 5 Front 2 4 6 2 6 1 Front 3 5 1 5 3 2 Front 4 2 6 3 4 7 Front 5 3 4 1 6 7 Front 6 5 2 6 5 1 Front 7 3 5 4 2 3

This is not so simple. Of course, you cannot send infinite troops by from any place to any front. Routes are also defined by a limited flow as shown in the following table:

 To | From Giedi Prime Betelgeuse Wallach IX Lampadas Ix Front 1 200 105 135 95 65 Front 2 100 200 30 55 80 Front 3 125 25 50 75 90 Front 4 400 25 80 90 105 Front 5 95 120 70 50 110 Front 6 60 75 65 140 40 Front 7 80 55 140 100 200
1. Resolve the transportation problem
1. Show the problem as a bipartite graph with costs and flow (5 point)
2. Find the array (2 points)
3. Solve the problem with Stepping Stone method (5 points)
2. Solve the flow problem
1. Find an algorithm to solve the problem (min cost flow), explain it and show the flowchart (4.5points)
2. Show a solution (5 points)
FR
FR
EN
ES