sigit.cloud

Interesting Problem in Graph Theory


June 27, 2012

One of my homework problem for SYSM6302: Dynamics of Complex Networks and Systems, where we review basics of Graph Theory:

Here is a diagram of a prison for political dissidents. The prisoners have been divided into seven groups as shown. A spy plans to help all the prisoners escape by blowing up the gates in the prison walls. Due to the danger of this plan, he wants to destroy as few gates as possible and still allow all prisoners to escape. How many gates must be blasted to do this?

Image

The answer will be posted next week ;)

Written by Sigit Priyanggoro, Sr Global Partner Solutions Architect at Amazon Web Services in Dallas. LinkedIn.

Disclaimer

Any views or opinions expressed here are strictly my own. While I work for Amazon Web Services (AWS), this blog is not my job for AWS. I am solely responsible for all content published here. This is a personal exploration blog, not a corporate blog. Content published here is not read, reviewed, or approved in advance by my employer and does not necessarily represent or reflect the views or opinions of my employer or any of its divisions, subsidiaries, or business partners.