Definition of Graph
The network G = (V, E, C) is a Directed Acyclic Graph (DAG), V is the set of vectors and E is the set of edges. For each directed edge <i,j>∊E there is a positive integer capability Ci,j∊C. The source node, in which information is generated, is denoted by s and the target node, also called sink node or receiver node, is denoted by t. The set of all the incoming edges of one node u (u∊V) is in(u) and all the outgoing edges of node u is out(u).
Min-Cut and Max-Flow
A flow F of the network is a set of positive values for each edge <i,j> which satisfies:
0≤ Fi,j ≤ Ci,j, <i,j>∊E (1)
For every node except s and t, the incoming flow is same as the outgoing flow as described below:
(2)
The outgoing flow of the source node s is same as the incoming flow of the sink node t. And this value is defined as the total value of the flow F.
(3)
A max-flow is a flow F with the maximum total value |F| than any other flow over the network.
The cut set U is a subset of node set V such that the source node s∊U and the target node t∉U. The edges across the cut set U could be represented as:
EU={∊E : ∊out(u)∩ in(v), u∊U, v∊V} (4)
The capacity of the cut set U is the total capacity of edges in EU
(5)
Similarly as max-flow, the cut set C with minimum |C| in one network is called min-cut. Intuitively, the min-cut is the bottleneck between node s and node t, and any max-flow could not exceed the min-cut.
There is an example network shown in Figure 5.(a), the source node is s and the sink nodes are , the capacity Ci,j of each edge <i,j> is marked besides it.
![](data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKYAAABZCAYAAAC0TF+7AAAACXBIWXMAAA7NAAAOwAHWSJrXAAAJSUlEQVR4nO2dT0gVWxzHzzX7BxHiSnyLiBYZkRIimpsKw4gsW0lYD4I0K8sWbnr9wSwowtpkLkwjqoebglJeBVGLikwRe/nc2MqV4srFIzKz9+67v3n8hjNz50wz986c85u55wMxc86c2/nOud97zoxzzm/yk8kkixvFxcWzKYrz8vL+TZGH+Xway8jWMDIyUlVdXT0MeWFrcNMF+4WFhfMpCvEYplXospOvsvJc5NatW22qNSAtLS29bmmVxNKYnZ2dHdBTwT72WPY0lFGhYfny5Utr1679G/Z7e3tbwtQg0oWaysvLx69du/Yb6sR02G3jhVgas7m5uQ/+8Xn8cIplVGtQAWritchuGy+QNWZqWDEvflM9SyLXdfBQ1IQEpY2cMfHEurq60vJkfglUdNjrpqSJJ+j2ImVMOJErV64Y+wUFBcZ2bm6OYZ6sL4HX8e3bN1ZUVMRqa2vZgwcPpOpw0gNcunSJdXd3s5mZGUvbqDKnvb327NnDNmzYwG7fvm0eh62bPrzOBeDSgowxQfy5c+fYwsKCkZ6enmbr16830wAcx7JhfQl2HailrKzMzJOhw03P3bt32ZMnT9LaRoU5nfTl5+ezZ8+emb1nJu1FxpjA169fPeWp0NHQ0KBEC2Cv98ePH+zy5cvs/v37SvTYsetrb2+HGyhf7ZVIJJKp3nbVypUrFyFNwpjwSzp+/LgxDCDl5eXGdvPmzWx8fNxSHsqG0Ts46UAtmzZtYidOnAiyuoz17Ny50+jF7flhtYtffYcOHWJHjhxJy3ejpqbmNZoShnUSxgTsJ/H+/XvhMZk6eC0ydSBOdZ4/f154TDZOGt6+fSs8JuLly5e1fJqsMVVBRQdCTY+dsPSRMCYMPTAs7N+/31P5oaGhUO6I/eoIGyrtIiLM9iJhTIS/s1MJFR0INT12wtBHxpj469u2bZuwzIcPH8yycdfhRw9qUvF3zLDai4wxATxJ2Me7cgDvymU1PBUdP9OjUhNPGO1FypgAnoTq58FUdLjp4fNVE3R7kTMmQq3BqUBNj52g9JE1pia3ERqzrw+mEzb3wV/h6+rq/hgaGjL+JoAP2+FBO5aRJZYafBtVVVWNDA8PV0M+n1bVRpS1eUFozI6Ojk4QDQaEtSCYz88GxzIyhFIEz39mZuaXLVu2TGI+n1bVRpS1ecHTUE5pLQhF4As+fPjw76K0Sihrc0NoTNHaEJyGL2PdDHXw/Pv7+5tge/PmzXZY04PHIa2qjShr84LQmG5rQ3BLdRiQBeX1M5S1eUHflWtIoo2pIYk2poYk2pgakmhjakhC2phRf3qhyRzSxoz60wtN5pA2JhLVpxeazCFtzKg/vdBkDmljRv3phegaGaisrBxNUamvkZ0xjLl169Y/JyYmyiiEyYsTomtkiCo8NjZWwZdRp5ImhjGbmpr67QvONcFhvyamFFWYKoYxT58+3V1RUTGmWkzcEF0jq44qHAUMY+ohPB37oi8er+tavFwjB6HHj6aoQPrmRxVgguvXr1vydu3axV69emUelx1EltdTWPj/iybm5+ctZeJkTm1MAXxMHlgf/fHjRzMvNURLNwKvZ3Z2Fl6LQj6uUTa4GpPKmmqZwDmfPXvWEvbkzp07xpbPgzKyArfa9SAq9MjC0ZhoyNTFelpeXE7cCTjHtra2tICjL168YGvWrDHCN09OTgo+HR6iAKhfvnyBeQNmGrTHxZxpxuTjaUODQLBSOPmenh7zeBxOXITT8Iixd0THwwLa+tixY451jo2Nse/fv0vTIhuLMZ3iaUNvkUgkLPHH42xOatdt1PTIIq3HFDVErjQQtfOkpkcWpjGhFzx58mRaQ+zYscMYyvl8KBfHXhOjlu3du1e1FAO/euBNEXH5Tiw9ptNF9sWLF4XH4gq1XoqaHhlYjJmLDWAHe6nKykphmdHRUbMsBT2oyY8enNXU2Ng4sGzZsn8ePnz4K+RTWR1gGhMb4MCBAz/90NOnT2MzZDiRC4FbcVbT4OBgPbxjB/OprA5Iu/mhHu9bFmEGbs2kt5IVuJXK6gCLMb3G045zb2knjHPNprcKSg/OfKqvrx+EHwfs8+9zVL06IK3HpDaM5RIyeys0/cDAQCPmUVod4PhIklr8cR63Jb0YYJb6cgXqvRUFXCdxUDEjj2i5Ah9glvpyBeq9FQUiO+3NadjTAWbjQ+SM6bakFwPM5vowGAciZ8yoL+nVeCNyxtTkBtqYGpJoY2pIoo2pIYk2poYk2pgakmhjakiijakhiW9jRmEShdt8xzA1qqo3apq84NuYUZhEIZrvGLZGVfVS0hTUROaMh/KoTqJQpZFi2wSliTdjd3e34zG/BvVtTFmTKLKZC+o239GrxkzqD6JeL/jRFrYm0NLV1cUKCgqMNOwDR48eZan6zLhPXpZ749udYevbmGFPoggiblI28x2zqT/MeZa8Gf1oC1sThBOC1bVzc3OsqKjIXGn7/PlzI4ILpqGcV3PCZSKpu3J73CQ4UVjeAQv58Thsw5rA7FQ/AI2Ox1VMnuZ1ARgA4dGjRwzzVcTsvHDhAltcXLTkYzqZTFrSAJR30wnXwCkjr2ptbe0hY0ynuEmwVnr37t2WuElYNugvwal+YHp6WmncJiddnz59ssSTUqWNj0OwceNGY7tu3Tr2+fNnVlNTYwzlfmIVpD7zevXq1QvQo5MxJmA/iRs3brB9+/ZJC8TgVE9dXR17/PixlPpF2HUdPHjQMV8W8AM4deqUpf6JiQlzH/KvXr1q7vPA50Q/IP4FFSSMKYqbBEMVcObMGePXhwQdO0lUP7BixQplcZtEut69e2f0mHCMR6a2sEMgkjAm4BaXcmlpyfinqn6VoXOc6r53757wmCzCrpuMMVUH7VJdvwiKujD2QENDQ2h1kDCmn7hJQNCxk6jGbVLdLj8jk+Hcq0YSxkRUx01SXb+IXNRFxphe4yZhWVX1q4r05qYLkK0NdW3fvt1T+Tdv3pif81KejDEB1XGTVNfvVxegUhuvC6ioqLAchxcY8GX9/N+kjAmojpukun4RssIQ+oWvP0ht5IyJUGpwSlDVBQSpjawxNbmNNqaGJNqYWcIvNcHpZBSXKkQNbcws4ZcllJaW/pWiVPXSkjigjRkgU1NTJao1xAVtzCzhlyWUlJRM2fM0maGNmSVOS030MJ49/wGOzHxa4gQ/3AAAAABJRU5ErkJggg==)
Two sink nodes network with two max-flow examples
The max-flow F1 from s to t1 could be worked out with any one of the algorithms discussed in Section III (A). The result is shown in Figure 5. 1 (b). The actual flow values and the capacity limitation are indicated as a pair in the form of “(Fi,j ,Ci,j)”. The edges with no flow (Fi,j=0) are marked with dash lines in the graph. The flows are: 1 unit along path 0-1-3-6-9; 2 units along path 0-1-4-6-9, 2 units along path 0-2-4-7-9. Total flow value is 5.
Similarly, the max-flow F2 from s to t2 is shown in Figure 5.(c). The flows are: 1 unit along path 0-2-5-8-10; 2 units along path 0-2-4-8-10, 2 units along path 0-1-4-7-10. Total flow value is 5. All the edges shared by both flow are marked with bold lines.
Share with your friends: |