Flow network ($(G,c,s,t)$)

A flow network is a directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$ and a nonnegative flow network edge capacity $c_{uv}$ on each directed edge $(u,v)$. In the finite setting here, every flow network edge capacity is a finite real number. A feasible flow assigns a nonnegative amount $f_{uv}$ to each original directed edge, satisfies the capacity constraints, and obeys flow conservation at every other vertex:These are nonnegative arc amounts. The antisymmetric convention in flow instead records net amounts ${\theta }_{uv}=f_{uv}-f_{vu}$, taking a missing arc amount as zero. The two conventions express the same flow conservation; keeping them distinct makes backward residual network edges easier to interpret.

Think of vertices as routers, directed edges as communication links, flow network edge capacities as available bandwidth, and flow as a steady transmission rate. An intermediate router can distribute incoming traffic among outgoing links, but flow conservation prevents it from creating traffic. The maximum flow problem asks how much total traffic can pass from $s$ to $t$, allowing several graph paths to share the work. The same flow network language models transportation and abstract resource allocation.^[ref]

Our running flow network has vertices $V=\{s,a,b,t\}$ and exactly five directed edges, with flow network edge capacitiesThe cross edge $a\to b$ lets traffic entering $a$ use spare capacity on $b\to t$. With this edge removed, the two separate graph paths can carry only $\min (3,2)+\min (2,3)=4$; including it will let the maximum flow reach $5$. Thus a link's usefulness depends on the rest of the flow network, rather than just its own flow network edge capacity.

A prescribed minimum amount on each directed edge can be removed by substituting $f_e={\ell }_e+x_e$. The new capacity constraints are $0\le x_e\le c_e-{\ell }_e$. For a circulation with vertex demands using net inflow $d_v$, the adjusted demand is $d_v^{\prime }=d_v-({\sum }_u{\ell }_{uv}-{\sum }_w{\ell }_{vw})$. Solving the adjusted problem and adding $\ell$ back gives a one-to-one correspondence of feasible solutions. In particular, removing a lower bound on $u\to v$ increases $u$'s residual demand and decreases $v$'s by that amount.

A network circulation is a flow with zero net supply at every vertex. A feasible residual network circulation changes one feasible flow into another with the same prescribed supplies. It decomposes into directed cycles, giving the negative-cycle optimality test for minimum-cost flow.

A flow on a directed graph satisfying capacity constraints and a specified net inflow $d_v$ at each vertex. Positive $d_v$ denotes consumption and negative $d_v$ supply. Summing all balances cancels each edge once as inflow and once as outflow, so ${\sum }_v{d}_v=0$ is necessary. With balanced demands and no lower bounds, add a source edge of flow network edge capacity $-d_v$ into every supply vertex and an edge of flow network edge capacity $d_v$ from each demand vertex to a new sink. A maximum flow saturating all auxiliary edges exists exactly when the demands are feasible.

An internal vertex capacity bounds the total flow through that vertex, equivalently its total inflow or outflow by flow conservation. Replace the vertex by an input and output vertex, direct incoming edges to the input and outgoing edges from the output, and connect input to output with an edge of the vertex capacity. This converts the constraint into an ordinary flow network edge capacity.

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

For a league in which every remaining game gives exactly one win, first give the target team all its remaining wins, obtaining $W$. Make a node for each unordered pair of other teams, with source capacity equal to their remaining games. Route each game-node flow to one of its two teams, and cap the team's total additional wins at $W-w_i-1$ for a strict target victory. A negative cap immediately rules out success. Otherwise an integral maximum flow saturating every game-source arc specifies the winners of all games and proves feasibility. Each actual game is counted once; duplicating ordered pairs changes the problem.

In a flow network for treatment facilities, the amount treated at a facility is represented by a directed arc from it to the sink, with that arc's capacity equal to its treatment limit. Untreated fluid may pass through the facility independently of how much is treated there. Thus the treatment limit is not a bound on total incoming flow. Flow conservation at a facility equates incoming flow with outgoing untreated flow plus its sink-arc flow.

