HW 6

Phipps Garden Subway Problem


Written submission is due in lecture on Wednesday, April 11 2012.

I’m updating this post according to the restatement given in lecture on Friday.

You’re given a map of a subway rail system (planar graph). Each face (except the outer one) of the planar graph is a country with a train that travels around it continuously in the clockwise direction.

All vertices are intersections of track of degree 3. Furthermore, the graph is 2-edge-connected, meaning you can’t delete a single edge and disconnect the graph.

Prove that there is a scheduling algorithm that guarantees no gridlocks and no starvation.

No gridlocks means that trains may only travel in one direction on a rail at one time. No starvation means that every train must make infinitely many trips around its face.

If the planar graph is embedded on a sphere, there’s now an outside country that has a train traveling clockwise. Prove that there is no scheduling algorithm.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s