EF Adding information to graphs

🔗

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),$ where $(V, E)$ is an ordinary graph and $w : E \to 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.

$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),$ 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