MA010 Graph Theory (an online guide)

Interactive demonstrations (need java)

Network flow - an interactive animation  (change the capacities as you like)

<p>Imagine a connection network between various points. The connections could be streets while the connection points specific sites or crossroads; or, the connections can be water or gas pipelines, while the sites/points can be the places the pipelines connect; or, one may consider electricity network, information capacity network, etc. The maximal flow problem is the following: given a start and finish points in a network, which is the maximal flow of units the network is able to pass through (entering the start point and exiting the finish point). </p> <p>Each network connection may have different capacity. The demo allows you to change their values. A zero capacity value means there is no connection between the points. </p> <p>On the right side of the network a maximal flow value is calculated. Utilization of the whole network is calculated as well. </p> <p>E.g., considering a city traffic example, the problem becomes even more interesting if some of the streets needs to be closed or its capacity reduced (e.g., due to traffic accident or maintenance work). The model instantly gives a new solution in order to have a maximum flow (maximum transit capacity) between the start and the finish nodes. </p> <p>Although this demo does not allow one to change the network structure, the problem is solved in a way that any network structure can be accommodated and any network structure change does not increase the cost of the maximal flow solution. </p> <p><em>Your browser does not support the applet tag.</em></p>
Previous
Next