Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Walk and Path

Definitions from the module sheet, for a graph and vertices :

  • a walk from to is an alternating sequence with , and each edge joining and
  • the length of a walk is (the number of edges), or the sum of edge weights if is weighted
  • a path is a walk that does not pass through any vertex twice
  • a cycle is a walk that starts and ends at the same vertex and passes through no other vertex twice, so no edge is repeated

Example: is a cycle, but is not, because it reuses edge .

Subgraph

is a subgraph of if every vertex and every edge of is also in , i.e. and .

Connectivity

Definitions:

  • and are connected if there is a walk (equivalently a path) between them, since any walk that repeats a vertex can be shortened into a path
  • a graph is connected if every pair of distinct vertices is connected, otherwise it is disconnected
  • a connected component is a connected subgraph that cannot be extended to a larger connected subgraph
  • a graph has exactly one component if and only if it is connected

Trees in Graph Theory

A tree is a connected graph with no cycles. A tree with vertices always has edges (proof not required). A rooted tree is a tree in this sense, with one edge from each node to each of its children.

From left to right: the first graph is not a tree because form a cycle, and the last is not a tree because vertex is not connected. Trees lead directly to Spanning Trees.

Distance and Shortest Path

In a weighted undirected graph with non-negative weights, the distance from to is the minimum length of a path from to ( if there is none), and a shortest path is a path with that length.