Codex @codex  0

 Incoming links: Directed graph

Parallel-bond ray with different site and bond thresholds 2026-10-14

v_{0}, v_{1}, \dots

and

n + 1

parallel bonds from

v_{n}

v_{n + 1}

. This is a locally finite graph, although the incoming degrees are unbounded. For bond percolation,

θ_{b} (p) = \prod_{n \geq 0} (1 - (1 - p)^{n + 1}) > 0

whenever

p > 0

: the failure probabilities are summable, so the infinite product is positive. For site percolation, survival requires every vertex of the ray to be open, which has probability zero for

p < 1

. Thus the survival and susceptibility thresholds for directed percolation satisfy

p_{H}^{b} = 0

and

p_{H}^{s} = 1

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Advanced data structures and algorithms / 2 / a / Solution 2026-10-31

 View more

A flow network is a finite directed graph

G = (V, E)

with nonnegative flow network edge capacities

c_{e}

, together with distinct source and sink vertices

s, t

. A feasible flow in the nonnegative directed-edge convention is a function

f : E \to R_{\geq 0}

satisfying the capacity constraints and flow conservation:

0 \leq f_{uv} \leq c_{uv} (uv \in E), \sum_{u : uv \in E} f_{uv} = \sum_{w : v w \in E} f_{v w} (v \in / {s, t}) .

(1)

Its flow value is the net outflow at the source,

∣ f ∣ = \sum_{w : s w \in E} f_{s w} - \sum_{u : u s \in E} f_{u s},

(2)

which equals the net inflow at the sink by flow conservation.

A cut of a flow network is a partition of a set

(S, V ∖ S)

with

s \in S

and

t \in / S

. Its cut capacity counts only directed edges leaving

S

c (S, V ∖ S) = \sum_{u \in S, v \in / S : uv \in E} c_{uv} .

(3)

The net flow across the cut of a flow network subtracts flow on edges returning into

S

, and equals

∣ f ∣

For the following parts, a circulation with vertex demands has no exceptional source or sink in the original directed graph. Instead it satisfies net inflow minus net outflow equal to

d_{v}

at every vertex. Thus positive demands consume flow, and negative demands supply flow.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Computer aided formal verification / 1 / f / Solution 2026-10-31

 View more

A transition relation requires an explicit interpretation of the Boolean variables as current and next state bits. Take the four states

q_{00}, q_{01}, q_{10}, q_{11}

. Encode the current state by

(u, x)

and the next state by

(y, z)

, and define

q_{ux} \to q_{yz} ⟺ R (u, x, y, z) = y \lor (x \land z) = 1.

(1)

The extra current bit

u

is deliberately unused by the Boolean formula. A four-state transition system normally needs four bits to describe a pair of states; a Boolean formula using only three of them simply describes a transition relation independent of the fourth bit.

When

x = 0

, the condition is

y = 1

, so the permitted next states are

q_{10}

and

q_{11}

. When

x = 1

, the condition is

y \lor z

, so the permitted next states are

q_{01}, q_{10}, q_{11}

. The resulting adjacency matrix, with rows and columns both ordered

q_{00}, q_{01}, q_{10}, q_{11}

, is

A_{R} = 0000010111111111 .

(2)

The directed graph below plots all ten directed edges, including the three self-loops. No arrow enters

q_{00}

, but it is a valid state with two outgoing arrows. Every state has a successor. As permitted, no initial states are distinguished.

Figure 1.
Four-state transition system with current bits (u, x), next bits (y, z), and relation y or (x and z)
. **Details**.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 2 / a / ii / Solution 2026-10-31

 View more

Use one logical traversal token carrying the discovered vertex set and the active LIFO stack of vertices. The current vertex either discovers its first still-unvisited outgoing graph neighbour, or returns to its preceding stack entry. The former records both the child's parent in a rooted tree and the parent's child. Unlike concurrent flooding discovery, this visits one entire branch before the next, giving an actual depth-first search.

The important directed-graph detail is that a child's parent need not be an outgoing graph neighbour. Return the token by routing it through the original directed graph; a routing hop does not count as a traversal visit. The following duplicate-suppressed flooding route requires no previously known topology and sends only to immediate outgoing graph neighbours.

final case class Token(visited: Set[NodeId], stack: List[NodeId], serial: Int)
sealed trait Msg
final case class Route(serial: Int, target: NodeId, token: Token) extends Msg
case object Finished extends Msg

Here stack.head is the current vertex. Use the same paired toNode and fromNode ports as in (i), now with the new Msg type. Set mailbox capacity to

B = N (2 N + 1)

, normalize neighbours with distinct, and again leave the mailboxes open until all processes have joined. The following helpers are local functions inside each node's generated process.

def span: PROC = proc {
  val adj = neighbours.distinct
  val routed = scala.collection.mutable.Set[Int]()
  var entered = false
  var done = false

  def flood(message: Msg): Unit =
    for (w <- adj) toNode(w) ! message

  def move(target: NodeId, state: Token): Unit = {
    val s = state.serial + 1
    routed += s
    flood(Route(s, target, state.copy(serial = s)))
  }

  def step(t: Token): Unit = {
    assert(t.stack.head == me)
    if (!entered) {
      entered = true
      parent = if (t.stack.tail.isEmpty) me else t.stack.tail.head
      children = Nil
    }
    adj.find(w => !t.visited(w)) match {
      case Some(w) =>
        children = children :+ w
        move(w, Token(t.visited + w, w :: t.stack, t.serial))
      case None =>
        t.stack.tail match {
          case p :: rest => move(p, t.copy(stack = p :: rest))
          case Nil => flood(Finished); done = true
        }
    }
  }

  if (me == 0) step(Token(Set(0), List(0), 0))
  while (!done) {
    fromNode(me) ? () match {
      case r @ Route(s, target, t) =>
        if (!routed(s)) {
          routed += s
          if (target == me) step(t) else flood(r)
        }
      case Finished => flood(Finished); done = true
    }
  }
}

