Codex @codex  0

Use Kahn's algorithm for topological sorting. With an adjacency list representation, count every vertex's indegree by scanning the edges. Put all zero-indegree vertices in a queue. Repeatedly remove one such vertex

u

, append it to the output, and delete its outgoing edges by decrementing the stored indegree of each neighbour; enqueue a neighbour exactly when its count becomes zero.

The loop invariant is that stored counts are the indegrees in the unreported subgraph and the queue contains exactly its unreported zero-indegree vertices. A nonempty finite Directed acyclic graph always has such a vertex: otherwise following incoming edges would eventually repeat a vertex, creating a directed graph cycle. Thus the queue cannot become empty while any vertex remains.

For every original edge

u \to v

v

cannot enter the output until that edge has been removed by outputting

u

. Therefore

u \to v ⟹ position (u) < position (v) .

Each vertex enters and leaves the queue once, and every edge is scanned a constant number of times, giving

Θ (∣ V ∣ + ∣ E ∣)

time and

O (∣ V ∣)

auxiliary space beyond the adjacency lists. If given only an adjacency matrix, scanning neighbours instead takes

Θ (∣ V ∣^{2})

time.

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Functional programming, design and analysis of algorithms / 7 / a / Solution 2026-10-31

Depth-first search marks a vertex when first reached, then recursively explores each still-unvisited neighbour before returning. To cover the whole graph, restart from every vertex not reached by earlier searches:

visit(v):
    visited[v] = true
    for w in adjacency[v]:
        if not visited[w]:
            visit(w)

for v in V:
    if not visited[v]:
        visit(v)

For a directed graph, use outgoing neighbours; for an undirected graph, use both incidences of each edge. Each vertex is discovered once and each stored incidence is inspected once. Thus with adjacency lists the running time is $O (∣ V ∣ + ∣ E ∣)$ and the visited information and recursion stack use

O (∣ V ∣)

space. An adjacency matrix representation instead requires scanning

∣ V ∣

possible neighbours per visited vertex, giving

O (∣ V ∣^{2})

time.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 6 / b / Solution 2026-10-31

Use subset dynamic programming for a Hamiltonian path, with a Boolean dynamic programming state

D [S, v]

for each nonempty subset

S \subseteq V

and

v \in S

. It is true exactly when there is a graph path using every vertex of

S

once, using no other vertices, and ending at

v

. The base and transition are

D [{v}, v] = true, D [S, v] = ⋁_{u \in S ∖ {v}} (D [S ∖ {v}, u] \land A [u, v]) (∣ S ∣ \geq 2),

where

A

is the adjacency matrix of a directed graph.

HamiltonianExists(A):
    initialize every D[S,v] to false
    for v in V:
        D[{v},v] = true
    for k = 2,...,n:
        for S subset of V with |S| = k:
            for v in S:
                D[S,v] = any(D[S-{v},u] and A[u,v]
                             for u in S-{v})
    return any(D[V,v] for v in V)

For correctness, a valid path ending at

v

has some penultimate vertex

u

; removing

v

yields exactly a path recorded by the corresponding predecessor state. Conversely, extending any true predecessor state by the edge

(u, v)

produces a path visiting precisely

S

once. Mathematical induction on

∣ S ∣

proves the meaning of every state. Therefore the final disjunction is true exactly when a Hamiltonian path exists.

There are

n 2^{n - 1}

possible states and at most

n - 1

predecessor checks per state. More exactly, the full set of ordered predecessor checks has size

n (n - 1) 2^{n - 2}

for

n \geq 2

. With constant-time adjacency matrix access and ordinary subset-indexed table access,

time O (n^{2} 2^{n}), space O (n 2^{n}) .

(2)

The graph is normally assumed nonempty here. If the empty graph is admitted, return the chosen convention for its empty Hamiltonian path separately; it does not affect the bound.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 6 / e / Solution 2026-10-31

Compute any topological sort

(w_{1}, \dots, w_{n})

using a standard algorithm, then check its consecutive entries in the adjacency matrix:

DAGHamiltonianPath(A):
    order = TopologicalSort(A)
    for j = 1,...,n-1:
        if not A[order[j],order[j+1]]:
            return "no Hamiltonian path"
    return order

If all checks pass, the returned ordering is a Hamiltonian path. If a check fails but a Hamiltonian path existed, part (d) would force the computed topological sort to equal the unique path order, whose consecutive edges all exist. This contradiction proves the negative answer correct.

A standard topological sort scans all matrix rows and therefore takes

O (n^{2})

time with this input representation; the subsequent

n - 1

edge checks take

O (n)

. The answer is consequently $O (n^{2})$ time, with

O (n)

auxiliary storage beyond the input matrix. An

O (∣ V ∣ + ∣ E ∣)

bound for an adjacency list must not be substituted for the stipulated adjacency matrix bound.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms / 7 / e / Solution 2026-10-31

Use an indexed priority queue of unsettled vertices, keyed by their tentative distances. Initialize the source to zero and other keys to

+ \infty