To find the smallest link failure set separating a client from every server, add a common sink with sufficiently large-capacity server arcs and give original links unit capacities in both directions. The max-flow min-cut theorem identifies the minimum failure count $\lambda$. Unit-capacity vertex splitting also charges intermediary node failures. The network tolerates fewer than $\lambda$ failures and fails for some set of $\lambda$ failures. This concerns connection to at least one server, not separate connectivity to each server.

This maximum flow algorithm repeatedly augments along a shortest residual path found by breadth-first search. Residual distances from the source never decrease. If the same arc becomes saturated again after being restored by a reverse augmentation, the distance to its tail has increased by at least two. Thus each arc is critical only $O(|V|)$ times, yielding $O(|V||E|)$ augmentations. Each search costs $O(|E|)$, so the total time is $O(|V||E{|}^2)$. Termination with no residual source-sink path supplies a max-flow min-cut theorem certificate.

The maximum flow problem with internal vertex capacities reduces to the usual edge-capacitated problem by splitting each constrained vertex into input and output copies. The connecting edge carries its entire through-flow. Feasible flows correspond under this construction, preserving the source-to-sink value; the Ford-Fulkerson algorithm and max-flow min-cut theorem therefore apply to the transformed network.

Replace a vertex $v$ by $v_{\mathrm{in}},v_{\mathrm{out}}$ and an arc between them carrying its vertex capacity. Incoming arcs enter $v_{\mathrm{in}}$ and outgoing arcs leave $v_{\mathrm{out}}$. A path must cross that internal arc to use the vertex. This converts node-capacitated maximum flow to an ordinary flow network. For undirected mixed-failure cuts, normalize the source side so $v_{\mathrm{out}}$ inside implies $v_{\mathrm{in}}$ inside; then each original link contributes at most one crossing orientation.

A directed edge capacity is the upper bound $c_{ij}\ge 0$ on the feasible nonnegative flow through that edge. In a residual network, its forward residual capacity is $c_{ij}-f_{ij}$ and its backward residual capacity is $f_{ij}$. Increasing every edge capacity need not increase the maximum flow by that same amount, because a cut of a flow network can contain several edges.

If a directed edge $e$ has capacity $c(e)$, a feasible flow satisfies $0\le f(e)\le c(e)$. In an antisymmetric-flow convention, this is encoded together with the residual capacity of the reverse orientation.

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.

A minimum cut is a cut of a flow network of least cut capacity for the prescribed source $s$ and sink $t$. The max-flow min-cut theorem equates that least cut capacity with the greatest flow value.^[ref]

To certify a particular minimum cut, exhibit a feasible flow whose flow value equals its cut capacity. Every feasible flow is bounded above by every cut capacity, so this single equality proves both optimalities.^[ref]

In the running example, the four possible source sides $\{s\}$, $\{s,a\}$, $\{s,b\}$ and $\{s,a,b\}$ have cut capacities $5,5,6,5$, respectively. The feasible flow of flow value $5$ therefore certifies three different minimum cuts. A minimum cut need not be unique; the optimum cut capacity is the same for all of them. Merely saturating many edges does not give this certificate: flow conservation and the particular cut of a flow network must also be checked.

On $\{0,\dots ,m{\}}^2$, give an adjacent edge capacity equal to the larger endpoint distance $|i_1-i_2|$ from the diagonal. The set $S=\{i_1<i_2\}$ has $2m$ outgoing edges: two at each interior diagonal vertex and one at each endpoint. Every such edge has capacity one. Thus any flow from above to below the diagonal is at most $2m$; a feasible path decomposition attaining this value certifies optimality by weak duality.

The cut capacity of $(S,S^c)$, with $S^c=V\setminus S$ the complement of a set, isOnly outward directed edges contribute; incoming and internal edges contribute nothing.^[ref]

Here is the accounting behind the bound, using nonnegative original edge amounts $f_{uv}$ in a finite flow network. Sum the divergence of a flow over the vertices in $S$:An edge with both endpoints in $S$ appears once with a plus sign at its tail and once with a minus sign at its head, so those contributions cancel. An outward edge appears only with a plus sign; an incoming edge appears only with a minus sign. Since $s\in S$, $t\notin S$ and every other vertex satisfies flow conservation, the left side is the flow value. ThusThe inequality uses two facts separately: each forward flow is at most its flow network edge capacity, and each backward flow is nonnegative. This is the weak duality bound underlying the max-flow min-cut theorem. It is an accounting proof, requiring no choice of augmenting paths.

