# graph.maxflow

##### Maximum flow in a network

In a graph where each edge has a given flow capacity the maximal flow between two vertices is calculated.

- Keywords
- graphs

##### Usage

```
graph.maxflow(graph, source, target, capacity=NULL)
graph.mincut(graph, source=NULL, target=NULL, capacity=NULL)
```

##### Arguments

- graph
- The input graph.
- source
- The id of the source vertex.
- target
- The id of the target vertex (sometimes also called sink).
- capacity
- Vector giving the capacity of the edges. If this is
`NULL`

(the default) then the`capacity`

edge attribute is used.

##### Details

`graph.maxflow`

calculates the maximum flow between two vertices
in a weighted (ie. valued) graph. A flow from `source`

to
`target`

is an assignment of non-negative real numbers to the
edges of the graph, satisfying two properties: (1) for each edge the
flow (ie. the assigned number) is not more than the capacity of the
edge (the `capacity`

parameter or edge attribute), (2) for every
vertex, except the source and the target the incoming flow is the same
as the outgoing flow. The value of the flow is the incoming flow of
the `target`

vertex. The maximum flow is the flow of maximum
value.

`graph.mincut`

calculates the minimum st-cut between two vertices
in a graph (if the `source`

and `target`

arguments are
given) or the minimum cut of the graph (if both `source`

and
`target`

are `NULL`

).

The minimum st-cut between `source`

and `target`

is the
minimum total weight of edges needed to remove to eliminate all paths from
`source`

to `target`

.

The minimum cut of a graph is the minimum total weight of the edges
needed to remove to separate the graph into (at least) two
components. (Which is to make the graph *not* strongly connected
in the directed case.)
The maximum flow between two vertices in a graph is the same as the minimum
st-cut, so `graph.maxflow`

and `graph.mincut`

essentially
calculate the same quantity, the only difference is that
`graph.mincut`

can be invoked without giving the `source`

and `target`

arguments and then minimum of all possible minimum
cuts is calculated.

##### Value

- A numeric constant, the maximum flow, or the minimum cut.

##### References

A. V. Goldberg and R. E. Tarjan: ``A New Approach to the Maximum Flow Problem'' Journal of the ACM 35:921-940, 1988.

##### See Also

*Documentation reproduced from package igraph, version 0.4.4, License: GPL version 2 or later (June, 1991)*