Transportation network (graph theory)
Encyclopedia
A transportation network is a type of directed, weighted graph or network
Network diagram
A computer network diagram is a schematic depicting the nodes and connections amongst nodes in a computer network or, more generally, any telecommunications network.-Symbolization:...

.

Transportation networks are used to model the flow of commodity
Commodity
In economics, a commodity is the generic term for any marketable item produced to satisfy wants or needs. Economic commodities comprise goods and services....

, information
Information
Information in its most restricted technical sense is a message or collection of messages that consists of an ordered sequence of symbols, or it is the meaning that can be interpreted from such a message or collection of messages. Information can be recorded or transmitted. It can be recorded as...

, or traffic
Traffic
Traffic on roads may consist of pedestrians, ridden or herded animals, vehicles, streetcars and other conveyances, either singly or together, while using the public way for purposes of travel...

(see transport network
Transport network
A transport network, or transportation network in American English, is typically a network of roads, streets, pipes, aqueducts, power lines, or nearly any structure which permits either vehicular movement or flow of some commodity....

).

In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection Transportation Planning Volume I for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".

## Definitions

A transportation network G is a graph with
• Exactly one vertex
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

of in-degree 0 (no incoming edges
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

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
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

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.