Problem $5$: Consider the data on the London subway from the first project. We want to monitor stations so that we can find out if there is any disruption in the system.

$1.$ Suppose that disruptions can only occur in edges between stations and, if a station is monitored, we will find out if there is a disruption in any of the edges that are adjacent to this station. Write the problem of finding out if there is a disruption in the system by monitoring the smallest number of stations as an integer programming problem and solve it with your favorite software.

$2.$ Ignore the hypothesis from part $1.$ above. Suppose that disruptions can only occur in stations and, if a station $\backslash ($ i $\backslash )$ is monitored, we will find out if there is a disruption in any station $\backslash ($ j $\backslash )$ that has distance at most $2$ from station $\backslash ($ i$^\{1\}\backslash ).$ Write the problem of finding out if there is a disruption in the system by monitoring the smallest number of stations as an integer programming problem and solve it with your favorite software.

$3.$ Consider the following modification of part $2.$ above. We want to be able to monitor stations so that we will always realize that there is a disruption if a disruption occurs in $10$ or more stations. Again, write the problem of achieving our goal by minimizing the number of monitored stations as an integer program and solve it$.$