|
[____]
Networks are an essential tool in modelling communication systems
and dependence problems. A network is generally defined as a directed
graph whose arcs are associated with a cost and a capacity; it may
have multiple (i.e., parallel) edges.
The fundamental network flow problem is the minimum cost flow problem,
that is, determining a maximum flow at minimum cost from
a specified source to a specified sink.
Specializations of this problem are the shortest path problem
(where there is no capacity constraint) and the maximum flow problem
(where there is no cost constraint).
Some of the related problems are the minimum spanning tree problem
(finding a spanning tree whose sum of the costs of its arcs is
minimum),
the matching problem (a pairing of the edges of the graph
according to some criteria), and the multicommodity flow problem
(where arcs may carry several flows of different nature).
For a comprehensive monograph on networks, their implementation
and applications, see [AMO93].
For convenience we provide users with the
Magma network object with type GrphNet.
It differs from the Magma multidigraph object having type
GrphMultDir in one respect only:
its edges are always assumed to be capacitated.
The edges of a network have a capacity of one by default,
unless they are specifically assigned a capacity.
The loops in a network always have capacity zero.
Since networks are a specialisation of multidigraphs, all
the functions applying to multidigraphs also apply to networks.
Below we outline those few functions that specifically concern
networks, namely, their construction.
[Next][Prev] [Right] [____] [Up] [Index] [Root]
|