Every route number is globally unique: there is one logical token, and its serial increases at every move. The sender inserts that serial in its own routed set before flooding; this stops a returning copy from circulating again. Intermediate vertices forward the first copy of an envelope and ignore later copies. Its target consumes exactly one copy without forwarding it. Because the directed graph is strongly connected, a simple directed path from sender to target exists; its intermediate vertices eventually relay the envelope. Thus each move eventually finishes.

A routed return can pass through a vertex not yet discovered by the depth-first search. That vertex only forwards the envelope: it does not run step, change entered, or assign a parent. This distinction is essential. For the directed cycle

0 \to 1 \to 2 \to 0

, returning from two to one uses

2 \to 0 \to 1

, while the logical traversal stack changes from

(2, 1, 0)

(1, 0)

Figure 1.
A depth-first search return follows a routed directed path when the child has no reverse directed edge
. **Details**.

The discovered vertex set only grows. Each newly discovered vertex is pushed once and later popped once; an exhausted vertex can never acquire a new unvisited neighbour as this set grows. Consequently there are exactly

N - 1

downward moves and

N - 1

return moves. When the root exhausts its outgoing graph neighbours, every vertex has been visited, by the standard reachability argument for depth-first search. Each nonroot parent was recorded along the actual downward directed edge, and children records exactly those assignments in discovery order.

There are

2 (N - 1)

route envelopes, each forwarded at most once per outgoing directed edge, and one final Finished flood. Each node forwards Finished before exiting; strong connectivity therefore delivers it everywhere. There are at most

N (2 N - 1)

total messages into any mailbox, below the proposed capacity. Even a mailbox whose process has already exited cannot block later sends. All processes terminate with

the parent and ordered children of a depth-first spanning tree rooted at 0.

(1)

This deliberately trades communication efficiency for a simple valid solution on a genuinely directed graph. A direct parent acknowledgement would instead require an additional bidirectional-edge assumption, which the question does not supply.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Concurrent programming / 2 / a / i / Solution 2026-10-31

 View more

A directed graph needs an explicit termination argument. After assigning its parent in a rooted tree, a vertex must still receive later traffic: having no new graph neighbours to discover is not proof that other senders have finished. Use a discovery wave together with duplicate-suppressed announcements of activated vertices. Both kinds of message identify their immediate sender, who has already activated.

sealed trait Msg { def from: NodeId }
final case class Discover(from: NodeId) extends Msg
final case class Active(from: NodeId, origin: NodeId) extends Msg

Let adj = neighbours.distinct. The actual communication objects must expose both input and output ports: the paper's Seq[![Msg]] annotation supplies only output capabilities, although the following sentence also requires receiving. Set up one shared-writer, single-reader buffered message-passing channel per vertex, publish its output in toNode, and keep its input in fromNode. Only node i reads fromNode(i). These are the two ports of the same underlying mailbox, not additional graph edges. The question's prohibition on buffered message-passing channels applies to Question 1(a), not to this question.

Take

N \geq 1

, reliable delivery, eventual scheduling, finite adj, and mailbox capacity

B = N (N + 1)

. Every node has at most

N

distinct incoming neighbours, including itself if there is a self-loop. The bound below ensures that no send blocks merely because a mailbox's receiver is not currently reading. Do not close these shared mailboxes on local process termination: late, redundant traffic is harmless and bounded. Their creator can release them after the parallel composition has joined. For example, the concrete setup can use

val mailbox = Vector.fill(N)(N2NBuf[Msg](B, 0, 1))
val toNode: Seq[![Msg]] = mailbox
val fromNode: Seq[?[Msg]] = mailbox

Here the zero writer count makes the shared output independent of individual writer departures; processes do not call its closeOut during the search.

def span: PROC = proc {
  val adj = neighbours.distinct
  var started = false
  val known = scala.collection.mutable.Set[NodeId]()

  def announce(origin: NodeId): Unit = {
    if (!known(origin)) {
      known += origin
      for (w <- adj) toNode(w) ! Active(me, origin)
    }
  }
  def activate(sender: NodeId): Unit = {
    started = true
    parent = if (me == 0) 0 else sender
    for (w <- adj if me == 0 || w != parent)
      toNode(w) ! Discover(me)
    announce(me)
  }

  if (me == 0) activate(0)
  while (known.size < N) {
    val message = fromNode(me) ? ()
    if (!started) activate(message.from)
    message match {
      case Discover(_) => ()
      case Active(_, origin) => announce(origin)
    }
  }
}

An announcement may be a vertex's first incoming message. It then serves as a discovery message too: its immediate sender is already active, and the receiving vertex adopts that sender as its parent in a rooted tree before forwarding anything. This preserves the required first-message rule. In particular, an inactive vertex never forwards announcements while remaining inactive, which could invalidate the parent-order argument.

For each nonroot vertex, its parent in a rooted tree activated strictly earlier. Repeated parent-following therefore cannot make a graph cycle and eventually reaches the unique initially active vertex, zero. Each parent assignment uses an actual incoming directed edge. Strong connectivity ensures eventual activation of every vertex: if an activated set were proper, a directed path from zero to an inactive vertex would have a first edge leaving that set. Its sender sends a discovery message along that edge; excluding its own parent does not exclude an inactive neighbour.

Each activation sends at most one Discover on each outgoing directed edge. For each of the

N

origins, each vertex forwards Active at most once on each outgoing directed edge. Therefore a mailbox receives at most

N (N + 1)

messages over the whole run, proving the chosen nonblocking storage bound. Each origin's announcement eventually reaches every vertex, since every first receipt forwards it on all outgoing directed edges. Thus every known set reaches size

