Han and Chewie are on the run from the Imperial Army. Starting from the Rebel's base on Yavin 4, in order to shake off Darth Vader's pursuit, they have to make a series of hyperspace jumps to seven different planets then return to the original base. However, the Millennium Falcon cannot make any jump longer than 12 parsec (Note: parsec is a unit of distance, not time). They looked up their star map and made the following table of the distances between planets. All the entries below are measured in parsec Yavin 4 Coruscant Tatooine Hoth EndorNaboo Kessel Dagobah Yavin 4 0 10 15 15 18 14 16 12 10 0 12 13 16 12 14 10 15 12 0 10 12 15 13 10 0 12 12 13 15 18 16 12 12 0 12 14 12 9 12 12 0 9 12 16 12 10 12 15 16 12 14 0 Coruscant 10 Tatooine Hoth Endor Naboo Kessel 13 10 0 Dagobah 12 16 (a) (4 points) Draw a graph that will help Han and Chewie plan their escape. Specify whether your graph is directed or undirected. Carefully describe what the vertices of your graph represent, and when two vertices are connected with an edge. (b) (2 points) Say which graph theory problem they are trying to solve on this graph ) (2 points) Find a feasible escape route for Han and Chewie that meets the constraints or explain why no such route exists. Han and Chewie are on the run from the Imperial Army. Starting from the Rebel's base on Yavin 4, in order to shake off Darth Vader's pursuit, they have to make a series of hyperspace jumps to seven different planets then return to the original base. However, the Millennium Falcon cannot make any jump longer than 12 parsec (Note: parsec is a unit of distance, not time). They looked up their star map and made the following table of the distances between planets. All the entries below are measured in parsec Yavin 4 Coruscant Tatooine Hoth EndorNaboo Kessel Dagobah Yavin 4 0 10 15 15 18 14 16 12 10 0 12 13 16 12 14 10 15 12 0 10 12 15 13 10 0 12 12 13 15 18 16 12 12 0 12 14 12 9 12 12 0 9 12 16 12 10 12 15 16 12 14 0 Coruscant 10 Tatooine Hoth Endor Naboo Kessel 13 10 0 Dagobah 12 16 (a) (4 points) Draw a graph that will help Han and Chewie plan their escape. Specify whether your graph is directed or undirected. Carefully describe what the vertices of your graph represent, and when two vertices are connected with an edge. (b) (2 points) Say which graph theory problem they are trying to solve on this graph ) (2 points) Find a feasible escape route for Han and Chewie that meets the constraints or explain why no such route exists