maths.free › Combinatorics & Graph Theory › Network Flows › Flows and Cuts
Flows and Cuts
Considering the applications suggested at the beginning of the chapter, it is natural to ask for the maximum value of a flow in a given network.
Flows and Cuts
Considering the applications suggested at the beginning of the chapter, it is natural to ask for the maximum value of a flow in a given network. Put another way, we want to find the largest number \(v_0\) so that there exists a flow \(\phi\) of value \(v_0\) in the network. Of course, we not only want to find the maximum value \(v_0\), but we also want to find a flow \(\phi\) having this value. Although it may seem a bit surprising, we will develop an efficient algorithm which both finds a flow of maximum value and finds a certificate verifying the claim of optimality. This certificate makes use of the following important concept.
A partition \(V=L\cup U\) of the vertex set \(V\) of a network with \(S\in L\) and \(T\in U\) is called a cut.Our choice of \(L\) and \(U\) for the names of the two parts of the partition will make more sense later in the chapter. The capacity of a cut \(V=L\cup U\), denoted \(c(L,U)\), is defined by \[\begin{aligned}\end{aligned}\] Put another way, the capacity of the cut \(V=L\cup U\) is the total capacity of all edges from \(L\) to \(U\). Note that in computing the capacity of the cut \(V=L\cup U\), we only add the capacities of the edges from \(L\) to \(U\). We do not include the edges from \(U\) to \(L\) in this sum.
Example
Let's again take a look at the network in . Let's first consider the cut \(V=L_1\cup U_1\) with \[\begin{aligned}\end{aligned}\] Here we see that the capacity of the cut is \[\begin{aligned}\end{aligned}\] We must be a bit more careful, however, when we look at the cut \(V=L_2\cup U_2\) with \[\begin{aligned}\end{aligned}\] Here the capacity of the cut is \[\begin{aligned}\end{aligned}\] Notice that we do not include \(c(D,B)\) in the calculation as the directed edge \((D,B)\) is from \(U_2\) to \(L_2\).
The relationship between flows and cuts rests on the following fundamentally important theorem.
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
Haddaad Ma jiro xisaabis oo ku nool midkan, laakiin qaybaha ka mid ah waa la xisaabi karaa. Ku raaxayso mid ka hooseeya, ama ku qor adiga kuu gaar ah.
A xisaab bilaash ah oo ku daray qoraalada waxbarasho kasta, diiwaanka waxa aad dhamaatay, dhibaatooyinka aad xal u tahay meel kaliya, iyo macallinka aad weydiisan kartaa oo ku saabsan bogga. Xisaabta oo keliya waa u furan yahay qof kasta, la diiwaan geliyey ama aan.
Ku soo biir Ku soo galCalaamadaha la isticmaalay halkan
Taab calaamad kasta oo loogu talagalay qeexidda buuxda, sawir, iyo waxa xarfaha oo dhan ka mid ah ka dhigan tahay.
Su'aalaha dadku waydiiyaan
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Qaybaha ee boggaan waxaa la beddelay ka Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed iyo dib-oo halkan lagu sharaxay; khaladaadka waa inoo.
In ka badan Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs