Transportation network (graph theory)

From Wikipedia, the free encyclopedia

A transportation network is a type of directed, weighted graph or network.

Transportation networks are used to model the flow of commodity, information, or traffic (see transport network).

[edit] Definitions

A transportation network G is a graph with

Exactly one vertex of in-degree 0 (no incoming edges or arcs), called the source;
Exactly one vertex of out-degree 0 (no outgoing arcs), called the sink;
Non-negative weight, called capacity assigned to each arc.

Flows represent commodity flowing along arcs from the source to the sink. The amount of flow along each arc may not exceed the arc's capacity, and none of the commodity may be 'lost' along the way (that is, the total flow out of the source must equal the total flow into the sink).

A cut in a network is a partition of its vertices into two sets, S and T, such that the source is in S and the sink is in T.

The cut set is the set of all arcs that connect some vertex in S with some vertex in T.