---
title: "Labelled, Capacitated, and Weighted Graphs"
canonical: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/labels.html"
source: "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/labels.md"
part: "Combinatorics"
chapter: "Graphs"
breadcrumbs:
  - {"title": "Magma Handbook", "source": "https://docs.magma-maths.org/v2.30-1/index.md"}
  - {"title": "Combinatorics", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/index-combinatorics.md"}
  - {"title": "Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/index-graphs.md"}
prev: {"title": "The Vertex–Set and Edge–Set of a Graph", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/vertex-edge-set.md"}
next: {"title": "Standard Constructions for Graphs", "source": "https://docs.magma-maths.org/v2.30-1/Combinatorics/Graphs/operation.md"}
---

<a id="labels"></a>
<a id="graph-sec-labels"></a>
# 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](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/multig-decorations.md#multigraph-sec-decs) in Chapter [Multigraphs](https://docs.magma-maths.org/v2.30-1/Combinatorics/Multigraphs/index-multigraphs.md#multigraph). A few examples are also given there.