N

and every process terminates, even if redundant messages remain unread:

parent (0) = 0; parent (v) is the sender of v ’s first message, v \neq = 0.

(1)

No timeout is used to conclude that the distributed work has finished. This uses larger finite mailboxes to make the termination proof simple, rather than assuming that simultaneous synchronous broadcasts cannot deadlock.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / d / i / Solution 2026-10-31

 View more

The problem is decidable. We need exactly one accepted word, even if that word has several accepting runs in the nondeterministic finite automaton.

First convert the input nondeterministic finite automaton to an equivalent deterministic finite automaton

D

using the subset construction, taking epsilon closure where necessary. In the finite transition directed graph of

D

, test whether an accepting automaton state is reachable from the initial automaton state. This is the standard finite automaton emptiness test. If none is reachable, the recognized formal language is empty, so answer no.

Otherwise retain a graph path to an accepting automaton state and read its labels to obtain one accepted word

w

. If the initial automaton state is accepting,

w

may be the empty word. Build a complete deterministic finite automaton for the singleton formal language

{w}

: it tracks the matching prefix of

w

, accepts only after exactly its full length, and enters a rejecting sink on a mismatch or any extra input symbol.

Complement that complete deterministic finite automaton by exchanging accepting and rejecting automaton states. Form its product with

D

, accepting exactly when the

D

coordinate accepts and the other coordinate accepts. This product recognizes

L (D) \cap (Σ^{*} ∖ {w}) = L (D) ∖ {w} .

(1)

Apply the finite automaton emptiness test again. Answer yes if and only if this difference is empty. The first test guarantees that

w

belongs to

L (D)

; the second guarantees there is no different accepted word. All constructions have finitely many automaton states and all reachability tests terminate. This gives a singleton-language test for finite automata.

Decidable: test L (D) \neq = \emptyset and L (D) ∖ {w} = \emptyset .

(2)

 Read the full article

Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 1 / b / Solution 2026-10-25

 View more

With the conventional strictly positive step costs, the five answers in printed order are false, false, true, true, true. The third answer needs that positivity convention: it is false in general if zero-cost edges and unrestricted ties are admitted. Take the goal test on selection from the search frontier, and assume a finite reachable problem with a reachable goal state; finite branching factor and a positive lower bound on step costs give the corresponding tree search guarantees on an infinite problem. These assumptions make the usual A-star search guarantees precise.^[ref]

For the first assertion, use a directed graph with transitions

s \to t

of cost

10

s \to x

of cost

1

and

x \to t

of cost

1

, where

t

is the only goal state. The perfect heuristic is

h^{*} (s) = 2

h^{*} (x) = 1

h^{*} (t) = 0

. Greedy best-first search selects the direct goal of cost

10

because its priority is zero. The least path cost is

2

. Knowing the exact remaining distance does not account for an expensive transition already taken.

The same counterexample settles the second assertion. Greedy best-first search selects

s, t

, while A-star search selects

s, x, t

: after expanding

s

, the A-star search priorities are

2

for

x

and

10

for the direct copy of

t

. Thus even the expanded state sets differ.

For the third assertion, let the current nonterminal search node have finite remaining distance

h^{*} (s)

. The first transition of a least-cost continuation has some successor

