labelled digraph
A triple is called a labelled digraph, if is a
digraph and is an association of elements from some set , the
labels, to some of the edges and vertices of the digraph. In
other words, is a mapping from a subset to
. Most often, is a subset of the real numbers, in which case
is called a weighted digraph and its labels are
called weights. Typically, either or , in which case
is called either a vertex-weighted digraph or an
edge-weighted digraph, respectively.
Application examples
We give two typical “real life” examples. The first features an edge-weighted digraph, while the second requires the implementation of a vertex-weighted digraph.
Railway network
A railway network consists of railway stations connected by rails. A
train needs a certain time (measured in minutes) to fare from one
station to another. In a formalisation, is the set of train
stations, the set of direct connexions between them and a weighting corresponding to the journey times, so
is an edge-weighted digraph. Although typically is a
http://planetmath.org/node/1702symmetric
digraph, does not need to be symmetric: for example, the
journey from to might take longer than the return journey
because is located on a mountain.
An important optimisation problem is the efficient determination of the fastest way from one station to another. An even harder problem is to find the fastest round trip (usually called a tour) via a given number of stations. This is the travelling salesman problem.
Dependency graph
A software bundle consists of a number of packages each of which is
either installed or not. An installed package occupies a certain
amount of bytes on a storage medium. Packages may depend on other
packages, that is installation of a package may require other packages
to be installed first, which in turn may require still other packages
and so forth. One is interested in the complete storage requirement
incurred by the installation of one package and all its dependencies.
In a formalisation, the packages are vertices of a digraph , and an edge means “ depends on ”. Such a digraph is typically not symmetric. The weighting associates sizes to packages. A subset of is dependency-closed, if for any , all dependencies of are in . Given a to-be-installed package , the storage requirement incurred by the installation of and all its dependencies is the sum of the vertex weights of the smallest dependency-closed subset of containing .
Title | labelled digraph |
Canonical name | LabelledDigraph |
Date of creation | 2013-03-22 15:15:07 |
Last modified on | 2013-03-22 15:15:07 |
Owner | GrafZahl (9234) |
Last modified by | GrafZahl (9234) |
Numerical id | 4 |
Author | GrafZahl (9234) |
Entry type | Definition |
Classification | msc 05C20 |
Classification | msc 05C12 |
Classification | msc 05C78 |
Classification | msc 05C90 |
Defines | label |
Defines | weighted digraph |
Defines | weight |
Defines | vertex-weighted digraph |
Defines | edge-weighted digraph |