Directed graph primer: cycles, topological order

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. How many serial schedules exist for n transactions? from Lesson 6.3.1
2. Name the anomaly R1(X) R2(X) W1(X) W2(X). from Lesson 6.2.1
3. How many schedules for transactions of 2 and 2 operations? from Lesson 6.3.1

1 · The Hook

"T1 must come before T2, T2 before T3, T3 before T1." No order of the three can satisfy that: the requirements go round in a cycle. The test for "is this schedule as good as a serial one?" draws exactly such requirements as arrows and looks for a cycle. Two graph ideas are needed: cycles and topological order.

2 · Predict First

Arrows: T1 → T2, T1 → T3, T3 → T2 ("→" means "must come before"). Is there an order of T1, T2, T3 that respects every arrow? How many?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Yes, exactly one: T1, T3, T2. T1 has no incoming arrow, so it goes first; then T3 (its only requirement, T1, is done); then T2.

Directed graphs

A directed graph has vertices (nodes) and directed edges u → v (arrows). Edges here mean "u must come before v".

• A path follows arrows: T1 → T3 → T2.
• A cycle is a path that returns to its start: T1 → T2 → T1, or T1 → T2 → T3 → T1.
• A graph with no cycle is a DAG (directed acyclic graph).

Topological order

A topological order lists all vertices so that every edge points forward (u before v for every u → v).

• A topological order exists iff the graph is acyclic.
• Algorithm: repeatedly remove a vertex with no incoming edges (from vertices not yet removed) and append it to the order. If at some point every remaining vertex has an incoming edge, there is a cycle.
• When several vertices are available at once, any choice works: each choice can lead to a different valid order. Counting orders = counting the different choice sequences.

Examples

4 · Visual

Left: acyclic, one topological order T1, T3, T2. Right: a cycle T1 → T2 → T3 → T1, so no order exists.

5 · Worked Examples

Example 1 Easy

Edges T2 → T1, T2 → T3. Give all topological orders.

Solution

T2 first; then T1 and T3 in either order: T2, T1, T3 and T2, T3, T1.

Example 2 Medium

Edges T1 → T2, T2 → T3, T3 → T4, T4 → T2. Topological order?

Solution

T2 → T3 → T4 → T2 is a cycle: none exists.

Example 3 GATE

Four vertices, edges T1 → T3 and T2 → T4 only. How many topological orders?

Solution

Choose positions: of the 4! = 24 orders, half have T1 before T3 and, independently, half have T2 before T4: 24 / 4 = 6.

8 · Connect the Dots

Lesson 6.3.1 counted schedules; this lesson gave the graph tools (cycles, topological orders). Next: build a graph from a schedule (the precedence graph) and use them to decide conflict serializability.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Cycle

Which edge set contains a cycle?

1. (A) 1→2, 1→3
2. (B) 2→1, 3→1
3. (C) 1→2, 2→3, 1→3
4. (D) 1→2, 2→3, 3→1

Q2 · NAT · 1 mark(s) — Count

How many topological orders does a graph on vertices 1, 2, 3 with the single edge 1 → 2 have?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Count

Vertices 1, 2, 3, 4 with edges 1 → 2, 1 → 3, 1 → 4. How many topological orders?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Existence

A topological order exists exactly when the graph:

1. (A) is connected
2. (B) is acyclic
3. (C) has a vertex with no outgoing edges
4. (D) has no edges

Q5 · MCQ · 2 mark(s) — Order

Edges T3 → T1, T1 → T2, T3 → T2. The only topological order is:

1. (A) T1, T3, T2
2. (B) T3, T1, T2
3. (C) T1, T2, T3
4. (D) T3, T2, T1

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

directed graphvertexdirected edgepathcycledirected acyclic graph (DAG)topological ordercounting topological orders