For $S=\{s,b\}$ in the running example, explicitly add the two divergences of a flow:The internal $s\to b$ edge cancels. The $a\to b$ edge is a genuine original directed edge entering $S$, so its flow is subtracted; this is different from a backward edge in a residual network. Its flow network edge capacity is neither added to nor subtracted from cut capacity, which remains $c_{sa}+c_{bt}=6$.

Equality in the bound holds precisely when every outward edge is saturated and every incoming edge carries zero flow, becauseand every term is nonnegative. For $S=\{s\}$ the two outward edges are saturated and there are no incoming edges, so the gap is zero. For $S=\{s,b\}$ all outward edges are still saturated, but the incoming flow of $1$ gives a gap of $1$. This explains exactly why the second cut of a flow network is not a minimum cut.

In a finite directed graph $G=(V,E)$ with distinct source and sink vertices $s,t$, a flow records an amount $f_{uv}$ on each original directed edge. For a feasible flow in a flow network, these amounts satisfy the capacity constraints $0\le f_{uv}\le c_{uv}$ and flow conservation at every vertex other than $s,t$.^[ref]

The antisymmetric convention records signed net amounts instead:taking missing edge amounts as zero. The paired signs describe one net transfer, rather than two independent transfers.^[ref]

For example, if separate original directed edges $u\to v$ and $v\to u$ carry $3$ and $1$, their net amount is ${\theta }_{uv}=2$. This signed record loses the separate amounts: $f_{uv}=2$, $f_{vu}=0$ would give the same net amount. When checking capacity constraints on actual edges, keep the original amounts or specify the signed bounds carefully; when summing flow conservation, either record gives the same divergence of a flow.

For the running flow network, choose the original edge amountsEvery capacity constraint holds. At $a$, incoming flow $3$ equals outgoing flow $1+2$; at $b$, incoming flow $2+1$ equals outgoing flow $3$. This feasible flow has flow value $5$, computed at $s$ or $t$.

The total of all five edge amounts is $11$, but the flow value is $5$. A unit passing through several edges appears several times in that total. Concretely, route $2$ units along each of the directed paths $s\to a\to t$ and $s\to b\to t$, and $1$ along $s\to a\to b\to t$. Their delivered amounts sum to $2+2+1=5$, while their edge usages sum to $2\cdot 2+2\cdot 2+1\cdot 3=11$. The cut of a flow network $S=\{s\}$ certifies that this delivery rate is already a maximum flow.

Flow conservation is useful because it makes a local ledger predict a global delivery rate: intermediate vertices only redistribute the resource. An additional network circulation can change the individual edge amounts without changing the flow value. Counting net delivery rather than total edge usage prevents such recirculation from masquerading as increased output.

A unit flow from $a$ to $b$ is an antisymmetric flow with net outward strength of a flow one at $a$, net inward strength one at $b$, and zero divergence of a flow elsewhere. For a unit flow to infinity, only the finite source has nonzero divergence.

The divergence of a flow at a vertex $v$ is net outward flow. For original nonnegative edge amounts and their signed net record, respectively,Positive divergence of a flow means net supply, negative divergence of a flow means net demand, and zero is flow conservation. This is the same sign convention as flow balance.

In the running example, the divergences of a flow at $(s,a,b,t)$ are $(5,0,0,-5)$. Adding the four divergences of a flow gives zero: every edge contributes positively at one endpoint and negatively at the other. In a finite flow network, this cancellation explains why net supply at $s$ equals net demand at $t$.

Flow conservation requires equal total inflow and outflow at every vertex other than the source and sink:Equivalently, the divergence of a flow is zero there.^[ref]

