Description
Imagine a graph representing a network of stations (nodes) connecting by roads
(edges). If a camera is placed at a node, it can “watch” all roads connected to it. For
example, in the network rg_10_15_2018, a camera placed at station 8 can watch the
roads that connect station 8 to stations 3, 4, and 0. In this network, cameras placed
at stations 3, 4, 0 and 1 can watch all roads. Therefore, {3, 4, 0, 1} is a camera
placement on this network that covers all roads.
1. (30 points) Write a Python program, using the backtracking technique we
learned, to generate all possible camera placements on a network. Test your
program on the 3 networks above.
2. (30 points) We are limited with resources and have budget for only 6 cameras.
Write a Python program, using the backtracking technique we learned, to
generate all possible camera placements on a network that use only 6 or fewer
cameras. Test your program on the 3 networks above.
3. (30 points) Write a Python program, using the backtracking technique we
learned, to find the minimum number of cameras that can be placed to watch all
roads of a given network. Print out the placement that gives the minimum
number of cameras. Test your program on the 3 networks above.
4. (10 points) Again we have a budget of k cameras. For example, k=6. We want
the camera to cover as many roads as possible. It is possible we won’t be able
to cover all roads. Write a Python program, using the backtracking technique we
learned, to find the camera placements that cover as many roads as possible.
