D1 2.1 - Graphs and network matrices

Vertices edges degree paths and cycles

Can two pictures describe the same connections even when one looks completely different? Yes: the connections and their labels matter, not the positions of the dots or the lengths drawn on the page.

Here the weights could be connection costs. There is an edge from $B$ to $D$ with weight $3$, but no direct edge from $A$ to $D$. A crossing of drawn edges is not an extra vertex unless a vertex is marked there.

[DIAGRAM: asset_name: Five vertices and seven weighted edges; asset_slug: graph-language-network; caption: The labels give weights; the drawing's lengths do not.; description: An undirected network has vertices A B C D E and edges AB 6, AC 7, BC 2, BD 3, CD 1, CE 8 and DE 4. No other edges are present.]

The degree, or valency, of a vertex is the number of edges incident to it. At $C$, four edges meet: $AC,BC,CD,CE$, so its degree is $4$. Degrees of $A,B,C,D,E$ are $2,3,4,3,2$: $B,D$ are odd vertices and the others are even. The sum is $14$, twice the seven edges, because each edge contributes once at each end.

A walk follows a sequence of adjoining edges and may repeat vertices or edges. A path follows adjoining edges with no repeated vertex. A cycle, also called a circuit, returns to its start without repeating any other vertex. In the picture:

• $A,B,D,E$ is a path, using $AB,BD,DE$.
• $A,B,C,A,B$ is a walk but not a path: it repeats vertices and the edge $AB$.
• $A,B,C,A$ is a cycle: only the first/last vertex repeats.

A tour is a walk which visits every vertex and returns to its start. For example, $A,B,D,E,C,A$ is a tour here. A cycle need not visit every vertex, and a tour is allowed to repeat vertices and edges. Keep these terms distinct.

Edges with an indicated direction produce a digraph. Follow their arrows: an arc from $A$ to $B$ does not imply one from $B$ to $A$. Our pictured network is undirected, so either direction is allowed.

Use the supplied connections rather than guessing from the names.

Connected graphs trees and spanning trees

Keeping every vertex does not necessarily keep every connection, and a tree deliberately excludes cycles.

Two vertices are connected if a path joins them, possibly through other vertices. A graph is connected when every pair of its vertices is connected; direct edges between every pair are not needed. A complete graph does have a direct edge between every pair of distinct vertices. The five-vertex picture above is connected but not complete: for example, $A$ and $E$ connect through other vertices but have no direct edge.

For the earlier network, retain only $AB,BC,CD,DE$. These four edges join all five vertices in a chain without a cycle, so they form a spanning tree. Retaining $AB,BC,AC$ instead would create a cycle and leave $D,E$ disconnected: it is a subgraph, but not a spanning tree.

[DIAGRAM: asset_name: A connected graph, its spanning tree and a disconnected subgraph; asset_slug: networks-and-trees; caption: A spanning tree keeps every vertex and enough edges to connect them without a cycle.; description: Three panels use vertices A B C D E. The first is the seven-edge connected network. The second retains AB BC CD DE as a spanning tree. The third retains AB AC BC DE, forming a triangle on A B C separated from D E. The last has four edges but is not a tree.]

A tree on $n$ vertices has $n-1$ edges. To see why, start with one vertex. Each new vertex needs one edge to attach it; adding an extra edge between already connected vertices creates a cycle. Connecting the other $n-1$ vertices therefore needs $n-1$ edges. There is exactly one path between any two vertices in a tree; two different paths would form a cycle.

Counting $n-1$ edges alone is insufficient. The last panel also has four edges and five vertices, but it is disconnected and contains a cycle. For a proposed spanning tree, check the vertices, connectivity and absence of cycles together.

A minimum spanning tree, or minimum connector, is a spanning tree with the smallest possible total weight. Many different spanning trees may exist; “spanning” alone makes no claim about their weight.

Use both defining conditions in this check.

Weighted adjacency matrices

A weighted adjacency matrix records the direct connections in a table with matching vertex labels on its rows and columns.