This is a steady accounting condition: an intermediate vertex neither creates the routed resource nor accumulates it. Splitting is allowed; equality between individual incoming and outgoing edges is not required. For the running flow, the equation at $a$ is $f_{sa}=f_{ab}+f_{at}$, or $3=1+2$, and at $b$ it is $f_{sb}+f_{ab}=f_{bt}$, or $2+1=3$.

Capacity constraints alone do not ensure flow conservation. For instance, changing only $f_{ab}$ from $1$ to $0$ keeps every edge amount within its flow network edge capacity, but leaves an excess inflow of $1$ at $a$ and an excess outflow of $1$ at $b$. It is therefore not a feasible flow. Changing all affected edge amounts together to $(f_{sa},f_{sb},f_{ab},f_{at},f_{bt})=(2,2,0,2,2)$ restores both equations and gives flow value $4$.

The strength of a flow, also called its flow value, is net outflow from $s$, equivalently net inflow to $t$:The notation $|f|$ denotes this signed value, rather than an absolute value.^[ref]

The equality follows by summing the divergence of a flow over all vertices: the internal vertices contribute zero by flow conservation, while every edge cancels between its two endpoints. Hence $\mathrm{div}f(s)=-\mathrm{div}f(t)$. For the running flow, $|f|=3+2=2+3=5$.

Net outflow matters even when the source has incoming edges. As a separate example, give $s\to a$, $a\to s$ and $s\to t$ flow network edge capacities $2,2,3$ and flow amounts $2,2,3$. At $a$, flow conservation reads $2=2$. The source sends $5$ units along outgoing edges but receives $2$ back, so the flow value is $5-2=3$, exactly the amount arriving at $t$. The two-edge network circulation through $a$ raises total edge usage without increasing net delivery.

For unit edge resistances, the energy of a flow iswhere every unoriented edge is counted once.

An infinite locally finite connected graph is a transient graph exactly when it supports a unit flow from a vertex to infinity with finite energy of a flow.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

In a finite flow network, a maximum flow exists because the feasible flow set contains the zero flow and is a compact set: the capacity constraints bound every coordinate, and they and flow conservation define a closed set. The strength of a flow is a continuous function, so the extreme value theorem gives an attained maximum. An augmenting path in the residual network would permit positive augmentation, contradicting maximality. The source-reachable vertices in the residual network therefore define a cut of a flow network whose outgoing original edges are saturated and incoming original edges carry zero flow. Flow conservation makes the strength of a flow equal to this cut capacity, proving the max-flow min-cut theorem.

Existence and strong duality for finite real flow network edge capacities do not imply finite termination for every choice of augmenting paths in the Ford-Fulkerson algorithm. With irrational capacities, some choices can continue forever. With integer capacities, Integrality of the Ford-Fulkerson algorithm instead forces finite termination; rational capacities reduce to that case by a common denominator. Choosing shortest augmenting paths as in the Edmonds–Karp algorithm avoids dependence on capacity magnitudes.^[ref]

If every directed edge capacity increases by $\epsilon$, a cut of a flow network with $m(S)$ outgoing edges gains $\epsilon m(S)$. By the max-flow min-cut theorem, the new maximum flow value isFor a finite flow network, this is a nondecreasing concave piecewise-linear function, and its active cut can change as $\epsilon$ varies. Two unit-capacity edge-disjoint two-edge source-to-sink paths gain $2\epsilon$, refuting an invariably exact $\epsilon$ increase. If there is a directed source-to-sink path, every cut has at least one outgoing edge and the increase is at least $\epsilon$; without a path it can be zero.

A flow network with integer capacities has a maximum flow whose value on every edge is an integer. The augmenting-path algorithm proves this because every augmentation preserves integrality.

In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. It follows by representing matching as an integral flow and vertex covers as finite-capacity cuts.

For a feasible flow $f$, each original directed edge $u\to v$ supplies a forward residual network edge of capacity $c_{uv}-f_{uv}$ and a backward one $v\to u$ of capacity $f_{uv}$; zero-capacity residual edges may be omitted. The forward edge permits an increase, while the backward edge permits cancellation of existing flow. In particular, backward residual capacity is the amount already sent, rather than unused original capacity. If both original orientations exist, keep their residual contributions separate, or add capacities for contributions with the same direction. An augmenting path uses these permitted changes while preserving flow conservation and the capacity constraints.

