The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
98 views

City authorities are concerned about traffic accidents on major roads. They would like to have ambulances stationed at road intersections to quickly reach the scene of any accident along these roads. To minimize response time, ambulances are to be located at intersections with traffic lights so that any segment of road can be reached by at least one ambulance that does not have to pass through a traffic light to reach the scene of the accident. If we model the road network as a graph, where intersections with traffic lights are vertices and edges represent road segments between traffic lights, the graph-theoretic question to be answered is:

  1. Find a spanning tree with minimum number of edges.
  2. Find a spanning tree with minimum cost.
  3. Find a minimal coloring.
  4. Find a minimum size vertex cover.
in Graph Theory by Boss (18.1k points)
edited by | 98 views

1 Answer

0 votes
If we imagine city with proper block then graph will be somewhat like n*m grid with intersection point as vertex.

So we have to find an vertex where absence of ambulance would cause problem. This is similary to finding minimum number of vertex such that each edge is covered.

Hence answer would be finding vertex cover.
by Boss (18.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,362 questions
55,786 answers
192,411 comments
90,919 users