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

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

**Scale: 50 points**

__10 points____15 points____10 points____15 points__

### “Violence, naked force, has settled more issues in history than has any other factor.”

## 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 |

- Find the price of each stuff for each planet (
)**1 point** - Draw a table for the problem (
s)**5 point** - Resolve the problem (
s)**3 point** - Draw the problem as a graph (
s)**5 point** - Solve the problem with excel (
s)**3 point**

## 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.

- Graph without refueling stop
- Draw the graph where costs are equal to used fuel (
)**1 point** - Find all the shortest paths (
s)**5 point** - Draw the tree of shortest paths (
)**1 point**

- Draw the graph where costs are equal to used fuel (
- Graph with refueling stop
- Draw the graph where costs are equal to used fuel (
s)**2 point** - Find all the shortest paths (
s)**5 point** - Draw the tree of shortest paths (
)**1 point**

- Draw the graph where costs are equal to used fuel (

## 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!

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

## 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 par 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 |

- Resolve the transportation problem
- Show the problem as a bipartite graph with costs and flow (
)**5 point** - Find the tableau (
s)**2 point** - Resolve the problem with Stepping Stone method (
s)**5 point**

- Show the problem as a bipartite graph with costs and flow (
- Resolve the flow problem
- Find an algorithm to solve the problem (min cost flow), explain it and show the flowchart (4.5
s)**point** - Show a solution (
s)**5 point**

- Find an algorithm to solve the problem (min cost flow), explain it and show the flowchart (4.5