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 in Chapter Multigraphs. A few examples are also given there.