To see why cancellation matters, give all five directed edges $s\to a$, $s\to b$, $a\to b$, $a\to t$, $b\to t$ unit flow network edge capacities. Starting from zero flow, an augmenting path $s\to a\to b\to t$ carrying $1$ yieldsThe remaining unused original edges are $s\to b$ and $a\to t$, which do not form a source-to-sink graph path. However, the backward residual edge $b\to a$ has capacity $f_{ab}=1$. Consequently the residual network contains the augmenting path $s\to b\to a\to t$, with residual capacities $1,1,1$.

Augment by $1$: increase $f_{sb}$ and $f_{at}$ from $0$ to $1$, and decrease $f_{ab}$ from $1$ to $0$. The result isNow flow conservation is $1=0+1$ at $a$ and $1+0=1$ at $b$. The final flow sends one unit along each of $s\to a\to t$ and $s\to b\to t$. The cut of a flow network $S=\{s\}$ has cut capacity $1+1=2$, proving this is a maximum flow. Traversing $b\to a$ in the residual network revised the earlier routing decision; it did not send actual traffic along a nonexistent original edge.

For arc capacities $(c_{12},c_{13},c_{24},c_{34},c_{35},c_{46},c_{56})=(3,3,2,2,3,3,2)$, the feasible flow $(1,3,1,2,1,3,1)$ has value four. The displayed residual path has bottleneck one and traverses $4\to 3$ opposite to the original arc $3\to 4$. Augmentation cancels one unit there and gives $(2,3,2,1,2,3,2)$ of value five. The sink cut has capacity five, proving optimality. Reverse residual arcs are what permit rerouting instead of only adding flow along unused forward arcs.

For an undirected capacitated network, write the net edge flow as $y_{ij}=-y_{ji}$, and the directed residual capacity as $c_{ij}-y_{ij}$. On every source–sink cut, residual capacity is the original cut capacity minus the current net flow value $f$. Taking the minimum over cuts and applying the max-flow min-cut theorem to each network gives the displayed remaining-flow identity.

An augmenting path is a source-to-sink graph path $P$ of positive capacities in the residual network. Its bottleneck is $\Delta ={\min }_{e\in P}{c}_f(e)>0$. Add $\Delta$ to original flow on forward residual edges and subtract $\Delta$ on backward residual edges. Each internal vertex still satisfies flow conservation, and the bottleneck guarantees every capacity constraint. The resulting feasible flow has strength of a flow $|f|+\Delta$. In the unit-capacity residual network example, $\Delta =1$, and the subtraction on $a\to b$ is precisely what allows the value to rise from $1$ to $2$.

An augmenting path maximizing the possible increase in flow, namely its smallest residual network edge capacity. If the remaining maximum flow is $F>0$ and the original undirected network has $m$ edges, a path has bottleneck at least $F/m$. Otherwise the vertices reachable through arcs of capacity at least $F/m$ define a cut of capacity strictly less than $F$, contradicting the max-flow min-cut theorem. Only one directed arc per original crossing edge contributes to that cut.

Starting from zero flow, a widest augmenting path increases the current flow by at least $F_k/m$, where $F_k$ is its remaining optimality gap. Therefore $F_{k+1}\le (1-1/m)F_k$. Integer capacities keep this gap integer, so a gap below one is zero. The method takes $O(m\log f^{\ast })$ augmentations for $f^{\ast }\ge 2$, or uniformly $O(m\log (1+f^{\ast }))$; zero maximum flow requires no augmentation.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

Starting from the zero flow with integer capacities, every residual capacity and every augmenting bottleneck is an integer. Each augmentation therefore preserves integer edge flows and raises the flow value by at least one. Since the value is bounded by the total capacity leaving the source, the algorithm terminates after finitely many augmentations with an integral maximum flow.

If one edge leaving the source has capacity $x$, every cut capacity is affine in $x$ with coefficient zero or one. In the 2024 Cambridge Part IB example, cuts of capacities $x+5$ and $14$ are both sharp, giving