11.1 Graph Models, Representations, and Degrees

Chapter 10 studied trees: connected structures with no cycles. A tree is one special kind of graph. We now remove the no-cycle restriction so that a network may contain alternate routes, feedback loops, and dense clusters.

This section develops the language needed to describe such networks. We will first decide what vertices and edges mean, and then learn three ways to store the same graph.

Vertices and edges

A graph is an ordered pair

where $V$ is a nonempty finite set of vertices and $E$ is a set of edges. A vertex represents an object. An edge represents a relationship between two objects.

In an undirected graph, an edge has no direction. The edge between vertices $u$ and $v$ is the unordered pair

Because order does not matter, $\{u,v\}=\{v,u\}$. We may abbreviate this edge as $uv$ and write $u\sim v$ to say that $u$ and $v$ are adjacent.

Consider

The vertices $A$ and $B$ are adjacent because $AB\in E$. Vertices $A$ and $D$ are not adjacent because $AD\notin E$.

The endpoints of edge $CD$ are $C$ and $D$. An edge and either of its endpoints are said to be incident.

The graph must match the question

A graph model is useful only after its meanings are stated. Suppose four train stations are connected by direct tracks:

• a vertex represents one station;

• an undirected edge represents one direct two-way track;

• the absence of an edge means there is no direct track, not that travel is impossible through intermediate stations.

The same physical system can produce different graphs. If vertices represent train lines instead of stations, an edge might mean that two lines share a transfer station. Before calculating anything, always ask:

1. What does one vertex represent?

2. What does one edge represent?

3. Is the relationship directional?

4. Can an object relate to itself?

5. Can two objects have more than one relationship?

6. Does a number such as cost, distance, or capacity belong on each edge?

Directed graphs, loops, parallel edges, and weights

Some relationships have direction. A directed graph, or digraph, uses directed edges called arcs. An arc from $u$ to $v$ is the ordered pair

Now $(u,v)$ and $(v,u)$ are different. A webpage link, a one-way street, and a prerequisite relation are naturally directed.

An edge from a vertex back to itself is a loop. Two or more distinct edges with the same endpoints are parallel edges. A graph that allows parallel edges is often called a multigraph.

A simple undirected graph has neither loops nor parallel edges. Unless stated otherwise, most theorems in this chapter use simple undirected graphs.

A weighted graph attaches a numerical weight $w(e)$ to every edge $e$. The weight might measure distance, time, cost, risk, or capacity. Section 11.3 will use weights for shortest paths, and Section 11.4 will use them for minimum spanning trees.

These features answer different modeling needs. Direction records asymmetry; parallel edges preserve distinct relationships; loops preserve self-relations; weights record quantitative cost. None should be added merely to make a picture look realistic.

Build several networks from real-world briefs. Choose whether relationships are directed, add or remove loops and parallel links, and watch the model checker explain which information your current graph preserves or loses.

Three representations of one graph

A drawing helps people see a graph, but an algorithm needs a precise data representation. We use the same example throughout:

Edge list

An edge list stores each edge once:

It is compact and convenient when an algorithm scans every edge, as Section 11.4's Kruskal algorithm will do. Checking whether one particular edge exists may require scanning the list.

Adjacency list

For each vertex, an adjacency list stores its neighbors:

Every undirected edge appears twice, once at each endpoint. Adjacency lists are efficient for sparse graphs, where the number of edges is much smaller than the maximum possible number.

Adjacency matrix

Fix the vertex order $A,B,C,D$. The adjacency matrix is the $4\times4$ matrix $M$ defined by

For the example,

The matrix is symmetric because $M_{ij}=M_{ji}$ in an undirected graph. Its diagonal entries are $0$ because a simple graph has no loops. In a directed graph, row $i$ records arcs leaving vertex $i$, so the matrix need not be symmetric.

With $n=|V|$ vertices, an adjacency matrix uses $n^2$ positions even when few edges exist. Its advantage is that the question “is $u$ adjacent to $v$?” can be answered by one matrix lookup.

Degree counts local connections

The degree of vertex $v$, written $\deg(v)$, is the number of edges incident with $v$. A loop, when loops are allowed, contributes $2$ to the degree because both of its ends touch the same vertex.

In the example,

A vertex of degree $0$ is isolated. A vertex of degree $1$ is a pendant vertex. In a tree, pendant vertices are the unrooted version of leaves.

The adjacency representations reveal degrees directly:

• in an adjacency list, $\deg(v)$ is the length of $v$'s neighbor list;

• in a simple undirected adjacency matrix, $\deg(v)$ is the sum of the entries in $v$'s row.

The Handshake Lemma

If we add all vertex degrees in a finite undirected graph, every edge is counted exactly twice, once at each endpoint. Therefore

This identity is the Handshake Lemma. For the example,

Because the right side is even, the number of odd-degree vertices must be even. Odd numbers can sum to an even total only when an even number of them are present.

The average degree is

For a directed graph, we separate the number of incoming and outgoing arcs. The indegree $\deg^-(v)$ counts arcs ending at $v$, while the outdegree $\deg^+(v)$ counts arcs starting at $v$. Every arc contributes once to each total, so

Edit an adjacency matrix and watch the edge list, adjacency lists, graph drawing, degree sequence, and Handshake Lemma ledger update together. Switch to directed mode to separate incoming and outgoing counts.

What this section established

A graph model first states what vertices and edges mean. Direction, multiplicity, loops, and weights are deliberate modeling choices. Edge lists, adjacency lists, and adjacency matrices store the same relationships in different forms, while degree summarizes the connections touching one vertex.

Section 11.2 will stop looking at one edge at a time. It will join adjacent edges into walks, paths, and cycles, then use those routes to define connectivity.