Free degree-level computing lessons for careful independent study.
Aplailasain by Static Carnival

Degree Level Programmes · Formal Computing Foundations · Lesson 25

Graph Models for Networks, Dependencies and Systems

Apply graph theory to realistic computing structures.

Back to coursePreviousNext lesson

Lesson overview

Apply graph theory to realistic computing structures.

CourseFundamentals of Computing
Topic strandGraph theory
Assessment styleDigital exam practice
EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

  • Model dependencies as directed graphs.
  • Explain why cycles may be useful or dangerous depending on context.
  • Use graph language to discuss networks and scheduling.

Learning outcomes

  • By the end of this lesson, you can model dependencies as directed graphs.
  • By the end of this lesson, you can explain why cycles may be useful or dangerous depending on context.
  • By the end of this lesson, you can use graph language to discuss networks and scheduling.

Key vocabulary

dependencynetworkcycletopological order

What this lesson is about

Graphs model networks by representing entities as vertices and connections as edges. They model dependencies by using directed edges to show precedence or requirement.

The same graph vocabulary can describe social networks, build systems, course prerequisites, transport routes and service dependencies, but the meaning of each edge must be defined.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

Dependency graphGraph model. A directed graph where edges represent prerequisite or dependency relationships.
Topological orderNamed graph idea. An ordering of vertices so every dependency arrow points forward in the list.
DAG (Directed acyclic graph)Acronym. A directed graph with no directed cycles. A topological order exists only for DAGs.
CycleGraph term. A route that returns to its starting vertex. In dependency models, a directed cycle usually means no valid ordering exists.

Formal notation and definitions

A dependency graph is usually directed: edge a → b means b depends on a, or a must precede b, depending on the convention.A topological order exists only for directed acyclic graphs.

How to read the symbols

a→ba\to bA directed edge; its meaning depends on the convention stated in the model.
topological orderAn ordering of vertices that respects directed dependency edges.
cycleA route that returns to its starting vertex.

Use directed edges consistently: first define whether a → b means 'a depends on b' or 'a must happen before b'.

Degree-level reasoning

Graph theory is a modelling discipline. The mathematical graph is not the network itself; it is a selected abstraction of entities and connections.

A strong graph answer states what vertices and edges represent before discussing paths, cycles, connectivity or traversal.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

A build system can model files as vertices and dependencies as directed edges; a cycle may make the build order impossible.

Objects: tasks or services as vertices, dependency arrows as edges, and any directed cycle.

Model cue: Use a dependency graph with arrows showing prerequisite order. A directed cycle highlights an impossible ordering constraint.

2. Mathematical working

V={A,B,C,D},E={(A,B),(B,C),(A,D)}V=\{A,B,C,D\},\quad E=\{(A,B),(B,C),(A,D)\}A→Bmeans A must be completed before BA\to B\quad\text{means A must be completed before B}A,D,B,Cis one valid topological orderA,D,B,C\quad\text{is one valid topological order}
Plain text version
A dependency graph is usually directed: edge a → b means b depends on a, or a must precede b, depending on the convention.
A topological order exists only for directed acyclic graphs.

Worked use: If compile B depends on generated file A, draw A → B using the convention 'A must precede B'. If B also has to precede A, the cycle means no valid build order exists.

3. How to read the working

  1. Read V as the task set and E as the dependency relation between tasks.
  2. State the arrow convention before reasoning. Here A → B means A must be completed before B.
  3. A topological order lists vertices so every dependency arrow points forward in the list.
  4. Look for directed cycles, because a cycle in a dependency graph means no valid completion order exists.

4. Computing meaning and check

The direction of each edge controls the dependency meaning. A cycle may be harmless in a route network but fatal in a prerequisite or build-order model.

Now check: Create a four-task dependency graph and decide whether a topological order exists.

Worked example

From scenario to formal reasoning

Scenario: A build system can model files as vertices and dependencies as directed edges; a cycle may make the build order impossible.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

If compile B depends on generated file A, draw A → B using the convention 'A must precede B'. If B also has to precede A, the cycle means no valid build order exists.

Worked solution structure

How a strong answer should be written

  1. Define: State the domain and the objects under discussion. For this lesson, begin from A dependency graph is usually directed: edge a → b means b depends on a, or a must precede b, depending on the convention.
  2. Apply: Use the relevant definition from graph theory; do not rely on the diagram, wording or intuition alone.
  3. Check: Test a boundary case, counterexample candidate or representation limit.
  4. Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is treating cycles as always bad. In route networks they are normal; in dependency ordering they may be a defect.

Guided practice

  1. Create a four-task dependency graph using the convention A → B means A must precede B.
  2. Find one valid topological order if the graph is acyclic.
  3. Add one edge that creates a directed cycle and explain why no valid build order exists.
  4. Explain why cycles are normal in route networks but dangerous in dependency scheduling.

Quick checks

1. A topological order exists only for:

2. Before reasoning about a dependency edge a → b, you must state:

Digital exam practice

Example exam task

For tasks A, B, C and D with dependencies A → B, A → C, B → D and C → D, find a topological order. Then add D → A and explain why scheduling fails.

Notation toolkit

G=(V,E)G=(V,E)

Means: a graph model of tasks, services or network points

How to use: Use it to name the objects before reasoning.

u→vu\to v

Means: a directed dependency or route edge

How to use: Use it after stating what the arrow means in context.

v0→⋯→v0v_0\to\cdots\to v_0

Means: a directed cycle returning to the start

How to use: Use it when checking dependency scheduling.

What a good answer is expected to show

A strong answer for this lesson defines tasks or services as vertices, dependency arrows as edges, and any directed cycle, applies the graph theory method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

  1. Read V as the task set and E as the dependency relation between tasks.
  2. State the arrow convention before reasoning. Here A → B means A must be completed before B.
  3. A topological order lists vertices so every dependency arrow points forward in the list.
  4. Look for directed cycles, because a cycle in a dependency graph means no valid completion order exists.

Model answer

Reveal model answer
G=(V,E),V={A,B,C,D}G=(V,E),\quad V=\{A,B,C,D\}E={(A,B),(A,C),(B,D),(C,D)}E=\{(A,B),(A,C),(B,D),(C,D)\}D→A creates the directed cycle A→B→D→AD\to A\text{ creates the directed cycle }A\to B\to D\to A

For dependencies A → B, A → C, B → D and C → D, one topological order is A, B, C, D. Adding D → A creates a directed cycle A → B → D → A, so no schedule can put every prerequisite before every dependent task. Cycles can be acceptable in route networks but not in prerequisite scheduling.

Practise next

  1. Create a four-task dependency graph using the convention A → B means A must precede B.
  2. Find one valid topological order if the graph is acyclic.

Self-marking criteria

  • States the arrow convention.
  • Builds a directed graph over four tasks.
  • Gives a valid topological order for the acyclic case.
  • Identifies a directed cycle after the added edge.
  • Contrasts dependency cycles with harmless route-network cycles.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Propositional Logic: Syntax, Semantics and Truth Tables.