labelled digraph

A triple $(V,E,w)$ is called a labelled digraph, if $(V,E)$ is adigraph and $w$ is an association of elements from some set $L$, thelabels, to some of the edges and vertices of the digraph. Inother words, $w$ is a mapping from a subset $A\subseteq V\cup E$ to$L$. Most often, $L$ is a subset of the real numbers, in which case$(V,E,w)$ is called a weighted digraph and its labels arecalled weights. Typically, either $A=V$ or $A=E$, in which case$(V,E,w)$ is called either a vertex-weighted digraph or anedge-weighted digraph, respectively.

Application examples

We give two typical “real life” examples. The first features anedge-weighted digraph, while the second requires the implementation ofa vertex-weighted digraph.

Railway network

A railway network consists of railway stations connected by rails. Atrain needs a certain time (measured in minutes) to fare from onestation to another. In a formalisation, $V$ is the set of trainstations, $E$ the set of direct connexions between them and $w:E\to \mathbb{N}$ a weighting corresponding to the journey times, so$(V,E,w)$ is an edge-weighted digraph. Although typically $(V,E)$ is ahttp://planetmath.org/node/1702symmetric digraph, $w$ does not need to be symmetric: for example, thejourney from $a$ to $b$ might take longer than the return journeybecause $b$ is located on a mountain.

An important optimisation problem is the efficient determination ofthe fastest way from one station to another. An even harder problem isto find the fastest round trip (usually called a tour) via agiven number of stations. This is the travelling salesmanproblem.

Dependency graph

A software bundle consists of a number of packages each of which iseither installed or not. An installed package occupies a certainamount of bytes on a storage medium. Packages may depend on otherpackages, that is installation of a package may require other packagesto be installed first, which in turn may require still other packagesand so forth. One is interested in the complete storage requirementincurred by the installation of one package and all its dependencies.

In a formalisation, the packages are vertices of a digraph $(V,E)$, and anedge $(a,b)\in E$ means “$a$ depends on $b$”. Such a digraph is typicallynot symmetric. The weighting $w:V\to \mathbb{N}$ associates sizes topackages. A subset $W$ of $V$ is dependency-closed, if for any$w\in W$, all dependencies of $w$ are in $W$. Given a to-be-installedpackage $v$, the storage requirement incurred by the installation of$v$ and all its dependencies is the sum of the vertex weights of thesmallest dependency-closed subset of $V$ containing $v$.

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