## You are here

Homelabelled digraph

## Primary tabs

# labelled digraph

A triple $(V,E,w)$ is called a *labelled digraph*, if $(V,E)$ is a
digraph and $w$ is an association of elements from some set $L$, the
*labels*, to some of the edges and vertices of the digraph. In
other 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 are
called *weights*. Typically, either $A=V$ or $A=E$, in which case
$(V,E,w)$ 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, $V$ is the set of train stations, $E$ the set of direct connexions between them and $w\colon 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 a symmetric digraph, $w$ does not need to be symmetric: for example, the journey from $a$ to $b$ might take longer than the return journey because $b$ is located on a mountain.

# 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 $(V,E)$, and an
edge $(a,b)\in E$ means “$a$ depends on $b$”. Such a digraph is typically
not symmetric. The weighting $w\colon V\to\mathbb{N}$ associates sizes to
packages. 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-installed
package $v$, the storage requirement incurred by the installation of
$v$ and all its dependencies is the sum of the vertex weights of the
smallest dependency-closed subset of $V$ containing $v$.

## Mathematics Subject Classification

05C20*no label found*05C12

*no label found*05C78

*no label found*05C90

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections