3144:
3127:
2897:
2807:
3158:
6446:
2529:
answer will be correct if the algorithm terminates. In the case that the algorithm runs forever, the flow might not even converge towards the maximum flow. However, this situation only occurs with irrational flow values. When the capacities are integers, the runtime of Ford–Fulkerson is bounded by
2528:
By adding the flow augmenting path to the flow already established in the graph, the maximum flow will be reached when no more flow augmenting paths can be found in the graph. However, there is no certainty that this situation will ever be reached, so the best that can be guaranteed is that the
60:
The idea behind the algorithm is as follows: as long as there is a path from the source (start node) to the sink (end node), with available capacity on all edges in the path, we send flow along one of the paths. Then we find another path, and so on. A path with available capacity is called an
45:. It is sometimes called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times. It was published in 1956 by
509:
630:
5107:
2518:
2296:
2073:
2443:
1372:
288:
3555:
2384:
989:
386:
1850:
1807:
1575:
1491:
3723:
3639:
788:
5381:
3974:
3353:
1113:
4870:
4510:
4187:
5033:
1234:
1683:
704:
5232:
837:
1412:
1272:
3458:
2718:
2139:
1916:
878:
5285:
5189:
4822:
3868:
3399:
2940:
2850:
1041:
5331:
2165:
1969:
1764:
184:
149:
106:
4978:
4951:
4924:
4897:
4789:
4762:
4735:
4708:
4655:
4627:
4599:
4571:
4538:
4435:
4407:
4353:
4325:
4297:
4269:
4236:
4133:
4105:
4051:
4023:
3825:
3797:
3769:
3283:
3256:
3229:
2559:
2331:
2192:
2100:
1943:
1877:
1186:
1145:
5136:
2632:
416:
5252:
5156:
4842:
4676:
4456:
4374:
4208:
4072:
3995:
3910:
3889:
3419:
3373:
3303:
3202:
3182:
3120:
3100:
3080:
3060:
3040:
3020:
3000:
2980:
2960:
2890:
2870:
2786:
2766:
2746:
2672:
2652:
2603:
2583:
6120:
6450:
2677:
A variation of the Ford–Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the
4980:
infinitely many times and residual capacities of these edges will always be in the same form. Total flow in the network after step 5 is
523:
5038:
2448:
6248:
2197:
1974:
6330:
1724:, and on the other hand serves as an upper bound for all such flows. This proves that the flow we found is maximal. See also
2389:
1280:
207:
6057:
3463:
2336:
883:
302:
1812:
6151:
6104:
1769:
1502:
1418:
6364:
6307:
3644:
3560:
513:
The net flow to a node is zero, except for the source, which "produces" flow, and the sink, which "consumes" flow.
6428:
6183:
6438:
709:
6465:
1594:
6175:
5340:
3921:
3308:
1077:
6298:
4847:
4462:
4139:
2788:
is sent across the network. If breadth-first-search were used instead, only two steps would be needed.
2678:
1686:
54:
4983:
6470:
5298:, where they also show that the worst case running-time of the Ford-Fulkerson algorithm on a network
5287:. Therefore, the algorithm never terminates and the flow does not even converge to the maximum flow.
2728:
The following example shows the first steps of Ford–Fulkerson in a flow network with 4 nodes, source
1191:
6224:
1639:
660:
6143:
6062:
1725:
6133:
5194:
801:
6244:"The smallest networks on which the Ford–Fulkerson maximum flow procedure may fail to terminate"
1379:
1239:
6356:
6348:
6219:
6096:
3424:
2684:
2105:
1882:
6433:
6317:
George T. Heineman; Gary
Pollice; Stanley Selkow (2008). "Chapter 8:Network Flow Algorithms".
842:
5257:
5161:
4794:
3840:
3378:
2907:
2817:
2768:. This example shows the worst-case behaviour of the algorithm. In each step, only a flow of
1008:
504:{\displaystyle \forall u\in V:u\neq s{\text{ and }}u\neq t\Rightarrow \sum _{w\in V}f(u,w)=0}
6135:
6088:
5301:
2144:
1948:
1734:
154:
119:
76:
6285:
6067:
4956:
4929:
4902:
4875:
4767:
4740:
4713:
4686:
4633:
4605:
4577:
4549:
4516:
4413:
4385:
4331:
4303:
4275:
4247:
4214:
4111:
4083:
4029:
4001:
3803:
3775:
3747:
3261:
3234:
3207:
2532:
2309:
2170:
2078:
1921:
1855:
1629:
1164:
1118:
38:
5112:
2608:
8:
6136:
5291:
6383:
Backman, Spencer; Huynh, Tony (2018). "Transfinite Ford–Fulkerson on a finite network".
2605:
is the maximum flow in the graph. This is because each augmenting path can be found in
6410:
6392:
6200:
6114:
6086:
6052:
5237:
5141:
4827:
4661:
4441:
4359:
4193:
4057:
3980:
3895:
3874:
3404:
3358:
3288:
3187:
3167:
3105:
3085:
3065:
3045:
3025:
3005:
2985:
2965:
2945:
2875:
2855:
2771:
2751:
2731:
2657:
2637:
2588:
2568:
1708:
in the residual network, then the total capacity in the original network of edges from
1633:
6360:
6326:
6303:
6262:
6243:
6147:
6100:
6089:
6414:
6204:
6402:
6289:
6281:
6257:
6192:
34:
798:
is allowed in the residual network, though disallowed in the original network: if
6171:
6134:
Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2009).
5334:
4683:
Note that after step 1 as well as after step 5, the residual capacities of edges
62:
50:
6293:
6167:
5035:. If we continue to use augmenting paths as above, the total flow converges to
3143:
2562:
46:
57:, which is a fully defined implementation of the Ford–Fulkerson method.
6459:
6429:
A tutorial explaining the Ford–Fulkerson method to solve the max-flow problem
6340:
6322:
6344:
6316:
6196:
3126:
2896:
2806:
42:
3157:
6406:
6302:(Second ed.). MIT Press and McGraw–Hill. pp. 651–664.
5386:
6239:
3122:
edge is left with zero flow, but the overall flow increases by one.
6397:
3460:. We use augmenting paths according to the following table, where
625:{\displaystyle \sum _{(s,u)\in E}f(s,u)=\sum _{(v,t)\in E}f(v,t)}
194:. After every step in the algorithm the following is maintained:
6087:
Laung-Terng Wang, Yao-Wen Chang, Kwang-Ting (Tim) Cheng (2009).
1766:
has multiple sources and sinks, we act as follows: Suppose that
6445:
6091:
Electronic Design
Automation: Synthesis, Verification, and Test
186:
be the flow. We want to find the maximum flow from the source
5747:# If we reached sink in BFS starting from source, then return
5102:{\displaystyle \textstyle 1+2\sum _{i=1}^{\infty }r^{i}=3+2r}
2634:
time and increases the flow by an integer amount of at least
2513:{\displaystyle c(u_{\mathrm {in} },u_{\mathrm {out} })=d_{u}}
53:. The name "Ford–Fulkerson" is often also used for the
5960:# update residual capacities of the edges and reverse edges
1622:" terminates the algorithm and outputs the following value.
6280:
5822:# Augment the flow while there is path from source to sink
3164:
Consider the flow network shown on the right, with source
6296:(2001). "Section 26.2: The Ford–Fulkerson method".
5861:# path filled by BFS. Or we can say find the maximum flow
5759:# Returns the maximum flow from s to t in the given graph
5522:
source 's' to sink 't' in residual graph.
3139:
The final flow network, with a total flow of 2000 units.
2904:
Here, one unit of flow is sent along the augmenting path
2291:{\displaystyle c(t,t^{*})=d_{t}=\sum _{(v,t)\in E}c(v,t)}
2068:{\displaystyle c(s^{*},s)=d_{s}=\sum _{(s,u)\in E}c(s,u)}
1716:
is on the one hand equal to the total flow we found from
790:
and no flow. Notice that it can happen that a flow from
6339:
5858:# Find minimum residual capacity of the edges along the
5042:
2438:{\displaystyle (u_{\mathrm {in} },u_{\mathrm {out} })}
1367:{\displaystyle c_{f}(p)=\min\{c_{f}(u,v):(u,v)\in p\}}
283:{\displaystyle \forall (u,v)\in E:\ f(u,v)\leq c(u,v)}
5343:
5304:
5260:
5240:
5197:
5164:
5144:
5115:
5041:
4986:
4959:
4932:
4905:
4878:
4850:
4830:
4797:
4770:
4743:
4716:
4689:
4664:
4636:
4608:
4580:
4552:
4519:
4465:
4444:
4416:
4388:
4362:
4334:
4306:
4278:
4250:
4217:
4196:
4142:
4114:
4086:
4060:
4032:
4004:
3983:
3924:
3898:
3877:
3843:
3806:
3778:
3750:
3647:
3563:
3550:{\displaystyle p_{1}=\{s,v_{4},v_{3},v_{2},v_{1},t\}}
3466:
3427:
3407:
3381:
3361:
3311:
3291:
3264:
3237:
3210:
3190:
3170:
3108:
3088:
3068:
3048:
3028:
3008:
2988:
2968:
2948:
2910:
2878:
2858:
2820:
2774:
2754:
2734:
2687:
2660:
2640:
2611:
2591:
2571:
2535:
2451:
2392:
2339:
2312:
2200:
2173:
2147:
2108:
2081:
1977:
1951:
1924:
1885:
1858:
1815:
1772:
1737:
1642:
1505:
1421:
1382:
1283:
1242:
1194:
1167:
1121:
1080:
1011:
886:
845:
804:
712:
663:
526:
419:
305:
210:
157:
122:
79:
6218:"Ford-Fulkerson Max Flow Labeling Algorithm". 1998.
5633:# Get all adjacent vertices of the dequeued vertex u
2379:{\displaystyle u_{\mathrm {in} },u_{\mathrm {out} }}
984:{\displaystyle c_{f}(v,u)=c(v,u)-f(v,u)=f(u,v)>0}
5636:# If an adjacent has not been visited, then mark it
5387:
Python implementation of the
Edmonds–Karp algorithm
1628:The path in step 2 can be found with, for example,
381:{\displaystyle \forall (u,v)\in E:\ f(u,v)=-f(v,u)}
292:The flow along an edge cannot exceed its capacity.
6349:"Chapter 7:Extensions to the Maximum-Flow Problem"
5375:
5325:
5279:
5246:
5226:
5183:
5150:
5130:
5101:
5027:
4972:
4945:
4918:
4891:
4864:
4836:
4816:
4783:
4756:
4729:
4702:
4670:
4649:
4621:
4593:
4565:
4532:
4504:
4450:
4429:
4401:
4368:
4347:
4319:
4291:
4263:
4230:
4202:
4181:
4127:
4099:
4066:
4045:
4017:
3989:
3968:
3904:
3883:
3862:
3819:
3791:
3763:
3717:
3633:
3549:
3452:
3413:
3393:
3367:
3347:
3297:
3277:
3250:
3223:
3196:
3176:
3114:
3094:
3074:
3054:
3034:
3014:
2994:
2974:
2954:
2934:
2884:
2864:
2844:
2780:
2760:
2740:
2712:
2666:
2646:
2626:
2597:
2577:
2553:
2512:
2437:
2378:
2325:
2290:
2186:
2159:
2133:
2094:
2067:
1963:
1937:
1910:
1871:
1845:{\displaystyle S=\{s\mid s{\text{ is a source}}\}}
1844:
1801:
1758:
1677:
1569:
1485:
1406:
1366:
1266:
1228:
1180:
1139:
1107:
1035:
983:
872:
831:
782:
698:
650:This means that the flow through the network is a
624:
503:
380:
282:
178:
143:
100:
18:Algorithm to compute the maximum flow in a network
3375:and the capacity of all other edges some integer
2520:. Then apply the Ford–Fulkerson algorithm.
2298:. Then apply the Ford–Fulkerson algorithm.
654:after each round in the algorithm. We define the
6457:
6373:
5573:# Mark the source node as visited and enqueue it
1802:{\displaystyle T=\{t\mid t{\text{ is a sink}}\}}
1570:{\displaystyle f(v,u)\leftarrow f(v,u)-c_{f}(p)}
1486:{\displaystyle f(u,v)\leftarrow f(u,v)+c_{f}(p)}
1306:
5789:# This array is filled by BFS and to store path
5109:. However, note that there is a flow of value
3718:{\displaystyle p_{3}=\{s,v_{1},v_{2},v_{3},t\}}
3634:{\displaystyle p_{2}=\{s,v_{2},v_{3},v_{4},t\}}
4872:. This means that we can use augmenting paths
6166:
5290:Another non-terminating example based on the
6382:
6119:: CS1 maint: multiple names: authors list (
5411:This class represents a directed graph using
5295:
3963:
3925:
3712:
3661:
3628:
3577:
3544:
3480:
2892:edge, so only one unit of flow is possible.
1839:
1822:
1796:
1779:
1361:
1309:
2942:. In this case, flow is "pushed back" from
1692:When no more paths in step 2 can be found,
3152:
3134:1998 intermediate steps are omitted here.
398:must be the opposite of the net flow from
6396:
6261:
6223:
4858:
2585:is the number of edges in the graph and
783:{\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}
2814:Flow is sent along the augmenting path
2723:
6458:
5531:# Mark all the vertices as not visited
5376:{\displaystyle \omega ^{\Theta (|E|)}}
2333:, we replace this node with two nodes
638:must be equal to the flow arriving at
6238:
6058:Approximate max-flow min-cut theorem
5525:Also fills parent to store the path.
5519:Returns true if there is a path from
3969:{\displaystyle \{s,v_{2},v_{3},t\}}
3348:{\displaystyle r=({\sqrt {5}}-1)/2}
108:be a graph, and for each edge from
13:
5349:
5068:
3156:
2488:
2485:
2482:
2467:
2464:
2426:
2423:
2420:
2405:
2402:
2370:
2367:
2364:
2349:
2346:
1579:The flow might be "returned" later
1108:{\displaystyle f(u,v)\leftarrow 0}
420:
306:
211:
14:
6482:
6422:
4865:{\displaystyle n\in \mathbb {N} }
4505:{\displaystyle r^{1}-r^{2}=r^{3}}
4182:{\displaystyle r^{0}-r^{1}=r^{2}}
2790:
1704:is the set of nodes reachable by
6444:
6176:"Maximal flow through a network"
5414:adjacency matrix representation.
5028:{\displaystyle 1+2(r^{1}+r^{2})}
3142:
3125:
2895:
2805:
706:to be the network with capacity
6184:Canadian Journal of Mathematics
5948:# Add path flow to overall flow
1229:{\displaystyle c_{f}(u,v)>0}
6355:. Pearson Education. pp.
6232:
6211:
6160:
6127:
6080:
5368:
5364:
5356:
5352:
5320:
5308:
5022:
4996:
3334:
3318:
2852:. Here, the bottleneck is the
2707:
2691:
2621:
2615:
2548:
2539:
2494:
2455:
2432:
2393:
2285:
2273:
2259:
2247:
2223:
2204:
2128:
2109:
2062:
2050:
2036:
2024:
2000:
1981:
1905:
1886:
1753:
1741:
1678:{\displaystyle G_{f}(V,E_{f})}
1672:
1653:
1564:
1558:
1542:
1530:
1524:
1521:
1509:
1480:
1474:
1458:
1446:
1440:
1437:
1425:
1395:
1383:
1352:
1340:
1334:
1322:
1300:
1294:
1255:
1243:
1217:
1205:
1134:
1122:
1099:
1096:
1084:
1030:
1018:
972:
960:
951:
939:
930:
918:
909:
897:
861:
849:
820:
808:
777:
765:
756:
744:
735:
723:
699:{\displaystyle G_{f}(V,E_{f})}
693:
674:
619:
607:
593:
581:
570:
558:
544:
532:
492:
480:
458:
375:
363:
351:
339:
321:
309:
277:
265:
256:
244:
226:
214:
173:
161:
138:
126:
95:
83:
1:
6274:
2523:
1685:. The former is known as the
6263:10.1016/0304-3975(95)00022-O
6249:Theoretical Computer Science
6095:. Morgan Kaufmann. pp.
5819:# There is no flow initially
5227:{\displaystyle sv_{2}v_{3}t}
3062:is now free to send flow to
1700:in the residual network. If
68:
7:
6046:
3082:directly. As a result, the
832:{\displaystyle f(u,v)>0}
10:
6487:
6451:Ford-Fulkerson's algorithm
6439:Java Web Start application
6299:Introduction to Algorithms
6138:Introduction to Algorithms
5296:Backman & Huynh (2018)
3002:that originally came from
1696:will not be able to reach
1605:" means that the value of
1407:{\displaystyle (u,v)\in p}
1267:{\displaystyle (u,v)\in p}
6374:Samuel Gutekunst (2019).
5864:# through the path found.
4844:, respectively, for some
3739:
3736:
3733:
3730:
3453:{\displaystyle r^{2}=1-r}
3133:
2713:{\displaystyle O(VE^{2})}
2134:{\displaystyle (t,t^{*})}
1911:{\displaystyle (s^{*},s)}
6319:Algorithms in a Nutshell
6073:
6063:Turn restriction routing
5639:# visited and enqueue it
5552:# Create a queue for BFS
5390:
2306:has capacity constraint
1726:Max-flow Min-cut theorem
1609:changes to the value of
1495:Send flow along the path
873:{\displaystyle c(v,u)=0}
27:Ford–Fulkerson algorithm
5280:{\displaystyle sv_{4}t}
5191:, 1 unit of flow along
5184:{\displaystyle sv_{1}t}
4817:{\displaystyle r^{n+1}}
3863:{\displaystyle r^{0}=1}
3394:{\displaystyle M\geq 2}
3153:Non-terminating example
2935:{\displaystyle A,C,B,D}
2845:{\displaystyle A,B,C,D}
2654:, with the upper bound
1036:{\displaystyle G=(V,E)}
6434:Another Java animation
6197:10.4153/CJM-1956-045-5
6142:. MIT Press. pp.
5377:
5327:
5326:{\displaystyle G(V,E)}
5281:
5248:
5228:
5185:
5152:
5132:
5103:
5072:
5029:
4974:
4947:
4920:
4893:
4866:
4838:
4818:
4785:
4758:
4731:
4704:
4672:
4651:
4623:
4595:
4567:
4534:
4506:
4452:
4431:
4403:
4370:
4349:
4321:
4293:
4265:
4232:
4204:
4183:
4129:
4101:
4068:
4047:
4019:
3991:
3970:
3906:
3885:
3864:
3821:
3793:
3765:
3719:
3635:
3551:
3454:
3415:
3395:
3369:
3349:
3299:
3279:
3252:
3225:
3204:, capacities of edges
3198:
3178:
3161:
3116:
3096:
3076:
3056:
3036:
3016:
2996:
2976:
2956:
2936:
2886:
2866:
2846:
2802:Initial flow network.
2782:
2762:
2742:
2714:
2679:Edmonds–Karp algorithm
2668:
2648:
2628:
2599:
2579:
2555:
2514:
2439:
2380:
2327:
2292:
2188:
2161:
2160:{\displaystyle t\in T}
2135:
2096:
2069:
1965:
1964:{\displaystyle s\in S}
1939:
1912:
1873:
1846:
1803:
1760:
1759:{\displaystyle G(V,E)}
1687:Edmonds–Karp algorithm
1679:
1571:
1487:
1408:
1368:
1268:
1230:
1182:
1149:While there is a path
1141:
1109:
1037:
985:
874:
833:
784:
700:
634:The flow leaving from
626:
505:
382:
284:
180:
179:{\displaystyle f(u,v)}
145:
144:{\displaystyle c(u,v)}
102:
101:{\displaystyle G(V,E)}
55:Edmonds–Karp algorithm
6453:at Wikimedia Commons
6378:. Cornell University.
6286:Leiserson, Charles E.
5378:
5328:
5282:
5249:
5229:
5186:
5153:
5133:
5104:
5052:
5030:
4975:
4973:{\displaystyle p_{3}}
4948:
4946:{\displaystyle p_{1}}
4921:
4919:{\displaystyle p_{2}}
4894:
4892:{\displaystyle p_{1}}
4867:
4839:
4819:
4786:
4784:{\displaystyle r^{n}}
4759:
4757:{\displaystyle e_{3}}
4732:
4730:{\displaystyle e_{2}}
4705:
4703:{\displaystyle e_{1}}
4673:
4652:
4650:{\displaystyle r^{3}}
4624:
4622:{\displaystyle r^{2}}
4596:
4594:{\displaystyle r^{2}}
4568:
4566:{\displaystyle p_{3}}
4535:
4533:{\displaystyle r^{2}}
4507:
4453:
4432:
4430:{\displaystyle r^{2}}
4404:
4402:{\displaystyle p_{1}}
4371:
4350:
4348:{\displaystyle r^{1}}
4322:
4320:{\displaystyle r^{2}}
4294:
4292:{\displaystyle r^{1}}
4266:
4264:{\displaystyle p_{2}}
4233:
4231:{\displaystyle r^{1}}
4205:
4184:
4130:
4128:{\displaystyle r^{1}}
4102:
4100:{\displaystyle p_{1}}
4069:
4048:
4046:{\displaystyle r^{1}}
4020:
4018:{\displaystyle r^{0}}
3992:
3971:
3907:
3886:
3865:
3822:
3820:{\displaystyle e_{3}}
3794:
3792:{\displaystyle e_{2}}
3766:
3764:{\displaystyle e_{1}}
3720:
3636:
3552:
3455:
3416:
3396:
3370:
3350:
3300:
3280:
3278:{\displaystyle e_{3}}
3253:
3251:{\displaystyle e_{2}}
3226:
3224:{\displaystyle e_{1}}
3199:
3179:
3160:
3117:
3097:
3077:
3057:
3037:
3017:
2997:
2977:
2957:
2937:
2887:
2867:
2847:
2783:
2763:
2743:
2715:
2669:
2649:
2629:
2600:
2580:
2556:
2554:{\displaystyle O(Ef)}
2515:
2440:
2381:
2328:
2326:{\displaystyle d_{u}}
2293:
2189:
2187:{\displaystyle t^{*}}
2162:
2136:
2097:
2095:{\displaystyle t^{*}}
2075:. And add a new sink
2070:
1966:
1940:
1938:{\displaystyle s^{*}}
1913:
1874:
1872:{\displaystyle s^{*}}
1847:
1804:
1761:
1680:
1572:
1488:
1409:
1369:
1269:
1231:
1183:
1181:{\displaystyle G_{f}}
1142:
1140:{\displaystyle (u,v)}
1110:
1038:
998:Ford–Fulkerson
986:
875:
834:
785:
701:
627:
506:
383:
285:
202:Capacity constraints
181:
146:
103:
23:Ford–Fulkerson method
6466:Network flow problem
6325:. pp. 226–250.
5341:
5302:
5258:
5254:units of flow along
5238:
5195:
5162:
5158:units of flow along
5142:
5131:{\displaystyle 2M+1}
5113:
5039:
4984:
4957:
4930:
4903:
4876:
4848:
4828:
4795:
4768:
4741:
4714:
4687:
4662:
4634:
4606:
4578:
4550:
4517:
4463:
4442:
4414:
4386:
4360:
4332:
4304:
4276:
4248:
4215:
4194:
4140:
4112:
4084:
4058:
4030:
4002:
3981:
3922:
3896:
3875:
3841:
3804:
3776:
3748:
3740:Residual capacities
3645:
3561:
3464:
3425:
3421:was chosen so, that
3405:
3379:
3359:
3309:
3289:
3262:
3235:
3208:
3188:
3168:
3106:
3086:
3066:
3046:
3026:
3006:
2986:
2966:
2946:
2908:
2876:
2856:
2818:
2772:
2752:
2732:
2724:Integer flow example
2685:
2658:
2638:
2627:{\displaystyle O(E)}
2609:
2589:
2569:
2533:
2449:
2390:
2337:
2310:
2198:
2171:
2145:
2106:
2079:
1975:
1949:
1922:
1883:
1856:
1813:
1770:
1735:
1712:to the remainder of
1640:
1630:breadth-first search
1503:
1419:
1380:
1281:
1240:
1192:
1165:
1119:
1078:
1009:
884:
843:
802:
710:
661:
524:
417:
303:
208:
155:
151:be the capacity and
120:
77:
5603:# Standard BFS loop
5292:Euclidean algorithm
1852:. Add a new source
1043:with flow capacity
6407:10.3233/COM-180082
6242:(21 August 1995).
5750:# true, else false
5528:"""
5516:"""
5417:"""
5408:"""
5373:
5323:
5277:
5244:
5224:
5181:
5148:
5128:
5099:
5098:
5025:
4970:
4943:
4916:
4889:
4862:
4834:
4814:
4781:
4754:
4727:
4700:
4668:
4647:
4619:
4591:
4563:
4530:
4502:
4448:
4427:
4399:
4366:
4345:
4317:
4289:
4261:
4228:
4200:
4179:
4125:
4097:
4064:
4043:
4015:
3987:
3966:
3902:
3881:
3860:
3817:
3789:
3761:
3715:
3631:
3547:
3450:
3411:
3391:
3365:
3345:
3295:
3275:
3248:
3221:
3194:
3174:
3162:
3112:
3092:
3072:
3052:
3032:
3012:
2992:
2972:
2952:
2932:
2882:
2862:
2842:
2778:
2758:
2738:
2710:
2664:
2644:
2624:
2595:
2575:
2551:
2510:
2435:
2376:
2323:
2288:
2269:
2184:
2157:
2131:
2092:
2065:
2046:
1961:
1935:
1908:
1869:
1842:
1799:
1756:
1675:
1634:depth-first search
1597:. For instance, "
1593:"←" denotes
1567:
1483:
1404:
1364:
1264:
1226:
1178:
1137:
1105:
1051:, and a sink node
1033:
981:
870:
829:
780:
696:
622:
603:
554:
501:
476:
411:Flow conservation
390:The net flow from
378:
280:
176:
141:
98:
37:that computes the
6449:Media related to
6332:978-0-596-51624-6
6290:Rivest, Ronald L.
6282:Cormen, Thomas H.
6068:Dinic's algorithm
5247:{\displaystyle M}
5151:{\displaystyle M}
4837:{\displaystyle 0}
4681:
4680:
4671:{\displaystyle 0}
4451:{\displaystyle 0}
4369:{\displaystyle 0}
4203:{\displaystyle 0}
4067:{\displaystyle 0}
3990:{\displaystyle 1}
3905:{\displaystyle 1}
3884:{\displaystyle r}
3414:{\displaystyle r}
3368:{\displaystyle 1}
3326:
3298:{\displaystyle 1}
3197:{\displaystyle t}
3177:{\displaystyle s}
3150:
3149:
3115:{\displaystyle C}
3095:{\displaystyle B}
3075:{\displaystyle D}
3055:{\displaystyle B}
3035:{\displaystyle A}
3015:{\displaystyle B}
2995:{\displaystyle C}
2975:{\displaystyle B}
2955:{\displaystyle C}
2885:{\displaystyle C}
2865:{\displaystyle B}
2781:{\displaystyle 1}
2761:{\displaystyle D}
2741:{\displaystyle A}
2667:{\displaystyle f}
2647:{\displaystyle 1}
2598:{\displaystyle f}
2578:{\displaystyle E}
2242:
2019:
1837:
1836: is a source
1794:
1623:
1614:
1072:of maximum value
646:
645:
576:
527:
461:
447:
335:
240:
6478:
6471:Graph algorithms
6448:
6418:
6400:
6379:
6370:
6353:Algorithm Design
6336:
6313:
6268:
6267:
6265:
6236:
6230:
6229:
6227:
6215:
6209:
6208:
6180:
6172:Fulkerson, D. R.
6164:
6158:
6157:
6141:
6131:
6125:
6124:
6118:
6110:
6094:
6084:
6042:
6039:
6036:
6033:
6030:
6027:
6024:
6021:
6018:
6015:
6012:
6009:
6006:
6003:
6000:
5997:
5994:
5991:
5988:
5985:
5982:
5979:
5976:
5973:
5970:
5967:
5964:
5963:# along the path
5961:
5958:
5955:
5952:
5949:
5946:
5943:
5940:
5937:
5934:
5931:
5928:
5925:
5922:
5919:
5916:
5913:
5910:
5907:
5904:
5901:
5898:
5895:
5892:
5889:
5886:
5883:
5880:
5877:
5874:
5871:
5868:
5865:
5862:
5859:
5856:
5853:
5850:
5847:
5844:
5841:
5838:
5835:
5832:
5829:
5826:
5823:
5820:
5817:
5814:
5811:
5808:
5805:
5802:
5799:
5796:
5793:
5790:
5787:
5784:
5781:
5778:
5775:
5772:
5769:
5766:
5763:
5760:
5757:
5754:
5751:
5748:
5745:
5742:
5739:
5736:
5733:
5730:
5727:
5724:
5721:
5718:
5715:
5712:
5709:
5706:
5703:
5700:
5697:
5694:
5691:
5688:
5685:
5682:
5679:
5676:
5673:
5670:
5667:
5664:
5661:
5658:
5655:
5652:
5649:
5646:
5643:
5640:
5637:
5634:
5631:
5628:
5625:
5622:
5619:
5616:
5613:
5610:
5607:
5604:
5601:
5598:
5595:
5592:
5589:
5586:
5583:
5580:
5577:
5574:
5571:
5568:
5565:
5562:
5559:
5556:
5553:
5550:
5547:
5544:
5541:
5538:
5535:
5532:
5529:
5526:
5523:
5520:
5517:
5514:
5511:
5508:
5505:
5502:
5499:
5496:
5493:
5490:
5487:
5484:
5481:
5478:
5475:
5472:
5469:
5466:
5463:
5460:
5457:
5456:# residual graph
5454:
5451:
5448:
5445:
5442:
5439:
5436:
5433:
5430:
5427:
5424:
5421:
5418:
5415:
5412:
5409:
5406:
5403:
5400:
5397:
5394:
5382:
5380:
5379:
5374:
5372:
5371:
5367:
5359:
5332:
5330:
5329:
5324:
5286:
5284:
5283:
5278:
5273:
5272:
5253:
5251:
5250:
5245:
5233:
5231:
5230:
5225:
5220:
5219:
5210:
5209:
5190:
5188:
5187:
5182:
5177:
5176:
5157:
5155:
5154:
5149:
5137:
5135:
5134:
5129:
5108:
5106:
5105:
5100:
5082:
5081:
5071:
5066:
5034:
5032:
5031:
5026:
5021:
5020:
5008:
5007:
4979:
4977:
4976:
4971:
4969:
4968:
4952:
4950:
4949:
4944:
4942:
4941:
4925:
4923:
4922:
4917:
4915:
4914:
4898:
4896:
4895:
4890:
4888:
4887:
4871:
4869:
4868:
4863:
4861:
4843:
4841:
4840:
4835:
4823:
4821:
4820:
4815:
4813:
4812:
4790:
4788:
4787:
4782:
4780:
4779:
4764:are in the form
4763:
4761:
4760:
4755:
4753:
4752:
4736:
4734:
4733:
4728:
4726:
4725:
4709:
4707:
4706:
4701:
4699:
4698:
4677:
4675:
4674:
4669:
4656:
4654:
4653:
4648:
4646:
4645:
4628:
4626:
4625:
4620:
4618:
4617:
4600:
4598:
4597:
4592:
4590:
4589:
4572:
4570:
4569:
4564:
4562:
4561:
4539:
4537:
4536:
4531:
4529:
4528:
4511:
4509:
4508:
4503:
4501:
4500:
4488:
4487:
4475:
4474:
4457:
4455:
4454:
4449:
4436:
4434:
4433:
4428:
4426:
4425:
4408:
4406:
4405:
4400:
4398:
4397:
4375:
4373:
4372:
4367:
4354:
4352:
4351:
4346:
4344:
4343:
4326:
4324:
4323:
4318:
4316:
4315:
4298:
4296:
4295:
4290:
4288:
4287:
4270:
4268:
4267:
4262:
4260:
4259:
4237:
4235:
4234:
4229:
4227:
4226:
4209:
4207:
4206:
4201:
4188:
4186:
4185:
4180:
4178:
4177:
4165:
4164:
4152:
4151:
4134:
4132:
4131:
4126:
4124:
4123:
4106:
4104:
4103:
4098:
4096:
4095:
4073:
4071:
4070:
4065:
4052:
4050:
4049:
4044:
4042:
4041:
4024:
4022:
4021:
4016:
4014:
4013:
3996:
3994:
3993:
3988:
3975:
3973:
3972:
3967:
3956:
3955:
3943:
3942:
3911:
3909:
3908:
3903:
3890:
3888:
3887:
3882:
3869:
3867:
3866:
3861:
3853:
3852:
3826:
3824:
3823:
3818:
3816:
3815:
3798:
3796:
3795:
3790:
3788:
3787:
3770:
3768:
3767:
3762:
3760:
3759:
3728:
3727:
3724:
3722:
3721:
3716:
3705:
3704:
3692:
3691:
3679:
3678:
3657:
3656:
3640:
3638:
3637:
3632:
3621:
3620:
3608:
3607:
3595:
3594:
3573:
3572:
3556:
3554:
3553:
3548:
3537:
3536:
3524:
3523:
3511:
3510:
3498:
3497:
3476:
3475:
3459:
3457:
3456:
3451:
3437:
3436:
3420:
3418:
3417:
3412:
3400:
3398:
3397:
3392:
3374:
3372:
3371:
3366:
3354:
3352:
3351:
3346:
3341:
3327:
3322:
3304:
3302:
3301:
3296:
3284:
3282:
3281:
3276:
3274:
3273:
3257:
3255:
3254:
3249:
3247:
3246:
3230:
3228:
3227:
3222:
3220:
3219:
3203:
3201:
3200:
3195:
3183:
3181:
3180:
3175:
3146:
3129:
3121:
3119:
3118:
3113:
3101:
3099:
3098:
3093:
3081:
3079:
3078:
3073:
3061:
3059:
3058:
3053:
3041:
3039:
3038:
3033:
3021:
3019:
3018:
3013:
3001:
2999:
2998:
2993:
2982:. The flow into
2981:
2979:
2978:
2973:
2961:
2959:
2958:
2953:
2941:
2939:
2938:
2933:
2899:
2891:
2889:
2888:
2883:
2871:
2869:
2868:
2863:
2851:
2849:
2848:
2843:
2809:
2791:
2787:
2785:
2784:
2779:
2767:
2765:
2764:
2759:
2747:
2745:
2744:
2739:
2719:
2717:
2716:
2711:
2706:
2705:
2681:, which runs in
2673:
2671:
2670:
2665:
2653:
2651:
2650:
2645:
2633:
2631:
2630:
2625:
2604:
2602:
2601:
2596:
2584:
2582:
2581:
2576:
2560:
2558:
2557:
2552:
2519:
2517:
2516:
2511:
2509:
2508:
2493:
2492:
2491:
2472:
2471:
2470:
2445:, with capacity
2444:
2442:
2441:
2436:
2431:
2430:
2429:
2410:
2409:
2408:
2385:
2383:
2382:
2377:
2375:
2374:
2373:
2354:
2353:
2352:
2332:
2330:
2329:
2324:
2322:
2321:
2305:
2302:Also, if a node
2297:
2295:
2294:
2289:
2268:
2238:
2237:
2222:
2221:
2194:, with capacity
2193:
2191:
2190:
2185:
2183:
2182:
2166:
2164:
2163:
2158:
2141:from every node
2140:
2138:
2137:
2132:
2127:
2126:
2101:
2099:
2098:
2093:
2091:
2090:
2074:
2072:
2071:
2066:
2045:
2015:
2014:
1993:
1992:
1971:, with capacity
1970:
1968:
1967:
1962:
1944:
1942:
1941:
1936:
1934:
1933:
1917:
1915:
1914:
1909:
1898:
1897:
1878:
1876:
1875:
1870:
1868:
1867:
1851:
1849:
1848:
1843:
1838:
1835:
1808:
1806:
1805:
1800:
1795:
1792:
1765:
1763:
1762:
1757:
1723:
1719:
1715:
1711:
1707:
1703:
1699:
1695:
1684:
1682:
1681:
1676:
1671:
1670:
1652:
1651:
1617:
1592:
1576:
1574:
1573:
1568:
1557:
1556:
1492:
1490:
1489:
1484:
1473:
1472:
1413:
1411:
1410:
1405:
1373:
1371:
1370:
1365:
1321:
1320:
1293:
1292:
1273:
1271:
1270:
1265:
1235:
1233:
1232:
1227:
1204:
1203:
1187:
1185:
1184:
1179:
1177:
1176:
1160:
1156:
1152:
1146:
1144:
1143:
1138:
1114:
1112:
1111:
1106:
1071:
1067:
1063:
1054:
1050:
1047:, a source node
1046:
1042:
1040:
1039:
1034:
1005:Given a Network
990:
988:
987:
982:
896:
895:
879:
877:
876:
871:
838:
836:
835:
830:
797:
793:
789:
787:
786:
781:
722:
721:
705:
703:
702:
697:
692:
691:
673:
672:
656:residual network
641:
637:
631:
629:
628:
623:
602:
553:
510:
508:
507:
502:
475:
448:
445:
405:
401:
397:
393:
387:
385:
384:
379:
333:
289:
287:
286:
281:
238:
199:
198:
193:
189:
185:
183:
182:
177:
150:
148:
147:
142:
115:
111:
107:
105:
104:
99:
35:greedy algorithm
6486:
6485:
6481:
6480:
6479:
6477:
6476:
6475:
6456:
6455:
6425:
6367:
6333:
6310:
6294:Stein, Clifford
6277:
6272:
6271:
6237:
6233:
6225:10.1.1.295.9049
6217:
6216:
6212:
6178:
6165:
6161:
6154:
6132:
6128:
6112:
6111:
6107:
6085:
6081:
6076:
6053:Berge's theorem
6049:
6044:
6043:
6040:
6037:
6034:
6031:
6028:
6025:
6022:
6019:
6016:
6013:
6010:
6007:
6004:
6001:
5998:
5995:
5992:
5989:
5986:
5983:
5980:
5977:
5974:
5971:
5968:
5965:
5962:
5959:
5956:
5953:
5950:
5947:
5944:
5941:
5938:
5935:
5932:
5929:
5926:
5923:
5920:
5917:
5914:
5911:
5908:
5905:
5902:
5899:
5896:
5893:
5890:
5887:
5884:
5881:
5879:"Inf"
5878:
5875:
5872:
5869:
5866:
5863:
5860:
5857:
5854:
5851:
5848:
5845:
5842:
5839:
5836:
5833:
5830:
5827:
5824:
5821:
5818:
5815:
5812:
5809:
5806:
5803:
5800:
5797:
5794:
5791:
5788:
5785:
5782:
5779:
5776:
5773:
5770:
5767:
5764:
5761:
5758:
5755:
5752:
5749:
5746:
5743:
5740:
5737:
5734:
5731:
5728:
5725:
5722:
5719:
5716:
5713:
5710:
5707:
5704:
5701:
5698:
5695:
5692:
5689:
5686:
5683:
5680:
5677:
5674:
5671:
5668:
5665:
5662:
5659:
5656:
5653:
5650:
5647:
5644:
5641:
5638:
5635:
5632:
5629:
5626:
5623:
5620:
5617:
5614:
5611:
5608:
5605:
5602:
5599:
5596:
5593:
5590:
5587:
5584:
5581:
5578:
5575:
5572:
5569:
5566:
5563:
5560:
5557:
5554:
5551:
5548:
5545:
5542:
5539:
5536:
5533:
5530:
5527:
5524:
5521:
5518:
5515:
5512:
5509:
5506:
5503:
5500:
5497:
5494:
5491:
5488:
5485:
5482:
5479:
5476:
5473:
5470:
5467:
5464:
5461:
5458:
5455:
5452:
5449:
5446:
5443:
5440:
5437:
5434:
5431:
5428:
5425:
5422:
5419:
5416:
5413:
5410:
5407:
5404:
5401:
5398:
5395:
5392:
5389:
5363:
5355:
5348:
5344:
5342:
5339:
5338:
5335:ordinal numbers
5303:
5300:
5299:
5268:
5264:
5259:
5256:
5255:
5239:
5236:
5235:
5215:
5211:
5205:
5201:
5196:
5193:
5192:
5172:
5168:
5163:
5160:
5159:
5143:
5140:
5139:
5114:
5111:
5110:
5077:
5073:
5067:
5056:
5040:
5037:
5036:
5016:
5012:
5003:
4999:
4985:
4982:
4981:
4964:
4960:
4958:
4955:
4954:
4937:
4933:
4931:
4928:
4927:
4910:
4906:
4904:
4901:
4900:
4883:
4879:
4877:
4874:
4873:
4857:
4849:
4846:
4845:
4829:
4826:
4825:
4802:
4798:
4796:
4793:
4792:
4775:
4771:
4769:
4766:
4765:
4748:
4744:
4742:
4739:
4738:
4721:
4717:
4715:
4712:
4711:
4694:
4690:
4688:
4685:
4684:
4663:
4660:
4659:
4641:
4637:
4635:
4632:
4631:
4613:
4609:
4607:
4604:
4603:
4585:
4581:
4579:
4576:
4575:
4557:
4553:
4551:
4548:
4547:
4524:
4520:
4518:
4515:
4514:
4496:
4492:
4483:
4479:
4470:
4466:
4464:
4461:
4460:
4443:
4440:
4439:
4421:
4417:
4415:
4412:
4411:
4393:
4389:
4387:
4384:
4383:
4361:
4358:
4357:
4339:
4335:
4333:
4330:
4329:
4311:
4307:
4305:
4302:
4301:
4283:
4279:
4277:
4274:
4273:
4255:
4251:
4249:
4246:
4245:
4222:
4218:
4216:
4213:
4212:
4195:
4192:
4191:
4173:
4169:
4160:
4156:
4147:
4143:
4141:
4138:
4137:
4119:
4115:
4113:
4110:
4109:
4091:
4087:
4085:
4082:
4081:
4059:
4056:
4055:
4037:
4033:
4031:
4028:
4027:
4009:
4005:
4003:
4000:
3999:
3982:
3979:
3978:
3951:
3947:
3938:
3934:
3923:
3920:
3919:
3897:
3894:
3893:
3876:
3873:
3872:
3848:
3844:
3842:
3839:
3838:
3811:
3807:
3805:
3802:
3801:
3783:
3779:
3777:
3774:
3773:
3755:
3751:
3749:
3746:
3745:
3734:Augmenting path
3700:
3696:
3687:
3683:
3674:
3670:
3652:
3648:
3646:
3643:
3642:
3616:
3612:
3603:
3599:
3590:
3586:
3568:
3564:
3562:
3559:
3558:
3532:
3528:
3519:
3515:
3506:
3502:
3493:
3489:
3471:
3467:
3465:
3462:
3461:
3432:
3428:
3426:
3423:
3422:
3406:
3403:
3402:
3401:. The constant
3380:
3377:
3376:
3360:
3357:
3356:
3337:
3321:
3310:
3307:
3306:
3290:
3287:
3286:
3269:
3265:
3263:
3260:
3259:
3242:
3238:
3236:
3233:
3232:
3215:
3211:
3209:
3206:
3205:
3189:
3186:
3185:
3169:
3166:
3165:
3155:
3107:
3104:
3103:
3087:
3084:
3083:
3067:
3064:
3063:
3047:
3044:
3043:
3027:
3024:
3023:
3022:now comes from
3007:
3004:
3003:
2987:
2984:
2983:
2967:
2964:
2963:
2947:
2944:
2943:
2909:
2906:
2905:
2877:
2874:
2873:
2857:
2854:
2853:
2819:
2816:
2815:
2773:
2770:
2769:
2753:
2750:
2749:
2733:
2730:
2729:
2726:
2701:
2697:
2686:
2683:
2682:
2659:
2656:
2655:
2639:
2636:
2635:
2610:
2607:
2606:
2590:
2587:
2586:
2570:
2567:
2566:
2534:
2531:
2530:
2526:
2504:
2500:
2481:
2480:
2476:
2463:
2462:
2458:
2450:
2447:
2446:
2419:
2418:
2414:
2401:
2400:
2396:
2391:
2388:
2387:
2363:
2362:
2358:
2345:
2344:
2340:
2338:
2335:
2334:
2317:
2313:
2311:
2308:
2307:
2303:
2301:
2246:
2233:
2229:
2217:
2213:
2199:
2196:
2195:
2178:
2174:
2172:
2169:
2168:
2146:
2143:
2142:
2122:
2118:
2107:
2104:
2103:
2086:
2082:
2080:
2077:
2076:
2023:
2010:
2006:
1988:
1984:
1976:
1973:
1972:
1950:
1947:
1946:
1929:
1925:
1923:
1920:
1919:
1893:
1889:
1884:
1881:
1880:
1863:
1859:
1857:
1854:
1853:
1834:
1814:
1811:
1810:
1793: is a sink
1791:
1771:
1768:
1767:
1736:
1733:
1732:
1721:
1717:
1713:
1709:
1705:
1701:
1697:
1693:
1666:
1662:
1647:
1643:
1641:
1638:
1637:
1626:
1552:
1548:
1504:
1501:
1500:
1468:
1464:
1420:
1417:
1416:
1381:
1378:
1377:
1316:
1312:
1288:
1284:
1282:
1279:
1278:
1241:
1238:
1237:
1199:
1195:
1193:
1190:
1189:
1172:
1168:
1166:
1163:
1162:
1158:
1154:
1150:
1120:
1117:
1116:
1079:
1076:
1075:
1069:
1065:
1061:
1060:Compute a flow
1052:
1048:
1044:
1010:
1007:
1006:
999:
891:
887:
885:
882:
881:
844:
841:
840:
803:
800:
799:
795:
791:
717:
713:
711:
708:
707:
687:
683:
668:
664:
662:
659:
658:
639:
635:
580:
531:
525:
522:
521:
465:
446: and
444:
418:
415:
414:
406:(see example).
403:
399:
395:
391:
304:
301:
300:
209:
206:
205:
191:
187:
156:
153:
152:
121:
118:
117:
113:
109:
78:
75:
74:
71:
63:augmenting path
51:D. R. Fulkerson
19:
12:
11:
5:
6484:
6474:
6473:
6468:
6442:
6441:
6436:
6431:
6424:
6423:External links
6421:
6420:
6419:
6391:(4): 341–347.
6380:
6371:
6365:
6337:
6331:
6314:
6308:
6276:
6273:
6270:
6269:
6256:(1): 165–170.
6231:
6210:
6159:
6153:978-0262258104
6152:
6126:
6106:978-0080922003
6105:
6078:
6077:
6075:
6072:
6071:
6070:
6065:
6060:
6055:
6048:
6045:
5391:
5388:
5385:
5370:
5366:
5362:
5358:
5354:
5351:
5347:
5322:
5319:
5316:
5313:
5310:
5307:
5276:
5271:
5267:
5263:
5243:
5223:
5218:
5214:
5208:
5204:
5200:
5180:
5175:
5171:
5167:
5147:
5127:
5124:
5121:
5118:
5097:
5094:
5091:
5088:
5085:
5080:
5076:
5070:
5065:
5062:
5059:
5055:
5051:
5048:
5045:
5024:
5019:
5015:
5011:
5006:
5002:
4998:
4995:
4992:
4989:
4967:
4963:
4940:
4936:
4913:
4909:
4886:
4882:
4860:
4856:
4853:
4833:
4811:
4808:
4805:
4801:
4778:
4774:
4751:
4747:
4724:
4720:
4697:
4693:
4679:
4678:
4667:
4657:
4644:
4640:
4629:
4616:
4612:
4601:
4588:
4584:
4573:
4560:
4556:
4545:
4541:
4540:
4527:
4523:
4512:
4499:
4495:
4491:
4486:
4482:
4478:
4473:
4469:
4458:
4447:
4437:
4424:
4420:
4409:
4396:
4392:
4381:
4377:
4376:
4365:
4355:
4342:
4338:
4327:
4314:
4310:
4299:
4286:
4282:
4271:
4258:
4254:
4243:
4239:
4238:
4225:
4221:
4210:
4199:
4189:
4176:
4172:
4168:
4163:
4159:
4155:
4150:
4146:
4135:
4122:
4118:
4107:
4094:
4090:
4079:
4075:
4074:
4063:
4053:
4040:
4036:
4025:
4012:
4008:
3997:
3986:
3976:
3965:
3962:
3959:
3954:
3950:
3946:
3941:
3937:
3933:
3930:
3927:
3917:
3913:
3912:
3901:
3891:
3880:
3870:
3859:
3856:
3851:
3847:
3836:
3834:
3832:
3828:
3827:
3814:
3810:
3799:
3786:
3782:
3771:
3758:
3754:
3742:
3741:
3738:
3735:
3732:
3714:
3711:
3708:
3703:
3699:
3695:
3690:
3686:
3682:
3677:
3673:
3669:
3666:
3663:
3660:
3655:
3651:
3630:
3627:
3624:
3619:
3615:
3611:
3606:
3602:
3598:
3593:
3589:
3585:
3582:
3579:
3576:
3571:
3567:
3546:
3543:
3540:
3535:
3531:
3527:
3522:
3518:
3514:
3509:
3505:
3501:
3496:
3492:
3488:
3485:
3482:
3479:
3474:
3470:
3449:
3446:
3443:
3440:
3435:
3431:
3410:
3390:
3387:
3384:
3364:
3344:
3340:
3336:
3333:
3330:
3325:
3320:
3317:
3314:
3294:
3272:
3268:
3245:
3241:
3218:
3214:
3193:
3173:
3154:
3151:
3148:
3147:
3140:
3136:
3135:
3131:
3130:
3123:
3111:
3091:
3071:
3051:
3031:
3011:
2991:
2971:
2951:
2931:
2928:
2925:
2922:
2919:
2916:
2913:
2901:
2900:
2893:
2881:
2861:
2841:
2838:
2835:
2832:
2829:
2826:
2823:
2811:
2810:
2803:
2799:
2798:
2795:
2777:
2757:
2737:
2725:
2722:
2709:
2704:
2700:
2696:
2693:
2690:
2663:
2643:
2623:
2620:
2617:
2614:
2594:
2574:
2563:big O notation
2550:
2547:
2544:
2541:
2538:
2525:
2522:
2507:
2503:
2499:
2496:
2490:
2487:
2484:
2479:
2475:
2469:
2466:
2461:
2457:
2454:
2434:
2428:
2425:
2422:
2417:
2413:
2407:
2404:
2399:
2395:
2386:, and an edge
2372:
2369:
2366:
2361:
2357:
2351:
2348:
2343:
2320:
2316:
2287:
2284:
2281:
2278:
2275:
2272:
2267:
2264:
2261:
2258:
2255:
2252:
2249:
2245:
2241:
2236:
2232:
2228:
2225:
2220:
2216:
2212:
2209:
2206:
2203:
2181:
2177:
2156:
2153:
2150:
2130:
2125:
2121:
2117:
2114:
2111:
2089:
2085:
2064:
2061:
2058:
2055:
2052:
2049:
2044:
2041:
2038:
2035:
2032:
2029:
2026:
2022:
2018:
2013:
2009:
2005:
2002:
1999:
1996:
1991:
1987:
1983:
1980:
1960:
1957:
1954:
1945:to every node
1932:
1928:
1907:
1904:
1901:
1896:
1892:
1888:
1866:
1862:
1841:
1833:
1830:
1827:
1824:
1821:
1818:
1798:
1790:
1787:
1784:
1781:
1778:
1775:
1755:
1752:
1749:
1746:
1743:
1740:
1674:
1669:
1665:
1661:
1658:
1655:
1650:
1646:
1625:
1624:
1615:
1589:
1588:
1587:
1586:
1585:
1584:
1583:
1582:
1566:
1563:
1560:
1555:
1551:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1498:
1482:
1479:
1476:
1471:
1467:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1376:For each edge
1374:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1324:
1319:
1315:
1311:
1308:
1305:
1302:
1299:
1296:
1291:
1287:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1236:for all edges
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1202:
1198:
1175:
1171:
1147:
1136:
1133:
1130:
1127:
1124:
1115:for all edges
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1055:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
994:
993:
980:
977:
974:
971:
968:
965:
962:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
929:
926:
923:
920:
917:
914:
911:
908:
905:
902:
899:
894:
890:
869:
866:
863:
860:
857:
854:
851:
848:
828:
825:
822:
819:
816:
813:
810:
807:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
720:
716:
695:
690:
686:
682:
679:
676:
671:
667:
648:
647:
644:
643:
632:
621:
618:
615:
612:
609:
606:
601:
598:
595:
592:
589:
586:
583:
579:
575:
572:
569:
566:
563:
560:
557:
552:
549:
546:
543:
540:
537:
534:
530:
519:
515:
514:
511:
500:
497:
494:
491:
488:
485:
482:
479:
474:
471:
468:
464:
460:
457:
454:
451:
443:
440:
437:
434:
431:
428:
425:
422:
412:
408:
407:
388:
377:
374:
371:
368:
365:
362:
359:
356:
353:
350:
347:
344:
341:
338:
332:
329:
326:
323:
320:
317:
314:
311:
308:
298:
297:Skew symmetry
294:
293:
290:
279:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
237:
234:
231:
228:
225:
222:
219:
216:
213:
203:
175:
172:
169:
166:
163:
160:
140:
137:
134:
131:
128:
125:
97:
94:
91:
88:
85:
82:
70:
67:
47:L. R. Ford Jr.
17:
9:
6:
4:
3:
2:
6483:
6472:
6469:
6467:
6464:
6463:
6461:
6454:
6452:
6447:
6440:
6437:
6435:
6432:
6430:
6427:
6426:
6416:
6412:
6408:
6404:
6399:
6394:
6390:
6386:
6385:Computability
6381:
6377:
6372:
6368:
6366:0-321-29535-8
6362:
6358:
6354:
6350:
6346:
6342:
6341:Jon Kleinberg
6338:
6334:
6328:
6324:
6323:Oreilly Media
6320:
6315:
6311:
6309:0-262-03293-7
6305:
6301:
6300:
6295:
6291:
6287:
6283:
6279:
6278:
6264:
6259:
6255:
6251:
6250:
6245:
6241:
6235:
6226:
6221:
6214:
6206:
6202:
6198:
6194:
6190:
6186:
6185:
6177:
6173:
6169:
6163:
6155:
6149:
6145:
6140:
6139:
6130:
6122:
6116:
6108:
6102:
6098:
6093:
6092:
6083:
6079:
6069:
6066:
6064:
6061:
6059:
6056:
6054:
6051:
6050:
5384:
5360:
5345:
5336:
5317:
5314:
5311:
5305:
5297:
5293:
5288:
5274:
5269:
5265:
5261:
5241:
5221:
5216:
5212:
5206:
5202:
5198:
5178:
5173:
5169:
5165:
5145:
5138:, by sending
5125:
5122:
5119:
5116:
5095:
5092:
5089:
5086:
5083:
5078:
5074:
5063:
5060:
5057:
5053:
5049:
5046:
5043:
5017:
5013:
5009:
5004:
5000:
4993:
4990:
4987:
4965:
4961:
4938:
4934:
4911:
4907:
4884:
4880:
4854:
4851:
4831:
4809:
4806:
4803:
4799:
4776:
4772:
4749:
4745:
4722:
4718:
4695:
4691:
4665:
4658:
4642:
4638:
4630:
4614:
4610:
4602:
4586:
4582:
4574:
4558:
4554:
4546:
4543:
4542:
4525:
4521:
4513:
4497:
4493:
4489:
4484:
4480:
4476:
4471:
4467:
4459:
4445:
4438:
4422:
4418:
4410:
4394:
4390:
4382:
4379:
4378:
4363:
4356:
4340:
4336:
4328:
4312:
4308:
4300:
4284:
4280:
4272:
4256:
4252:
4244:
4241:
4240:
4223:
4219:
4211:
4197:
4190:
4174:
4170:
4166:
4161:
4157:
4153:
4148:
4144:
4136:
4120:
4116:
4108:
4092:
4088:
4080:
4077:
4076:
4061:
4054:
4038:
4034:
4026:
4010:
4006:
3998:
3984:
3977:
3960:
3957:
3952:
3948:
3944:
3939:
3935:
3931:
3928:
3918:
3915:
3914:
3899:
3892:
3878:
3871:
3857:
3854:
3849:
3845:
3837:
3835:
3833:
3830:
3829:
3812:
3808:
3800:
3784:
3780:
3772:
3756:
3752:
3744:
3743:
3729:
3726:
3709:
3706:
3701:
3697:
3693:
3688:
3684:
3680:
3675:
3671:
3667:
3664:
3658:
3653:
3649:
3625:
3622:
3617:
3613:
3609:
3604:
3600:
3596:
3591:
3587:
3583:
3580:
3574:
3569:
3565:
3541:
3538:
3533:
3529:
3525:
3520:
3516:
3512:
3507:
3503:
3499:
3494:
3490:
3486:
3483:
3477:
3472:
3468:
3447:
3444:
3441:
3438:
3433:
3429:
3408:
3388:
3385:
3382:
3362:
3342:
3338:
3331:
3328:
3323:
3315:
3312:
3292:
3285:respectively
3270:
3266:
3243:
3239:
3216:
3212:
3191:
3171:
3159:
3145:
3141:
3138:
3137:
3132:
3128:
3124:
3109:
3089:
3069:
3049:
3029:
3009:
2989:
2969:
2949:
2929:
2926:
2923:
2920:
2917:
2914:
2911:
2903:
2902:
2898:
2894:
2879:
2859:
2839:
2836:
2833:
2830:
2827:
2824:
2821:
2813:
2812:
2808:
2804:
2801:
2800:
2797:Flow network
2796:
2793:
2792:
2789:
2775:
2755:
2735:
2721:
2702:
2698:
2694:
2688:
2680:
2675:
2661:
2641:
2618:
2612:
2592:
2572:
2564:
2545:
2542:
2536:
2521:
2505:
2501:
2497:
2477:
2473:
2459:
2452:
2415:
2411:
2397:
2359:
2355:
2341:
2318:
2314:
2299:
2282:
2279:
2276:
2270:
2265:
2262:
2256:
2253:
2250:
2243:
2239:
2234:
2230:
2226:
2218:
2214:
2210:
2207:
2201:
2179:
2175:
2154:
2151:
2148:
2123:
2119:
2115:
2112:
2102:with an edge
2087:
2083:
2059:
2056:
2053:
2047:
2042:
2039:
2033:
2030:
2027:
2020:
2016:
2011:
2007:
2003:
1997:
1994:
1989:
1985:
1978:
1958:
1955:
1952:
1930:
1926:
1902:
1899:
1894:
1890:
1879:with an edge
1864:
1860:
1831:
1828:
1825:
1819:
1816:
1788:
1785:
1782:
1776:
1773:
1750:
1747:
1744:
1738:
1731:If the graph
1729:
1727:
1690:
1688:
1667:
1663:
1659:
1656:
1648:
1644:
1635:
1631:
1621:
1616:
1612:
1608:
1604:
1600:
1596:
1591:
1590:
1580:
1561:
1553:
1549:
1545:
1539:
1536:
1533:
1527:
1518:
1515:
1512:
1506:
1499:
1496:
1477:
1469:
1465:
1461:
1455:
1452:
1449:
1443:
1434:
1431:
1428:
1422:
1415:
1414:
1401:
1398:
1392:
1389:
1386:
1375:
1358:
1355:
1349:
1346:
1343:
1337:
1331:
1328:
1325:
1317:
1313:
1303:
1297:
1289:
1285:
1276:
1275:
1261:
1258:
1252:
1249:
1246:
1223:
1220:
1214:
1211:
1208:
1200:
1196:
1173:
1169:
1148:
1131:
1128:
1125:
1102:
1093:
1090:
1087:
1081:
1074:
1073:
1059:
1056:
1027:
1024:
1021:
1015:
1012:
1004:
1001:
1000:
997:
992:
978:
975:
969:
966:
963:
957:
954:
948:
945:
942:
936:
933:
927:
924:
921:
915:
912:
906:
903:
900:
892:
888:
867:
864:
858:
855:
852:
846:
826:
823:
817:
814:
811:
805:
774:
771:
768:
762:
759:
753:
750:
747:
741:
738:
732:
729:
726:
718:
714:
688:
684:
680:
677:
669:
665:
657:
653:
633:
616:
613:
610:
604:
599:
596:
590:
587:
584:
577:
573:
567:
564:
561:
555:
550:
547:
541:
538:
535:
528:
520:
517:
516:
512:
498:
495:
489:
486:
483:
477:
472:
469:
466:
462:
455:
452:
449:
441:
438:
435:
432:
429:
426:
423:
413:
410:
409:
389:
372:
369:
366:
360:
357:
354:
348:
345:
342:
336:
330:
327:
324:
318:
315:
312:
299:
296:
295:
291:
274:
271:
268:
262:
259:
253:
250:
247:
241:
235:
232:
229:
223:
220:
217:
204:
201:
200:
197:
196:
195:
170:
167:
164:
158:
135:
132:
129:
123:
92:
89:
86:
80:
66:
64:
58:
56:
52:
48:
44:
40:
36:
32:
28:
24:
16:
6443:
6388:
6384:
6375:
6352:
6318:
6297:
6253:
6247:
6234:
6213:
6188:
6182:
6162:
6137:
6129:
6090:
6082:
5765:edmonds_karp
5294:is given by
5289:
4682:
3163:
2727:
2676:
2527:
2300:
1730:
1691:
1627:
1619:
1610:
1606:
1602:
1598:
1578:
1494:
1188:, such that
1057:
1002:
995:
655:
651:
649:
190:to the sink
72:
59:
43:flow network
39:maximum flow
30:
26:
22:
20:
15:
6191:: 399–404.
6168:Ford, L. R.
5561:collections
5396:collections
6460:Categories
6398:1504.04363
6376:ENGRI 1101
6345:Éva Tardos
6275:References
6240:Zwick, Uri
2524:Complexity
1595:assignment
652:legal flow
6220:CiteSeerX
6115:cite book
6026:path_flow
6011:path_flow
5957:path_flow
5921:path_flow
5909:path_flow
5867:path_flow
5657:enumerate
5350:Θ
5346:ω
5069:∞
5054:∑
4855:∈
4477:−
4154:−
3737:Sent flow
3445:−
3386:≥
3329:−
2748:and sink
2565:), where
2263:∈
2244:∑
2219:∗
2180:∗
2152:∈
2124:∗
2088:∗
2040:∈
2021:∑
1990:∗
1956:∈
1931:∗
1895:∗
1865:∗
1829:∣
1786:∣
1632:(BFS) or
1546:−
1525:←
1441:←
1399:∈
1356:∈
1259:∈
1100:←
996:Algorithm
934:−
760:−
597:∈
578:∑
548:∈
529:∑
518:Value(f)
470:∈
463:∑
459:⇒
453:≠
439:≠
427:∈
421:∀
358:−
325:∈
307:∀
260:≤
230:∈
212:∀
69:Algorithm
6415:15497138
6347:(2006).
6205:16109790
6174:(1956).
6047:See also
6041:max_flow
5951:max_flow
5810:max_flow
5423:__init__
1601:←
6357:378–384
5756:visited
5729:visited
5681:visited
5627:popleft
5594:visited
5534:visited
3184:, sink
1607:largest
1599:largest
33:) is a
6413:
6363:
6329:
6306:
6222:
6203:
6150:
6103:
6038:return
6035:parent
5996:parent
5984:source
5945:parent
5903:source
5852:parent
5840:source
5792:parent
5777:source
5753:return
5738:parent
5717:append
5582:append
5510:parent
5393:import
5234:, and
3042:, and
2720:time.
1620:return
1058:Output
1003:Inputs
334:
239:
116:, let
6411:S2CID
6393:arXiv
6201:S2CID
6179:(PDF)
6074:Notes
6020:graph
6005:graph
5975:while
5933:graph
5894:while
5873:float
5825:while
5711:queue
5687:False
5669:graph
5621:queue
5609:queue
5606:while
5576:queue
5567:deque
5555:queue
5477:graph
5453:graph
5447:graph
5435:graph
5402:Graph
5399:class
2794:Step
2561:(see
1918:from
1277:Find
1153:from
1064:from
880:then
41:in a
6361:ISBN
6327:ISBN
6304:ISBN
6148:ISBN
6121:link
6101:ISBN
6014:self
5999:self
5972:sink
5927:self
5891:sink
5846:sink
5828:self
5801:self
5783:sink
5771:self
5735:True
5702:>
5663:self
5600:True
5543:self
5492:self
5459:self
5441:self
5429:self
4953:and
4824:and
4737:and
3731:Step
3641:and
3355:and
3258:and
1809:and
1611:item
1603:item
1221:>
976:>
839:and
824:>
73:Let
49:and
21:The
6403:doi
6258:doi
6254:148
6193:doi
6144:714
6097:204
5915:min
5834:bfs
5807:row
5762:def
5723:ind
5699:val
5693:and
5651:val
5645:ind
5642:for
5549:row
5486:bfs
5483:def
5471:len
5465:row
5420:def
5337:is
5333:in
2962:to
2167:to
1720:to
1636:in
1307:min
1161:in
1157:to
1068:to
794:to
402:to
394:to
112:to
31:FFA
25:or
6462::
6409:.
6401:.
6387:.
6359:.
6351:.
6343:;
6321:.
6292:;
6288:;
6284:;
6252:.
6246:.
6199:.
6187:.
6181:.
6170:;
6146:.
6117:}}
6113:{{
6099:.
6023:+=
6008:-=
5981:!=
5954:+=
5936:])
5900:!=
5855:):
5786:):
5708:):
5684:==
5675:if
5672:):
5654:in
5630:()
5570:()
5513:):
5438:):
5383:.
4926:,
4899:,
4791:,
4710:,
3725:.
3557:,
3305:,
3231:,
2674:.
1728:.
1689:.
1274::
991:.
642:.
65:.
6417:.
6405::
6395::
6389:7
6369:.
6335:.
6312:.
6266:.
6260::
6228:.
6207:.
6195::
6189:8
6156:.
6123:)
6109:.
6032:=
6029:v
6017:.
6002:.
5993:=
5990:u
5987::
5978:v
5969:=
5966:v
5942:=
5939:s
5930:.
5924:,
5918:(
5912:=
5906::
5897:s
5888:=
5885:s
5882:)
5876:(
5870:=
5849:,
5843:,
5837:(
5831:.
5816:0
5813:=
5804:.
5798:*
5795:=
5780:,
5774:,
5768:(
5744:u
5741:=
5732:=
5726:)
5720:(
5714:.
5705:0
5696:(
5690:)
5678:(
5666:.
5660:(
5648:,
5624:.
5618:=
5615:u
5612::
5597:=
5591:)
5588:s
5585:(
5579:.
5564:.
5558:=
5546:.
5540:*
5537:=
5507:,
5504:t
5501:,
5498:s
5495:,
5489:(
5480:)
5474:(
5468:=
5462:.
5450:=
5444:.
5432:,
5426:(
5405::
5369:)
5365:|
5361:E
5357:|
5353:(
5321:)
5318:E
5315:,
5312:V
5309:(
5306:G
5275:t
5270:4
5266:v
5262:s
5242:M
5222:t
5217:3
5213:v
5207:2
5203:v
5199:s
5179:t
5174:1
5170:v
5166:s
5146:M
5126:1
5123:+
5120:M
5117:2
5096:r
5093:2
5090:+
5087:3
5084:=
5079:i
5075:r
5064:1
5061:=
5058:i
5050:2
5047:+
5044:1
5023:)
5018:2
5014:r
5010:+
5005:1
5001:r
4997:(
4994:2
4991:+
4988:1
4966:3
4962:p
4939:1
4935:p
4912:2
4908:p
4885:1
4881:p
4859:N
4852:n
4832:0
4810:1
4807:+
4804:n
4800:r
4777:n
4773:r
4750:3
4746:e
4723:2
4719:e
4696:1
4692:e
4666:0
4643:3
4639:r
4615:2
4611:r
4587:2
4583:r
4559:3
4555:p
4544:5
4526:2
4522:r
4498:3
4494:r
4490:=
4485:2
4481:r
4472:1
4468:r
4446:0
4423:2
4419:r
4395:1
4391:p
4380:4
4364:0
4341:1
4337:r
4313:2
4309:r
4285:1
4281:r
4257:2
4253:p
4242:3
4224:1
4220:r
4198:0
4175:2
4171:r
4167:=
4162:1
4158:r
4149:0
4145:r
4121:1
4117:r
4093:1
4089:p
4078:2
4062:0
4039:1
4035:r
4011:0
4007:r
3985:1
3964:}
3961:t
3958:,
3953:3
3949:v
3945:,
3940:2
3936:v
3932:,
3929:s
3926:{
3916:1
3900:1
3879:r
3858:1
3855:=
3850:0
3846:r
3831:0
3813:3
3809:e
3785:2
3781:e
3757:1
3753:e
3713:}
3710:t
3707:,
3702:3
3698:v
3694:,
3689:2
3685:v
3681:,
3676:1
3672:v
3668:,
3665:s
3662:{
3659:=
3654:3
3650:p
3629:}
3626:t
3623:,
3618:4
3614:v
3610:,
3605:3
3601:v
3597:,
3592:2
3588:v
3584:,
3581:s
3578:{
3575:=
3570:2
3566:p
3545:}
3542:t
3539:,
3534:1
3530:v
3526:,
3521:2
3517:v
3513:,
3508:3
3504:v
3500:,
3495:4
3491:v
3487:,
3484:s
3481:{
3478:=
3473:1
3469:p
3448:r
3442:1
3439:=
3434:2
3430:r
3409:r
3389:2
3383:M
3363:1
3343:2
3339:/
3335:)
3332:1
3324:5
3319:(
3316:=
3313:r
3293:1
3271:3
3267:e
3244:2
3240:e
3217:1
3213:e
3192:t
3172:s
3110:C
3102:–
3090:B
3070:D
3050:B
3030:A
3010:B
2990:C
2970:B
2950:C
2930:D
2927:,
2924:B
2921:,
2918:C
2915:,
2912:A
2880:C
2872:–
2860:B
2840:D
2837:,
2834:C
2831:,
2828:B
2825:,
2822:A
2776:1
2756:D
2736:A
2708:)
2703:2
2699:E
2695:V
2692:(
2689:O
2662:f
2642:1
2622:)
2619:E
2616:(
2613:O
2593:f
2573:E
2549:)
2546:f
2543:E
2540:(
2537:O
2506:u
2502:d
2498:=
2495:)
2489:t
2486:u
2483:o
2478:u
2474:,
2468:n
2465:i
2460:u
2456:(
2453:c
2433:)
2427:t
2424:u
2421:o
2416:u
2412:,
2406:n
2403:i
2398:u
2394:(
2371:t
2368:u
2365:o
2360:u
2356:,
2350:n
2347:i
2342:u
2319:u
2315:d
2304:u
2286:)
2283:t
2280:,
2277:v
2274:(
2271:c
2266:E
2260:)
2257:t
2254:,
2251:v
2248:(
2240:=
2235:t
2231:d
2227:=
2224:)
2215:t
2211:,
2208:t
2205:(
2202:c
2176:t
2155:T
2149:t
2129:)
2120:t
2116:,
2113:t
2110:(
2084:t
2063:)
2060:u
2057:,
2054:s
2051:(
2048:c
2043:E
2037:)
2034:u
2031:,
2028:s
2025:(
2017:=
2012:s
2008:d
2004:=
2001:)
1998:s
1995:,
1986:s
1982:(
1979:c
1959:S
1953:s
1927:s
1906:)
1903:s
1900:,
1891:s
1887:(
1861:s
1840:}
1832:s
1826:s
1823:{
1820:=
1817:S
1797:}
1789:t
1783:t
1780:{
1777:=
1774:T
1754:)
1751:E
1748:,
1745:V
1742:(
1739:G
1722:t
1718:s
1714:V
1710:S
1706:s
1702:S
1698:t
1694:s
1673:)
1668:f
1664:E
1660:,
1657:V
1654:(
1649:f
1645:G
1618:"
1613:.
1581:)
1577:(
1565:)
1562:p
1559:(
1554:f
1550:c
1543:)
1540:u
1537:,
1534:v
1531:(
1528:f
1522:)
1519:u
1516:,
1513:v
1510:(
1507:f
1497:)
1493:(
1481:)
1478:p
1475:(
1470:f
1466:c
1462:+
1459:)
1456:v
1453:,
1450:u
1447:(
1444:f
1438:)
1435:v
1432:,
1429:u
1426:(
1423:f
1402:p
1396:)
1393:v
1390:,
1387:u
1384:(
1362:}
1359:p
1353:)
1350:v
1347:,
1344:u
1341:(
1338::
1335:)
1332:v
1329:,
1326:u
1323:(
1318:f
1314:c
1310:{
1304:=
1301:)
1298:p
1295:(
1290:f
1286:c
1262:p
1256:)
1253:v
1250:,
1247:u
1244:(
1224:0
1218:)
1215:v
1212:,
1209:u
1206:(
1201:f
1197:c
1174:f
1170:G
1159:t
1155:s
1151:p
1135:)
1132:v
1129:,
1126:u
1123:(
1103:0
1097:)
1094:v
1091:,
1088:u
1085:(
1082:f
1070:t
1066:s
1062:f
1053:t
1049:s
1045:c
1031:)
1028:E
1025:,
1022:V
1019:(
1016:=
1013:G
979:0
973:)
970:v
967:,
964:u
961:(
958:f
955:=
952:)
949:u
946:,
943:v
940:(
937:f
931:)
928:u
925:,
922:v
919:(
916:c
913:=
910:)
907:u
904:,
901:v
898:(
893:f
889:c
868:0
865:=
862:)
859:u
856:,
853:v
850:(
847:c
827:0
821:)
818:v
815:,
812:u
809:(
806:f
796:u
792:v
778:)
775:v
772:,
769:u
766:(
763:f
757:)
754:v
751:,
748:u
745:(
742:c
739:=
736:)
733:v
730:,
727:u
724:(
719:f
715:c
694:)
689:f
685:E
681:,
678:V
675:(
670:f
666:G
640:t
636:s
620:)
617:t
614:,
611:v
608:(
605:f
600:E
594:)
591:t
588:,
585:v
582:(
574:=
571:)
568:u
565:,
562:s
559:(
556:f
551:E
545:)
542:u
539:,
536:s
533:(
499:0
496:=
493:)
490:w
487:,
484:u
481:(
478:f
473:V
467:w
456:t
450:u
442:s
436:u
433::
430:V
424:u
404:u
400:v
396:v
392:u
376:)
373:u
370:,
367:v
364:(
361:f
355:=
352:)
349:v
346:,
343:u
340:(
337:f
331::
328:E
322:)
319:v
316:,
313:u
310:(
278:)
275:v
272:,
269:u
266:(
263:c
257:)
254:v
251:,
248:u
245:(
242:f
236::
233:E
227:)
224:v
221:,
218:u
215:(
192:t
188:s
174:)
171:v
168:,
165:u
162:(
159:f
139:)
136:v
133:,
130:u
127:(
124:c
114:v
110:u
96:)
93:E
90:,
87:V
84:(
81:G
29:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
