Skip to main content
Logo image

Section 14.3 Adding information to graphs

weighted graph (working definition)
a graph in which each edge is assigned a weight or cost, usually a numerical value
weighted graph (formal definition)
an ordered triple \((V,E,w)\text{,}\) where \((V,E)\) is an ordinary graph and \(\funcdef{w}{E}{W}\) is a function with some set \(W\) as codomain
weights
elements of the image \(w(E) \subseteq W\)
We usually label each edge with its weight on diagrams for the graph.

Example 14.3.1. A road map weighted by distances.

A road map with distances as weights is a weighted graph. Below is a simplified road map of the area around Camrose, Alberta. The vertex set is the set of cities, and the edge set is the set of highways. For example, the two-city set {Camrose, Edmonton} represents the edge on the graph between Camrose and Edmonton, and corresponds to Highway 21.
Road map of the area around Camrose, Alberta.
Figure 14.3.2. Road map of the area around Camrose, Alberta.
\(e\) \(w(e)\)
{Camrose, Edmonton} \(94\)
{Edmonton, Leduc} \(35\)
{Leduc, Wetaskiwin} \(35\)
{Wetaskiwin, Camrose} \(40\)
Figure 14.3.3. Table of values for distance weight function.
The edges in the graph are weighted by the (rounded) highway distances between cities. Formally, this is a function \(w\) from the edge set to the natural numbers. The input-output relationship defining this function is tabulated above right.

Example 14.3.4.

Variations on Example 14.3.1 include any kind of transportation or communication network with transportation/communication lines as edges. Possible weights assigned to an edge include: length of the line; amount of time it takes a vehicle/message to travel along the line from one node to the next; capacity of the line in vehicles/passengers/messages/data per unit time; etc..
directed graph (working definition)
a graph in which each edge can be given a direction, “pointing” to one of its incident vertices
directed graph (formal definition)
an ordered pair \((V,E)\text{,}\) where \(V\) is a finite set and \(E\) is an unordered, possibly empty list of elements of \(V \times V\)
Again, elements of \(V\) are the vertices and elements of \(E\) are the edges of the graph. For an ordinary graph, edges were represented by subsets of \(V\) because when specifying an edge, the order of the vertices which are to be incident to the edge is irrelevant. For a directed graph, the order of the vertices incident to an edge now matters, so we use ordered pairs of vertices to specify an edge. If \(e = (v,v') \in E\) for some \(v,v' \in V\text{,}\) consider the direction of \(e\) to be \(v \to v'\text{.}\)

Example 14.3.5. A basic directed graph.

Consider
\begin{gather*} V = \{ v_1, v_2, v_3, v_4 \}, \\ E = \{ (v_1,v_2), (v_1,v_2), (v_2,v_3), (v_3,v_2), (v_4,v_3), (v_4,v_4) \}. \end{gather*}
We draw the graph \(G = (V,E)\) with arrows to indicate the direction of edges.
Diagram for a basic directed graph.
Figure 14.3.6. Diagram of the directed graph \(G = (V,E)\text{.}\)

Checkpoint 14.3.7.

Invent a formal definition for directed, weighted graph.