Road Cover

In a small town, there are roads between junctions and the road network looks like this:

The mayor wants to place traffic police posts in these junctions in the following way:

  1. Every road must be incident on at least one junction in which there is a traffic police post.
  2. The number of traffic police posts must be as few as possible.

The mayor makes the following reasoning:

Because junction 3 is incident on the maximum number of roads, I must place a traffic police post on junction 3 to minimize the number of traffic police posts.

Is he correct?


Problem Loading...

Note Loading...

Set Loading...