Accounting for the limited street parking in Philadelphia, the university has created a map of the n ≥ 2 possible locations to park scooters near campus, as well as the bidirectional paths that connect these parking spots. The map includes Houston Hall and Franklin Field as special parking locations that are designated for scooter pick-up. To enforce organization and decrease the risk of scooter-related injuries, the university wants to assign a one-way direction to each scooter path on the map (which means choosing an orientation; refer to the last paragraph) such that: all paths connected to Houston Hall lead away from Houston Hall, all paths connected to Franklin Field lead to Franklin Field, and for any other parking spot, it is impossible to return to that same spot once you’ve left it. As an Math student, you have been tasked to prove it is possible to satisfy these conditions. Note that the parking spots can be visualized as vertices and the scooter paths as edges in graph G. An orientation of an undirected graph G = (V, E) is a directed graph G′ = (V, E′) that has the same set V of vertices and whose set E′ of directed edges is obtained by choosing a direction on each of the edges of G. That is, for each edge u−v in E we put in E′ either the directed edge u→v or the directed edge v→u, but not both. Prove that every undirected graph has some orientation that is a DAG. Please show all your work and fully explain the problem in detail.
Accounting for the limited street parking in Philadelphia, the university has created a map of
the n ≥ 2 possible locations to park scooters near campus, as well as the bidirectional paths
that connect these parking spots. The map includes Houston Hall and Franklin Field as special
parking locations that are designated for scooter pick-up.
To enforce organization and decrease the risk of scooter-related injuries, the university wants
to assign a one-way direction to each scooter path on the map (which means choosing an
orientation; refer to the last paragraph) such that: all paths connected to Houston Hall lead
away from Houston Hall, all paths connected to Franklin Field lead to Franklin Field, and for
any other parking spot, it is impossible to return to that same spot once you’ve left it. As an
Math student, you have been tasked to prove it is possible to satisfy these conditions.
Note that the parking spots can be visualized as vertices and the scooter paths as edges in graph
G. An orientation of an undirected graph G = (V, E) is a directed graph G′ = (V, E′) that has
the same set V of vertices and whose set E′ of directed edges is obtained by choosing a direction
on each of the edges of G. That is, for each edge u−v in E we put in E′ either the directed edge
u→v or the directed edge v→u, but not both.
Prove that every undirected graph has some orientation that is a DAG.
Please show all your work and fully explain the problem in detail.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 1 images
