Flow Nets

Directed Graph can be interpreted as Flow Net and used to find answers to questions regarding movement of "something" in such net. Let's imagine material circulating in given system from source, where it is produced, to outflow, where it's used. Source creates material with constant speed, and with same speed it is used in outflow. Intuitively, in each point (node) of this system, "flow" equals speed, with which material moves through this point. Flow nets may be used to model flow of fluid in pipelines, manufactured parts, electricity in circuits, information in communication networks and so on.

Each directed edge in net may be interpreted as channel, through which something flows. Each channel has given throughput, that determines maximum speed with which flow occurs in this channel (for example: 1000 liters of fluid per hour in pipeline). Nodes different from source and outflow are points, where channels converge. Flow occurs only through these nodes, and is not stopped in them. Speed of arriving in node must be same as speed of leaving it. This property is called "flow preservation".

No comments:

Post a Comment