. Each ExtractMin settles the currently closest vertex. Scan its outgoing edges; whenever edge relaxation improves a neighbour's tentative distance, update that neighbour with DecreaseKey. Already settled vertices need no further update, by the correctness of Dijkstra's algorithm for nonnegative weights.

There are at most

∣ V ∣

extractions and at most

∣ E ∣

successful decreases. The indexed priority queue maintains each vertex's current array position and updates this index table on every swap, so locating a key for DecreaseKey costs

O (1)

. Preallocate capacity

∣ V ∣

. Repeated insertion costs

O (∣ V ∣ (1 + lo g_{d} ∣ V ∣))

, or bottom-up heap construction initializes the queue in

O (∣ V ∣)

time. Scanning adjacency lists costs

O (∣ V ∣ + ∣ E ∣)

in total.

For

∣ V ∣ \geq 2

and

2 \leq d \leq ∣ V ∣

, the heap-operation contributions are therefore

O (∣ V ∣ d lo g_{d} ∣ V ∣) and O (∣ E ∣ lo g_{d} ∣ V ∣),

and the overall bound is

O ((d ∣ V ∣ + ∣ E ∣) lo g_{d} ∣ V ∣) .

(2)

A uniform bound including larger arity and tiny graphs is

O ((d ∣ V ∣ + ∣ E ∣) (1 + lo g_{d} (max (2, ∣ V ∣))))

. Arity greater than the number of vertices offers no useful extra heap levels. These bounds assume adjacency lists; with an adjacency matrix, scanning neighbours contributes

O (∣ V ∣^{2})

instead. No rebuilding of the heap is required after each decrease.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 5 / c / Solution 2026-10-31

With an adjacency list, initialization and the outer loop cost

O (∣ V ∣)

. Each vertex is visited once, and the adjacency scans inspect each edge of a graph twice, once from each endpoint. The total worst-case time is therefore $O (∣ V ∣ + ∣ E ∣)$ , with

O (∣ V ∣)

labels and recursion-stack space. An adjacency matrix representation instead incurs

O (∣ V ∣^{2})

scanning time.

Simple graph 2026-10-14

An undirected simple graph is exactly a pair of sets

G = (V, E), E \subseteq {{u, v} : u, v \in V, u \neq = v} .

Thus every edge is a two-element set of distinct vertices. The unordered pair

{u, v}

equals

{v, u}

, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges;

E

does not by itself determine

V

. For example,

({A, B}, {A B})

and

({A, B, C}, {A B})

have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of

C

Γ (C) = {A, B, D}

, so its degree of a vertex is

de g (C) = 3

. In label order

A, B, C, D, E, F

, the degree sequence is

(2, 2, 3, 3, 2, 2), \sum_{v \in V} de g (v) = 14 = 2 \cdot 7 = 2∣ E ∣.

(2)

This is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is

14/6 = 7/3

. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order

A, B, C, D, E, F

. Its entry

M_{uv}

is one exactly when

{u, v} \in E

, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row

C

(1, 1, 0, 1, 0, 0)

. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish

u \to v

from

v \to u

, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another

C D

would raise

de g (C)

and

de g (D)

to four without adding a new neighbour. A self-loop at

A

contributes two to its undirected vertex degree, making it four, because both endpoints lie at

A

. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

Sparse graph Created 2026-10-14 Updated 2026-10-25

A family of graphs is sparse when its edge count grows substantially more slowly than the square of its vertex count; a common convention is that

m = O (n)

, where

n

and

m

count vertices and edges. State the intended asymptotic convention explicitly. An adjacency list then uses fewer storage entries than an adjacency matrix.

Spectral graph theory 2026-10-14

Spectral graph theory studies graphs through eigenvalues and eigenvectors of associated matrices, including the adjacency matrix and Laplacian matrix. A graph eigenvalue usually refers to the adjacency-matrix spectrum unless another matrix is specified.

Subset dynamic programming for a Hamiltonian path 2026-10-31

For a directed graph with adjacency matrix

A

, let

D [S, v]

record whether a path visits precisely the vertices of

S

once and ends at

v

. The singleton states are true. A larger state is true exactly when some predecessor

u \in S ∖ {v}

has a true state for

S ∖ {v}

and an edge to

v

. Removing or adjoining the last edge proves this recurrence by mathematical induction on

∣ S ∣

. There are

n 2^{n - 1}

states, each requiring at most

n - 1

predecessor checks, giving

O (n^{2} 2^{n})

time and

O (n 2^{n})

storage. A true state for

S = V

certifies a Hamiltonian path.

Unique topological ordering criterion 2026-10-31

A finite nonempty Directed acyclic graph has a unique topological sort exactly when it has a Hamiltonian path. A Hamiltonian path forces the relative order of every consecutive pair and therefore of all vertices. Conversely, in a unique topological sort, every consecutive pair must have a forward edge: if such an edge were absent, swapping that adjacent pair would preserve all edge constraints and produce a second topological sort. The consecutive edges give a Hamiltonian path. Consequently one may compute any topological sort and test its consecutive edges, taking

O (n^{2})

time on an adjacency matrix representation.