50.1K

Verified Solution

Link Copied!

In a forest area, the forest department wants to place a total of 10 sensors for detection fire, one sensor for each point defined on the map below.

There are two types of sensors. Type A, in addition to recognizing range fires of it, it can receive signals from neighboring sensors and send its coordinates point that has a fire approaching the control center. Type B recognizes fires in range, it cannot receive signals and can only send signals to neighbors sensors.

Sensor A costs 1050 and sensor B costs 190. Because of the high cost sensor A, it was decided to purchase as few A sensors as possible based on the following design. Each sensor A will be placed on one point of the map and on the rest of the points a type B sensor will be placed. The A sensors should be placed against in such a way that each sensor B neighbors at least 2 sensors A. Selected this design so that, in the event that in the future any sensor A acquires failure, there should be a floating sensor A that transmits the signal of the neighboring sensor B in the control center.

A. Model the problem as an Integer Programming problem. B. Generalize the above problem for any initial graph G=(V,E) such that every vertex that has sensor B is adjacent to at least m vertices that have sensor A.

(It is emphasized that all vertices have exactly one sensor on them and there is no vertex without sensor).

Answer & Explanation Solved by verified expert

See Answer