vertices and edges, representations, walks and connectivity, trees, traversal, shortest paths, Eulerian paths, complexity, centrality
0.GR.01
Graphs, vertices and edges
Statement
A graph G = (V, E) is a set of vertices and a set of edges between them. An edge is unordered in an undirected graph and ordered in a directed one; it may carry a weight, a label, or both.
Shape check
|V| = n vertices and |E| = m edges. A simple undirected graph has m ≤ n(n−1)/2; a complete one attains it.
Worked line
Four proteins with three binding pairs: n = 4, m = 3. The same four with every pair binding: m = 6.
Almost every object in Books VI and VII is a graph, and so is the computational graph of I.6. The word means the same thing in all of them; only the interpretation of an edge changes — regulation, binding, catalysis, comorbidity, or the flow of a partial derivative.
An adjacency matrix A has A_ij = 1 when an edge joins i to j, and is n×n. An adjacency list stores, for each vertex, only its neighbours, and occupies O(n + m). An incidence matrix is n×m over vertices and edges.
Shape check
A is n×n and symmetric exactly when the graph is undirected. The degree matrix D is diagonal with D_ii = Σ_j A_ij.
Worked line
A path on three vertices has A = [[0,1,0],[1,0,1],[0,1,0]], degrees (1, 2, 1), and an adjacency list of total length 4.
The choice is not cosmetic. A biological network with 10⁶ nodes and 10⁷ edges is 10¹² entries as a matrix and 10⁷ as a list, which is the difference between running and not.
Used byI.14 · VII.7 · VII.9
0.GR.03
Walks, paths, cycles and connectivity
Statement
A walk is any sequence of adjacent vertices; a trail repeats no edge; a path repeats no vertex. A cycle is a closed path. Two vertices are connected when a path joins them, and a connected component is a maximal set of mutually connected vertices.
Shape check
A path visiting k vertices has k−1 edges. A graph on n vertices with fewer than n−1 edges cannot be connected.
Worked line
In a path graph a–b–c–d, a to d is a path of length 3. Deleting b leaves two components, {a} and {c, d}.
Connectivity is the first question asked of any biological network, and the distinction between a walk and a path is what separates a random-walk embedding from a shortest-path distance.
Used byVI.2 · VII.7 · VII.10
0.GR.04
Trees and spanning trees
Statement
A tree is a connected acyclic graph; on n vertices it has exactly n−1 edges, and between any two vertices there is exactly one path. A spanning tree of G is a tree using all of G's vertices; a minimum spanning tree minimises total edge weight.
Shape check
n vertices, n−1 edges, one unique path per pair. Adding any edge to a tree creates exactly one cycle.
Worked line
Four vertices in a square with unit weights: any three of the four edges form a spanning tree of weight 3.
A phylogeny is a tree, and the uniqueness of the path between two leaves is what makes an evolutionary distance well defined. Where that uniqueness fails, the object is a network — which is the subject of VII.8.
Used byVII.8
0.GR.05
Breadth-first and depth-first search
Statement
Breadth-first search visits vertices in order of increasing edge distance from a source, using a queue. Depth-first search follows one branch to exhaustion before backtracking, using a stack. Both run in O(n + m) on an adjacency list.
Shape check
Each vertex is enqueued once and each edge examined at most twice, giving the O(n + m) bound.
Worked line
From a in the path a–b–c–d, BFS visits a, b, c, d at distances 0, 1, 2, 3. On an unweighted graph BFS order is shortest-path order.
BFS gives shortest paths for free when every edge costs the same, which is why the weighted case in 0.GR.06 needs a different algorithm rather than a bigger queue.
0.GR.06
Shortest paths
Statement
Dijkstra's algorithm finds shortest paths from one source in O(m log n) when every weight is non-negative. Bellman–Ford allows negative weights, runs in O(nm), and detects negative cycles. Floyd–Warshall gives all pairs in O(n³).
Shape check
One source gives a vector of n distances; all pairs give an n×n matrix.
Worked line
a→b = 1, b→c = 1, a→c = 5. Dijkstra returns 2 for a→c, by way of b.
Sequence alignment is a shortest path through a grid whose edges are match, mismatch and gap. That is the whole content of the dynamic programme in VII.7, stated in this vocabulary.
Used byVII.7
0.GR.07
Eulerian and Hamiltonian paths
Statement
An Eulerian path uses every edge exactly once, and exists in a connected graph exactly when zero or two vertices have odd degree. A Hamiltonian path uses every vertex exactly once, and deciding whether one exists is NP-complete.
Shape check
Eulerian: a condition on degrees, checkable in O(n + m). Hamiltonian: no such condition is known.
Worked line
A triangle has all degrees 2, so an Eulerian circuit exists. Adding one pendant edge makes two vertices odd — a path, not a circuit.
This pair is why genome assembly moved from overlap graphs to de Bruijn graphs. Assembly over an overlap graph is Hamiltonian and intractable; over a de Bruijn graph it is Eulerian and linear. Same biology, different graph.
Used byVII.7
0.GR.08
Complexity: P, NP, and why some problems are hard
Statement
P is the class of problems solvable in polynomial time; NP is the class whose solutions are verifiable in polynomial time. An NP-hard problem is at least as hard as every problem in NP, so no polynomial algorithm is known for any of them.
Shape check
Polynomial in the input size, which for a graph means in n and m rather than in the number of possible subgraphs.
Worked line
Checking whether a given vertex ordering is a Hamiltonian path takes O(n). Searching all orderings takes n!, which at n = 20 is 2.4 × 10¹⁸.
Maximum parsimony, multiple sequence alignment, and Hamiltonian assembly are all NP-hard. Every practical tool for them is a heuristic, and knowing that is what stops a reader treating its output as an answer.
Used byVII.7 · VII.8
0.GR.09
Centrality and community structure
Statement
Degree centrality counts a vertex's neighbours. Betweenness counts the shortest paths passing through it. Eigenvector centrality gives the leading eigenvector of A, scoring a vertex by the scores of its neighbours. A community is a vertex set denser within than between.
Shape check
Centrality is a vector of length n; a partition into communities is an assignment of each vertex to one group.
Worked line
In a star with four leaves, the centre has degree 4 and betweenness 6; every leaf has degree 1 and betweenness 0.
A hub in a protein network and a hub in a comorbidity network are the same statistic about different claims. The arithmetic transfers between them; the interpretation does not.