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

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

project graph theory transport max flow stepping stone

Project Graph Theory: Starship Troopers project graph theory

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

Task 1: Relocate the production

Project Graph Theory: Starship Troopers project graph theory

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

Project Graph Theory: Starship Troopers project graph theory

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.

Project Graph Theory: Starship Troopers project graph theory

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

Project Graph Theory: Starship Troopers project graph theory

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!

Project Graph Theory: Starship Troopers project graph theory
  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!

Project Graph Theory: Starship Troopers project graph theory

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)
To share