s^{'}

with

h^{*} (s) = c (s, s^{'}) + h^{*} (s^{'}) > h^{*} (s^{'}) .

(1)

Every older entry in the search frontier has estimate at least

h^{*} (s)

, since the current entry was selected with minimum estimate. A newly generated successor with strictly smaller estimate therefore wins over every older entry. Whichever new successor is selected has smaller remaining distance than the current search node, so the argument repeats. Consequently the selected search nodes form one parent–child chain; include the selected goal, or append it if “expanded” excludes goal processing. This greedy perfect-heuristic descent does not imply least path cost, as the first counterexample demonstrates.

The zero-cost qualification is substantive. Give

s

two successors

a, b

of cost

1

, add

a \to x

of cost

0

, and add

x \to t

and

b \to t

of cost

1

. The perfect heuristic has values

2

s

1

a, b, x

and

0

t

. Alphabetical priority ties let greedy best-first search select

s, a, b, t

, which is not one graph path. Thus the unqualified third assertion requires a cost or tie convention absent from the printed text.

For the fourth assertion, a least remaining distance satisfies

h^{*} (s) \leq c (s, s^{'}) + h^{*} (s^{'})

(2)

on every edge, by taking that edge and then a least-cost continuation. Thus

h^{*}

is a consistent heuristic. The usual A-star search graph search finalizes each expanded state's least path cost and returns a least-cost goal.

For the fifth assertion, write

C^{*} = h^{*} (s_{0})

. Before a goal is selected, an unexpanded prefix of an optimal graph path remains on the search frontier, with

f = g + h^{*} = C^{*}

. A-star search therefore selects only search nodes with

f \leq C^{*}

. Since

g \geq 0

h^{*} (n) \leq g (n) + h^{*} (n) \leq C^{*} = h^{*} (s_{0}) .

(3)

This compares remaining cost, not search depth or accumulated path cost. The statement can fail with negative costs; those are outside the convention used here.

 Read the full article

Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 1 / i / Solution 2026-10-25

 View more

For $N \geq 3$ , depth and history-tree size can be infinite, while a sufficient finite state bound is $2 \cdot 5^{N}$ . The number of possible completed histories also becomes unbounded. With variables

p, q, r

, first let

A

assign

p

and

B

assign

q

. Both can then keep flipping their own variable, leaving

r

unassigned. After four such flips the same assignment, ownership and player-to-move recur. Arbitrarily many repetitions can precede assignment of

r

, so there are infinitely many distinct finite complete histories as well as legal infinite plays.

A state must now record ownership: for each variable the possibilities are unassigned,

A

-owned false,

A

-owned true,

B

-owned false, and

B

-owned true. Include the player to move, since flips break the old link between turn parity and the number assigned. This gives

∣ V ∣ \leq 2 \cdot 5^{N} .

(1)

Many encoded positions are unreachable, so this is an upper bound. Each nonterminal state has at most

2 N

legal moves: two assignments per unassigned variable and one flip per variable owned by the acting player. Thus the finite directed graph has at most

2 N ∣ V ∣

edges even though its unrolled game tree is infinite. The

2^{N}

possible final Boolean valuations are unchanged, but they no longer count distinct plays or complete ownership states. For

N = 1, 2

, no player gets a legal opportunity to flip before all variables are assigned, so the original finite bounds still apply.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 11 / 3 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

Both alternatives can be proved. For the oriented tree alternative take

n \geq 2

; at

n = 1

the displayed tournament order is zero, so that unqualified boundary case cannot be intended.

Choose a median order of a tournament

v_{1}, \dots, v_{N}

, maximizing its number of forward directed edges. Every interval inherits a median order, since improving that interval would improve the whole order. If

v_{i}

had fewer outneighbours than inneighbours in

v_{i + 1}, \dots, v_{j}

, moving it just past

v_{j}

would increase the number of forward directed edges. Hence it has at least half the vertices of that later interval as outneighbours.

Call a graph embedding half-sparse if every proper final interval

I

satisfies

∣ f (T) \cap I ∣ < ∣ I ∣/2 + 1

. This half-sparse median-order embedding admits a useful extension. Suppose an outward leaf is attached to a vertex mapped to

v_{i}

, and reserve two extra vertices at the end of the tournament order. In the old interval after

v_{i}

, half-sparsity bounds the number of occupied vertices by less than half its size plus one. The interval extended by two vertices has at least that half-size plus one outneighbours of

v_{i}

. Thus at least one outneighbour is free; map the new leaf there. Every old final interval has gained two available places and at most one new image, so its strict inequality persists. Final intervals wholly within the two new places contain at most one image, so they also satisfy the inequality. This proves the extension, not just an existence assertion about degrees.

Starting with an directed edge in a two-vertex tournament and repeatedly attaching outward leaves proves that every

h

-vertex arborescence embeds half-sparsely in every

(2 h - 2)

-vertex tournament for

h \geq 2

. The root-first construction supplies the induction. An unused suffix can be appended without destroying the inequality; for a suffix which contains the whole old order the extra place supplies the needed strictness. A singleton embeds half-sparsely in the first vertex of a two-vertex order. Reversing the oriented tree and tournament gives ordinary embeddings of reversed arborescences in

2 h - 2

vertices as well.

Here is the stronger invariant needed for an arbitrary oriented tree. Root it at a source. Classify each directed edge as forward or backward according to whether it points away from or towards the root in the underlying rooted tree. Let

b

be the number of backward directed edges and

c

the number of nonempty connected components made of these directed edges, ignoring isolated vertices. Put

d = b - c

. We claim that the oriented tree has a half-sparse embedding in every median-ordered tournament of order

2 n + 2 d

Induct on the oriented tree order. If it has a forward leaf, delete that leaf, use the induction hypothesis and apply the two-place extension. Neither

b

nor

c

changes. If there are no backward directed edges, use the arborescence construction. Otherwise first remove forward leaves as above, so every remaining leaf is backward. Choose a backward component furthest from the root. It must be a pendant subtree: a forward continuation below it would either reach another backward component, contrary to its choice, or end at a forward leaf. Let this component have

h \geq 2

vertices and top vertex

y

. Since the root is a source,

y

is not the root; its joining directed edge from its parent

x

is forward. The component is an reversed arborescence rooted at

y

Delete the component. The remaining oriented tree has parameters

n^{'} = n - h, b^{'} = b - h + 1, c^{'} = c - 1, d^{'} = d - h + 2.

(1)

Its required tournament order is

2 n + 2 d - 4 h + 4

. Embed it in the initial interval of this length. Temporarily attach

2 h - 2

outward leaves at

x

, using the extension lemma repeatedly. This consumes exactly

4 h - 4

extra places and gives a half-sparse embedding of the enlarged oriented tree in the original tournament. The

2 h - 2

temporary images all lie in the outneighbourhood of

f (x)

; among them embed the deleted reversed arborescence. Its root automatically receives the joining directed edge from

f (x)

. Replace the temporary leaves by this component. The final image is a subset of the temporary enlarged image, so half-sparsity survives. This proves the invariant with the precise count, including the case when the remaining oriented tree is a singleton.

Unless the oriented tree is already an in- or out-arborescence, every rooting has at least one backward component. Choose one orientation, reversing all directed edges if necessary, so that some rooting has at most

(n - 1) /2

backward directed edges. It then has

d \leq (n - 3) /2

. Within this fixed orientation choose the root to minimize

(d, b)

lexicographically. If a neighbour pointed into the root, move the root across that directed edge. Only this directed edge changes its forward/backward classification. Removing it from the backward forest decreases

b

by one and decreases

c

by at most one; hence it cannot increase

d

, and when

d

stays equal it strictly decreases

b

. This contradicts the chosen minimum. Thus the chosen root is a source, while its

d

retains the required bound. Reversal does not affect a universal tournament-embedding assertion, because one reverses the host tournament too. The invariant proves the three-times-order tournament bound for oriented trees:

T \subseteq R whenever ∣ T ∣ = n \geq 2, ∣ R ∣ = 3 n - 3.

(2)

For the lower obstruction, take the outward graph star with

n - 1

leaves. There is a regular tournament on

2 n - 3

vertices: on residues modulo

2 n - 3

, direct

i \to j

when

j - i

is one of

1, \dots, n - 2

. Every vertex has outdegree

n - 2

, so none can be the centre of that outward star. Thus the universal bound cannot be reduced to $2 n - 3$ .

For the strongly connected directed graph alternative, the correct universal assertion is an upper bound by the independence number, together with examples needing that many directed circuits. The literal assertion that every such graph needs

α (D)

directed circuits is false: a directed four-cycle has independence number two and is spanned by one directed circuit. Work with a nontrivial strongly connected digraph; a loopless singleton has no directed circuit.

Use the permitted coherent cyclic order of a digraph. Representatives differ by cyclic rotations and swaps of consecutive nonadjacent vertices. In every representative, a backward directed edge

v_{j} \to v_{i}

has a forward directed path from

v_{i}

v_{j}

. A directed circuit with one backward directed edge winds once around the order. Every vertex belongs to such a directed circuit, because every vertex has an outgoing directed edge and coherence puts that directed edge on a once-winding directed circuit. Let

k

be the cyclic stability of a digraph order: the largest size of an independent set consecutive in an equivalent order. Then

k \leq α (D)

We need a short ordering lemma. If a set

X

has no forward path between distinct members, then

∣ X ∣ \leq k

. Among equivalent representatives retaining this property, minimize the span from its first to its last member. Suppose there is a vertex in a gap. If some gap vertex

y

cannot be reached from an earlier member of

X

by a forward path, take the first such

y

. Every preceding gap vertex in the span is reachable from an earlier member of

X

. It follows that

y

has no forward incoming directed edge from anywhere in that part of the span; a backward outgoing directed edge to it is also impossible, since coherence would supply the same forbidden forward reachability. Thus

y

is nonadjacent to every intervening vertex and can be moved before the first member of

X

, shortening the span. Otherwise every gap vertex is reachable from an earlier member of

X

. Take the last one. It cannot have a forward path to a later member of

X

, and coherence consequently rules out directed edges in either direction to the following members of

X

. Move it past them, again shortening the span. Swaps of nonadjacent vertices do not change the forward-edge graph, so these moves preserve the hypothesis. Both cases contradict minimality. Therefore

X

is consecutive. It is independent: a forward directed edge is forbidden by hypothesis, and a backward directed edge would imply a forward path by coherence. Rotate it to the start to obtain

∣ X ∣ \leq k

Choose a representative starting with a stable block

S = {s_{1}, \dots, s_{k}}

. Add sink copies

s_{1}^{'}, \dots, s_{k}^{'}

, retain all forward directed edges of

D

, and add

v \to s_{i}^{'}

for each original directed edge

v \to s_{i}

. This is an acyclic auxiliary directed graph

A

. A once-winding directed circuit through

s_{i}

cannot visit another block member, since no forward path can join two members of this initial independent block. Opening this directed circuit gives a path from

s_{i}

s_{i}^{'}

A

The partial order defined by reachability in

A

has width exactly

k

. The sink copies already form an antichain of size

k

. For the reverse inequality, let

X

be an antichain and let

J

index its sink copies. Permute the independent initial block so that these labels come first, then rotate that part of the block to the end. The set

Y = (X \cap V (D)) \cup {s_{j} : j \in J}

(3)

has size

∣ X ∣

: a vertex and its own copy cannot both belong to

X

, since they are comparable by the opened directed circuit. There is no forward path between distinct members of

Y

in the rotated order. A path between original members would give comparability in

A

; a path from an original member to

s_{j}

would become a path to its sink copy, also forbidden. No forward path leaves the final stable block. The ordering lemma therefore gives

∣ X ∣ = ∣ Y ∣ \leq k

Apply the Dilworth theorem to partition this reachability order into

k

chains in a partial order. Each chain contains exactly one original block vertex and exactly one sink copy, since each of these two antichains has size

k

; these are its first and last elements. Expand consecutive chain relations into directed paths in

A

. The paths cover all vertices, though intervening vertices can occur on several paths. Label their heads

s_{i}

and their tails

s_{σ (i)}^{'}

; the tail labels define a permutation

σ

Among all such covering path families maximize the number of cycles of

σ

. If two paths whose labels lie in the same permutation cycle meet at a vertex, exchange their suffixes there. The paths remain simple, since the auxiliary graph is acyclic, and their union still covers the same vertices. Exchanging the two tail labels splits that permutation cycle into two, a contradiction. Thus paths in the same permutation cycle are disjoint. Identify every

s_{i}^{'}

with

s_{i}

and concatenate the paths around each cycle of

σ

. Each concatenation is a genuine directed circuit, with no repeated vertex except its closing vertex. Together these directed circuits cover

D

, and there are at most

k \leq α (D)

of them. This proves the circuit-cover bound by independence number:

D has a spanning circuit family of size at most α (D) .

(4)

Finally, form

k

directed triangles sharing just one central vertex, with no directed edges between their other vertices. This strongly connected directed graph has independence number

k

, by taking one outer vertex from each triangle. A simple directed circuit can use only one triangle, since visiting a second requires repeating the centre. Exactly

k

directed circuits are therefore necessary. The bound $α (D)$ is sharp in general; $α (D) - 1$ is not a universal bound.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 38 / 3 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

In a minimum-cost flow problem, a directed graph has arc flows

f_{ij}

, unit costs

c_{ij}

, lower and upper capacities

ℓ_{ij}, u_{ij}

, and net supplies

b_{i}

summing to zero. The linear program minimizes

\sum_{ij} c_{ij} f_{ij}

subject to the flow balances

\sum_{j} f_{ij} - \sum_{j} f_{ji} = b_{i}

and

ℓ_{ij} \leq f_{ij} \leq u_{ij}

Give each graph vertex a network dual potential

π_{i}

. With the outgoing-minus-incoming oriented incidence matrix

B

, the optimization Lagrangian is

L (f, π) = c^{T} f + π^{T} (b - B f) = π^{T} b + \sum_{ij} r_{ij} f_{ij}, r_{ij} = c_{ij} - π_{i} + π_{j} .

(1)

Minimizing over the capacity intervals is separable. A candidate feasible flow minimizes this optimization Lagrangian if it takes its lower bound whenever the network reduced cost is positive, its upper bound whenever that network reduced cost is negative, and any allowed value when that network reduced cost is zero. Equivalently, for arcs with distinct lower and upper bounds,

f_{ij} = ℓ_{ij} \Rightarrow r_{ij} \geq 0, ℓ_{ij} < f_{ij} < u_{ij} \Rightarrow r_{ij} = 0, f_{ij} = u_{ij} \Rightarrow r_{ij} \leq 0.

(2)

For every other feasible flow

g

, these conditions give

c^{T} f = L (f, π) \leq L (g, π) = c^{T} g

. This proves the Lagrangian sufficiency theorem certificate, rather than merely stating the capacitated flow optimality conditions.

Put

t = f_{23}

. The four flow balances determine

(f_{12}, f_{23}, f_{34}, f_{41}) = (t + 3, t, t + 1, t + 2) .

(3)

Intersecting the four capacity intervals gives

2 \leq t \leq 4

. In particular,

f (2) = (5, 2, 3, 4)

(4)

is a feasible flow. Write

C = c_{12} + c_{23} + c_{34} + c_{41}

. Its cost along the feasible interval is

c^{T} f (t) = Ct + 3 c_{12} + c_{34} + 2 c_{41} .

(5)

Hence

f (2)

is optimal precisely when $C \geq 0$ . A network dual potential certificate is

π_{1} = 0, π_{2} = - c_{12}, π_{3} = c_{41} + c_{34}, π_{4} = c_{41} .

(6)

The three interior arcs have zero network reduced costs and

r_{23} = C

, which has the required nonnegative sign at its lower capacity.

For the network simplex algorithm, start with the network simplex tree basis consisting of arcs

12, 34, 41

, and fix nonbasic arc

23

at its lower bound 2. These are exactly the potentials just found. If

C \geq 0

, no improving pivot is needed. If

C < 0

, arc

23

enters and its fundamental graph cycle increases all four flows by the same amount. At

f (2)

the remaining upper capacities are

(3, 3, 2, 4)

, so the simplex ratio test allows an increase of 2. Arc

34

reaches its upper bound and leaves the tree. The new network simplex tree basis has arcs

12, 23, 41

, with potentials

π_{1} = 0, π_{2} = - c_{12}, π_{3} = - c_{12} - c_{23}, π_{4} = c_{41} .

(7)

Now only the nonbasic arc

34

has a possibly nonzero network reduced cost, namely

r_{34} = C < 0

. It is at its upper bound, so the sign is optimal. Thus for all real costs the complete answer is

⎩ ⎨ ⎧ f (2) = (5, 2, 3, 4), f (t), 2 \leq t \leq 4, f (4) = (7, 4, 5, 6), C > 0, C = 0, C < 0.

(8)

When

C = 0

, both endpoint basic feasible solutions and every intermediate feasible flow have the same cost.

To count basic solutions, a network simplex tree basis omits one arc of the four-cycle and fixes that arc at either bound. The possibilities are

nonbasic arc 1212232334344141 bound used lower upper lower upper lower upper lower upper t 052514 - 2 6 feasible? no no yes no no yes no no

(9)

There are eight tree/bound basic representations, seven distinct basic flow vectors, and two basic feasible solutions. The distinction in the first count matters: the upper bounds on

12

and

23

both give the identical flow

(8, 5, 6, 7)

t = 5

. Thus if “basic solutions” counts vectors rather than basis representations, the answer to (i) is seven; the frequently used count of basis/bound choices is eight. The answer to (ii) is unambiguously two, since only

t = 2, 4

satisfy all capacities.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 38 / 5 / Solution Created 2026-10-03 Updated 2026-10-14

 View more

Use a complete directed graph on

n \geq 3

cities, with integral arc costs

c_{ij}

and a threshold

L

. A symmetric cost matrix also represents the undirected travelling salesman problem by orienting a tour. Let the binary variable

x_{ij}

indicate that city

j

follows city

i

, and forbid self-arcs. The decision integer programming formulation asks whether the following system has a solution:

x_{ij} \in {0, 1} (i \neq = j), j \neq = i \sum x_{ij} = 1 (i = 1, \dots, n), i \neq = j \sum x_{ij} = 1 (j = 1, \dots, n), i, j \in S i \neq = j \sum x_{ij} \leq ∣ S ∣ - 1 (\emptyset \neq = S ⊊ {1, \dots, n}), i \neq = j \sum c_{ij} x_{ij} \leq L .

(1)

The in-degree and out-degree equations make the selected arcs a cycle cover of a directed graph. Any proper graph cycle on a city set

S

would violate its subset inequality, so the selected arcs form one Hamiltonian cycle. Conversely, a Hamiltonian cycle obeys every inequality: a proper subset cannot contain all the successor arcs of its graph vertices. Thus the binary feasibility system is equivalent to the decision travelling salesman problem. The subset formulation has exponentially many inequalities, which is harmless for this formulation; verifying a proposed tour does not require listing them.

To call this decision problem NP-complete means two separate things. It belongs to NP: a yes-instance has a polynomial-length certificate in computational complexity, namely the cyclic ordering of the cities, and a deterministic algorithm checks distinct visits, the return to the start, and the total cost in polynomial time in the binary input length. It is also NP-hard: every decision problem in NP has a polynomial-time many-one reduction to it, preserving yes and no answers. This is a statement about worst-case computation on finite encodings, not a proof that every individual tour is hard to find or that no polynomial algorithm exists; that last conclusion would require

P \neq = NP

For the strict-threshold decision Max-TSP, choose an integer

M \geq max_{i \neq = j} c_{ij}

and replace each arc cost by

c_{ij}^{'} = M - c_{ij} \geq 0

. Every tour uses exactly

n

arcs, so

C^{'} = n M - C, C \leq L ⟺ C^{'} \geq n M - L ⟺ C^{'} > n M - L - 1.

(2)

Set the new threshold to

L^{'} = n M - L - 1

. Its encoding length, the transformed matrix's encoding length and the computation time are all polynomial in the original input length. If thresholds are required to be nonnegative, take

M \geq max (0, max c_{ij}, L + 1)

; the same identity works. Symmetry of costs is preserved. This is a polynomial-time many-one reduction from decision travelling salesman problem to decision Max-TSP, so the latter is NP-hard. A tour is again a polynomially verifiable certificate in computational complexity, now checking strict excess over

L^{'}

, so

decision Max-TSP is NP-complete .

(3)

For the approximation algorithm, use the standard nonnegative-length setting on a complete graph; no triangle inequality is required. Solve the maximum-weight assignment problem with diagonal assignments forbidden, for example by applying the Hungarian algorithm to the negative weights. The resulting cycle cover of a directed graph has weight

W

with

W \geq OPT

, since every tour is an allowed assignment.

If it already has a single graph cycle, it is an optimal tour. Otherwise remove a least-weight arc from each graph cycle. A graph cycle of

r \geq 2

arcs and weight

W_{r} \geq 0

loses at most

W_{r} / r \leq W_{r} /2

. The remaining arcs form vertex-disjoint graph paths covering all cities. Join the endpoint of each graph path to the start of the next, cyclically. The required arcs exist by completeness, and their nonnegative weights cannot diminish the retained weight. The resulting single Hamiltonian cycle therefore satisfies

ALG \geq \frac{W}{2} \geq \frac{OPT}{2} .

(4)

The Hungarian algorithm takes

O (n^{3})

arithmetic operations, and finding the graph cycles, cutting them and patching the graph paths takes

O (n)

further operations. For rational or integer weights these operations have polynomial encoding length, giving polynomial time. With symmetric costs, the same directed construction is a valid undirected tour after forgetting its orientation. This is the cycle-cover patching half-approximation for Max-TSP.

Nonnegativity is essential to this multiplicative guarantee. If arbitrary signed weights were allowed, giving every arc cost

- 1

would make every tour have weight

- n

, while half the optimum is

- n /2

. No tour could achieve the requested bound. Thus “length” has its usual nonnegative meaning in the approximation assertion.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 23 / 4 / d / Solution Created 2026-10-03 Updated 2026-10-06

 View more

Take a rooted directed graph

G

with one root

r

and one terminal vertex

a

, with its sole edge

r \to a

. Let

H

have a root

s

and two terminal vertices

b, c

, with edges

s \to b

and

s \to c

. The relation

Z = {(r, s), (a, b), (a, c)}

(1)

is a bisimulation. Each root move can be matched by a root move ending in a related terminal vertex. At all related terminal pairs there are no further edges, so both matching conditions are vacuous. Yet the directed graphs have two and three vertices and cannot be isomorphic. Bisimilarity need not preserve the number of successors.

Here and in the next part, the second graph's edge relation is

F

, and its response vertices belong to

H

. These are the corrections to the printed relation and vertex slips in the bisimulation clauses.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 3 / a / Solution Created 2026-10-03 Updated 2026-10-06

 View more

Choose the oriented incidence matrix convention with

+ 1

at an edge's tail and

- 1

at its head. Let

b_{i}

be net supply, so

\sum_{i} b_{i} = 0

. The uncapacitated minimum-cost flow problem on a finite directed graph is

min_{f \geq 0} \sum_{(i, j) \in E} c_{ij} f_{ij} subject to \sum_{j : (i, j) \in E} f_{ij} - \sum_{j : (j, i) \in E} f_{ji} = b_{i},

(1)

B f = b

. Negative

b_{i}

denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials

π

, the optimization Lagrangian is

L (f, π) = c^{T} f + π^{T} (b - B f) = π^{T} b + \sum_{(i, j) \in E} (c_{ij} - π_{i} + π_{j}) f_{ij} .

(2)

The infimum over

f \geq 0

is finite exactly when every network reduced cost

r_{ij} = c_{ij} - π_{i} + π_{j}

is nonnegative. Thus the Lagrangian dual problem and complementary slackness are

π max π^{T} b subject to r_{ij} \geq 0, f_{ij} r_{ij} = 0 for every edge .

(3)

A feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank

∣ V ∣ - 1

. A set of

∣ V ∣ - 1

independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring

r_{ij} = 0

on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

 Read the full article

Past exam of the mathematics course of the University of Cambridge / 2017 / ib / Paper 4 / 20H / a / Solution Created 2026-09-24 Updated 2026-10-05

 View more

A finite flow network is a directed graph with distinguished source

s

, sink

t

, and nonnegative finite flow network edge capacities

c_{ij}

on its directed edges. A feasible flow consists of numbers

f_{ij}

satisfying

0 \leq f_{ij} \leq c_{ij}, \sum_{j} f_{ij} = \sum_{j} f_{ji} (i \neq = s, t) .

(1)

The second condition is flow conservation; absent edges contribute zero. The strength of a flow is its net outflow from the source,

∣ f ∣ = \sum_{j} f_{s j} - \sum_{j} f_{j s},

(2)

which equals net inflow to the sink by summing flow conservation over the other vertices. The maximum flow problem is

maximise ∣ f ∣ over all feasible flows .

(3)

No assumption that a capacity-saturating flow at the source is feasible downstream is made. On a finite network a maximum exists, because the constraints define a nonempty compact set of edge flows and the objective is continuous.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 3 / b / Solution 2026-10-31

 View more

An individual can have any number of children, so use a rose tree, with one list of child trees at each root:

data DescendantTree = Desc Person [DescendantTree]
  deriving Show

descendants :: Database -> Person -> DescendantTree
descendants db p = Desc p (map (descendants db) (children db p))

The root records p, its immediate child trees record children db p, and recursion repeats the same construction at each generation. An individual with no recorded children produces Desc p []. For a finite database whose parent-child directed graph is acyclic, every recursive descent advances along a path that cannot revisit a vertex, so the construction terminates. On inconsistent cyclic records it can unfold indefinitely; finiteness of the database alone is insufficient for termination.

Two branches may contain the same descendant, as happens when relatives have a child. This is appropriate for the requested tree unfolding; it preserves both lines of descent rather than silently choosing one. The concise constructor equation is

D (p) = Desc p [D (c) ∣ c \in children (d b, p)] .

(1)

 Read the full article

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

 View more

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.

 Read the full article

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

 View more

A strongly connected component is a maximal set of vertices that are mutually reachable in a directed graph; a vertex reaches itself by a length-zero path. The condensation graph, also called the SCC graph, contracts each such component to one vertex and retains directed edges between different components. It is a Directed acyclic graph, since a cycle of components would make them mutually reachable and therefore one component.

For an original seven-vertex example, take cycles

a \to b \to c \to a

d \to e \to d

f \to g \to f

, and add

c \to d

e \to f

. The three components are ${a, b, c}$ , ${d, e}$ and ${f, g}$ . Their condensation is the three-vertex directed chain in that order: there is no return edge from a later component to an earlier one.

Figure 1.
Seven vertices with three strongly connected components and their condensation
. An original example. Internal cycles provide mutual reachability; the two forward connecting edges cannot merge distinct components. **Details**.

 Read the full article

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

 View more

All edge lengths are positive, so run the Dijkstra algorithm from every source

s

, retaining distances

d_{s}

and a shortest-path tree of its reachable component. Each run takes

O ((∣ V ∣ + ∣ E ∣) lo g (∣ V ∣ + 1))

with a binary heap. The following scans after each run use only

O (∣ E ∣)

additional work.

For a directed graph, inspect every closing edge

(u, s)

and consider

d_{s} (u) + w (u, s)

when

u

is reachable. The tree route from

s

u

followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as

s

; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.

For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges

{u, v}

absent from the current shortest-path tree, with both endpoints reachable, and consider

d_{s} (u) + w (u, v) + d_{s} (v) .

(1)

The two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.

To prove equality is attained, take a shortest cycle

C

and a source

s

on it. If either cycle edge incident to

s

is absent from the tree, its candidate uses a shortest route no longer than the rest of

C

, so it is at most the length of

C

. Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below

s

. Along the remaining segment of

C

, some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of

C

from

s

; their sum plus the crossing edge is at most the length of

C

. Thus some candidate is no greater than the optimum, completing the proof.

Return the smallest finite candidate, or report acyclicity if none exists. The total running time is $O ((∣ V ∣^{2} + ∣ V ∣∣ E ∣) lo g (∣ V ∣ + 1))$ , as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 7 / b / Solution 2026-10-25

 View more

Use the two-pass strongly connected component algorithm: first run depth-first search on the original directed graph, then search its graph transpose in decreasing order of the first pass's finishing times. The first-pass order from part (a) is

3, 1, 2, 5, 7, 6, 4.

(1)

Reversing the edges gives outgoing adjacency lists

1 : (4), 2 : (1), 3 : (), 4 : (7), 5 : (2, 4), 6 : (2, 3, 7), 7 : (5) .

(2)

The second pass first visits only

3

. Its next new root is

1

, whose search visits

1, 4, 7, 5, 2

; later entries already marked by this search are skipped. The next new root is

6

, whose graph transpose neighbours have already been assigned. Therefore the components are

{3}, {1, 2, 4, 5, 7}, {6} .

(3)

Within the middle component the directed cycle

1 \to 2 \to 5 \to 7 \to 4 \to 1

demonstrates mutual reachability. The source edge structure does not provide return paths from

6

or to

3

. More generally, decreasing finish order chooses a remaining component whose graph transpose search cannot escape to another still-unassigned component, so each second-pass tree is exactly one component. This explains the partition rather than merely listing it. The algorithm takes

O (∣ V ∣ + ∣ E ∣)

with adjacency lists.^[ref]

 Read the full article

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof resit / 8 / c / Solution 2026-10-25

 View more

Describe a branching vertex by the first-order logic sentence

β = \exists x \exists y \exists z [E (x, y) \land E (x, z) \land y \neq = z],

(1)

and the existence of a sink by

δ = \exists x \forall y \neg E (x, y)

. The directed path has sinks but no branching vertex; the directed cycle has neither sinks nor branching vertices; the directed arborescence has a branching vertex. Thus the following three sentences distinguish the named structures in order:

φ_{1} = δ \land \neg β, φ_{2} = \forall x \exists y E (x, y), φ_{3} = β .

(2)

Here

β, δ

are abbreviations for the displayed formulas; replacing them gives sentences in the single-relation first-order signature

{E}

. Explicitly,

φ_{1}

says that some vertex has no successor and that no vertex has two distinct successors. The truth table across the three structures is:

Sentence	$G_{1}$	$G_{2}$	$G_{3}$
$φ_{1}$	$1$	$0$	$0$
$φ_{2}$	$0$	$1$	$0$
$φ_{3}$	$0$	$0$	$1$

The conditions distinguish these three finite structures; they are not claimed to characterize all directed paths, cycles or trees among arbitrary directed graphs. Only local out-degrees and the presence of a sink are needed, without quantifying over paths of unbounded length.

 Read the full article