Interesting Problem in Graph Theory

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😉

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