14.3: Adding Information to Graphs

Definition: Weighted Graph(Working Definition)

a graph in which each edge is assigned a weight or cost, usually a numerical value

Definition: Weighted Graph(Formal Definition)

an ordered triple $(V,E,w)\text{,}$ where $(V,E)$ is an ordinary graph and $w: E \rightarrow W$ is a function with some set $W$ as codomain

Definition: Weights

elements of the image $w(E) \subseteq W$

We usually label each edge with its weight on diagrams for the graph.

Example $\PageIndex{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.

Figure $\PageIndex{1}$: Road map of the area around Camrose, Alberta.

Table $\PageIndex{1}$: Table of values for distance weight function.

$e$	$w(e)$
{Camrose, Edmonton}	$94$
{Edmonton, Leduc}	$35$
{Leduc, Wetaskiwin}	$35$
{Wetaskiwin, Camrose}	$40$

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 $\PageIndex{2}$

Variations on Example $\PageIndex{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..

Definition: Directed graph (working definition)

a graph in which each edge can be given a direction, “pointing” to one of its incident vertices

Definition: 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 $\PageIndex{1}$: 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.

Figure $\PageIndex{1}$: Diagram of the directed graph $G = (V,E)\text{.}$

Checkpoint $\PageIndex{1}$

Invent a formal definition for directed, weighted graph.