Transportation network (graph theory)
- Transportation network (graph theory)
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).
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".
ee also
* Spatial network
* graph theory
Wikimedia Foundation.
2010.
Look at other dictionaries:
Transportation network — may refer to:* Transport network, physical infrastructure * Transportation network (graph theory), the mathematical graph theory … Wikipedia
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 … Wikipedia
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.A transport… … Wikipedia
Flow network — In graph theory, a flow network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in Operations Research, a directed graph is called a… … Wikipedia
Spatial network — A spatial network is a network of spatial elements . In physical space (which typically includes urban or building space) spatial networks are derived from maps of open space within the urban context or building. One might think of the space map… … Wikipedia
List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie … Wikipedia
Peak oil — A logistic distribution shaped production curve, as originally suggested by M. King Hubbert in 1956 … Wikipedia
Shortest path problem — A graph with 6 vertices and 7 edges In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. An example is… … Wikipedia
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Operations research — For the academic journal, see Operations Research: A Journal of the Institute for Operations Research and the Management Sciences. Operations research (also referred to as decision science, or management science) is an interdisciplinary… … Wikipedia
