# Labelled, Capacitated and Weighted Graphs

A vertex labelling of a graph $G$ is a partial map $f$ from the vertex-set $V$ of $G$ into a set $L$. An edge labelling of a graph $G$ is a partial map $f$ from the edge-set $E$ of $G$ into a set $L$. A labelled graph is built by assigning labels successively to vertices or edges after the (unlabelled) graph has been constructed.

Similarly, a capacitated graph $G$ is a partial map from its edge-set into $Z^+$, and a weighted graph $G$ is a partial map from its edge-set into $R$, $R$ any ring with a total order. Those two last features are particularly convenient when running shortest-paths and flow algorithms. Edge capacities and edge weights are assigned to edges once the graph has been constructed. Any graph edge may carry a label, together with a capacity and/or a weight.

All the functions for decorating graph vertices and edges are fully documented in Section [Vertex and Edge Decorations](../Multigraphs/multig-decorations.md#multigraph-sec-decs) in Chapter [Multigraphs](../Multigraphs/index-multigraphs.md#multigraph). A few examples are also given there.