As we have discussed in this class $($see section $1\mathrm{.}5\mathrm{.}2$ of the textbook$),$ the problem of finding

a shortest path in a graph G $=($V$,$ E$)$ can be formulated using st$-$cuts. In particular the cut

constraints run over all U $$ V$,$ s in U$,$ t $6$ in U$.$ Show that it suffices for the cut constraints to

run over U $$ V$,$ s in U$,$ t $6$ in U with the additional property that the subgraph induced by U is

connected $($there exists a path between any two vertices in U that is only using vertices in U$).$

$($b$)$ You were running on the trails near the Laurel Creek Nature Centre in Waterloo when you fell

and hurt your knee. Now you just want to get back to your car by the shortest route possible.

The trails are configured as in the following graph.Question $3.(20$PTS$)$

This answer should fit on: $2$ page$($s$).$

Follow the Rules on how to write solutions to assignments and exams posted on the course page!!!

$($a$)$ As we have discussed in this class $($see section $1\mathrm{.}5\mathrm{.}2$ of the textbook$),$ the problem of finding

a shortest path in a graph $G=(V,E)$ can be formulated using st$-$cuts. In particular the cut

constraints run over all UsubeV,$sinU,t!$inU. Show that it suffices for the cut constraints to

run over UsubeV,$sinU,t!$inU with the additional property that the subgraph induced by $U$ is

connected $($there exists a path between any two vertices in $U$ that is only using vertices in $U).$

$($b$)$ You were running on the trails near the Laurel Creek Nature Centre in Waterloo when you fell

and hurt your knee. Now you just want to get back to your car by the shortest route possible.

The trails are configured as in the following graph.

You are at $i.$ You want to get to $a.$ The distances are as follows:

$ab$:$160m,bc$:$350m$ be: $350m,$ ce: $220m$ ef: $10m$

$fg$:$210m$ fh: $300m$ gh: $300m$ gi: $190m,$ hi: $260m$

Write the problem as an integer program using the insight of the previous part.