Graphs & Graph Models
What a graph is, the Königsberg bridge problem, finite vs infinite graphs, the six graph types (simple, multigraph, pseudograph, simple directed, directed multigraph, mixed), and graph models for social, information, transport and tournament problems.
▶Lecture videos
Click any timestamp — here or inside the notes — to jump the video to that moment. Your position is remembered.
Lesson 11 – Graphs & Graph Models
Main lesson video.
00:00Lesson 11: graphs and graph models01:52Where graphs are used: tournaments, networks03:42The Königsberg bridge problem04:37Definition of a graph: vertices and edges07:14Example: a computer network of data centres10:54Multigraphs12:43Pseudographs (loops)15:26Directed graphs18:55Directed multigraphs20:43Self-assessment: choose the right graph type21:33Graph models: acquaintanceship graphs25:06Influence graphs28:44The web graph31:30Road maps: one-way and two-way roads34:10Round-robin tournamentsVideo Lecture 1 – Introduction & Königsberg
Introduction to graph theory and the Königsberg bridge problem.
00:01Introduction: what a graph is01:39Vertices (nodes) and edges02:12Graph models: road maps, assigning jobs to employees02:48Video: the Seven Bridges of Königsberg03:51Can you cross every bridge exactly once?04:26Euler's insight: a new kind of geometry05:01Simplifying to a graph; counting degrees05:33Start and end are the only exceptions06:06Euler path condition: exactly 0 or 2 odd-degree nodes06:42Epilogue: the bridges destroyed in World War IIVideo Lecture 2 – Types of graphs (I)
Finite vs infinite; simple graphs, multigraphs and multiplicity.
00:01Recap: a graph = (V, E); vertices (nodes) and edges01:24Infinite vs finite graphs (we use finite)02:47The six types we'll study03:02Simple graph: no multiple edges, no loops05:20Multiple edges and loops explained06:09Multigraph: multiple edges, no loops06:43Edge of multiplicity m08:29Pseudographs beginVideo Lecture 3 – Types of graphs (II)
Pseudographs, directed graphs, ordered vs unordered pairs, and the summary table.
00:01Pseudograph: multiple edges and loops01:42Directed graphs (digraphs): arrows show direction03:06Ordered pair (u, v) vs unordered pair {u, v}04:08Simple directed graph vs directed multigraph05:41The summary table of all types06:37Mixed graphVideo Lecture 4 – Exercise hints
How to classify given graphs, and the airline routes exercise.
00:50Classifying graphs: arrows? multiple edges? loops?02:20Airline exercise: simple graph → multigraph → pseudographVideo Lecture 5 – Graph models
Social networks, information networks, transportation networks and tournaments.
01:03Social networks: acquaintanceship graphs (Facebook)03:16Influence graphs (directed)04:39Information networks: web graph, citation graph06:40Transportation: roadmaps and airline routes (directed multigraph)07:38Tournaments: round robin, single elimination1Why graphs?
Graphs are discrete structures made of vertices and edges that connect them. They model a huge range of problems:
- Competition between species in an ecological niche
- Who influences whom in an organisation
- Round-robin tournament outcomes
- Acquaintanceships between people and links between websites
- Roadmaps and assigning jobs to employees
- Whether a circuit fits on a planar circuit board
- Telling apart chemical compounds with the same formula but different structures
- Whether two computers are connected in a network
2The birth of graph theory — Königsberg
- Königsberg (Prussia) lay on the Pregel river, which split the city into four landmasses (including the island of Kneiphopf).
- Seven bridges linked them.
- Residents asked: can you leave home, cross each bridge exactly once, and return home?
- Leonhard Euler (1707–1783) solved it. He turned each landmass into a vertex (A, B, C, D) and each bridge into an edge. His method is considered the birth of graph theory.
A closed walk using every edge exactly once needs every vertex to have even degree (you leave a landmass as often as you enter it).
In Königsberg the degrees are A = 5, B = 3, C = 3, D = 3, all odd, so it's impossible. Load the Königsberg preset in the graph lab below to see it.
3What is a graph?
A graph G = (V, E) consists of:
- V: a non-empty set of vertices (nodes)
- E: a set of edges
Each edge has one or two vertices associated with it, called its endpoints. An edge connects its endpoints.
| Term | Meaning |
|---|---|
| Infinite graph | Infinite vertex set (or infinitely many edges) |
| Finite graph | Finite vertex set and finite edge set. This course uses finite graphs only 01:24 |
| Multiple edges | Two or more edges joining the same pair of vertices |
| Multiplicity m | When m different edges join the same unordered pair {u, v}, {u, v} is an edge of multiplicity m 06:43 |
| Loop | An edge that starts and ends at the same vertex 05:20 |
4The six types of graphs
The PDF builds these types using a computer network of data centres: San Francisco, Los Angeles, Denver, Chicago, Detroit, New York, Washington.
Undirected graphs
| Type | Definition | Network example |
|---|---|---|
| Simple graph | Each edge connects two different vertices, and no two edges connect the same pair. No multiple edges, no loops | One link between each pair of connected data centres (Figure 3). Each edge can be named by its unordered pair |
| Multigraph | Multiple edges allowed, no loops 06:09 | Several links between the same data centres, e.g. two between Los Angeles and Denver (Figure 4) |
| Pseudograph | Multiple edges and loops allowed 00:01 | A link from a data centre to itself, a diagnostic feedback loop (Figure 5). Not every vertex needs a loop |
Directed graphs (digraphs)
Some links work in one direction only (single duplex lines), e.g. heavy traffic one way. So we use directed edges (arcs), drawn as arrows 01:42.
A directed graph (digraph) G = (V, E) has a non-empty vertex set V and a set E of directed edges. Each directed edge is associated with an ordered pair (u, v): it starts at u and ends at v.
- {u, v} (undirected): you can travel u → v or v → u.
- (u, v) (directed): you must start at u and end at v. San Francisco → Denver does not allow Denver → San Francisco.
| Type | Definition |
|---|---|
| Simple directed graph | Directed, no loops, no multiple directed edges. At most one edge per ordered pair, so (u, v) names the edge |
| Directed multigraph | Directed, multiple directed edges (and loops) allowed. Formally G = (V, E, f), where f maps each edge to an ordered pair (Figure 7: e₁ v₁→v₂, e₂ v₂→v₃, e₄ v₁→v₃) |
| Mixed graph | Has both directed and undirected edges, e.g. a network with two-way and one-way links |
Table 1 — graph terminology (learn this)
| Type | Edges | Multiple edges? | Loops? |
|---|---|---|---|
| Simple graph | Undirected | No | No |
| Multigraph | Undirected | Yes | No |
| Pseudograph | Undirected | Yes | Yes |
| Simple directed graph | Directed | No | No |
| Directed multigraph | Directed | Yes | Yes |
| Mixed graph | Directed and undirected | Yes | Yes |
Ask three questions, in order:
- Arrows? None means undirected; all means directed; some means mixed.
- Multiple edges between the same pair?
- Loops?
Then read the type off Table 1.
5Graph models
When building a model, answer the three key questions: directed or undirected? multiple edges? loops?
| Model | Vertex | Edge | Type |
|---|---|---|---|
| Acquaintanceship graph (social network) | A person | Undirected: the two people know each other | Simple graph: no multiple edges, usually no loops (loops only if you model "self-knowledge"). A worldwide one would have about 7 billion vertices and over a trillion edges 01:03 |
| Influence graph (social network) | A person | Directed a → b: a influences b | Simple directed graph (no loops or multiple edges). E.g. Deborah influences Brian, Fred and Linda, but no one influences her; Yvonne and Brian influence each other 03:16 |
| Web graph (information network) | A web page | Directed a → b if page a links to b | Directed. More than 3 billion vertices and 20 billion edges, changing constantly 04:39 |
| Citation graph (information network) | A paper or patent | Directed: a cites b | Directed, no loops or multiple edges |
| Roadmap graph | An intersection | A road: undirected = two-way, directed = one-way, multiple = several roads, loop = loop road | Two-way only, no loops or duplicates: simple. One-way only: simple directed. Both: mixed |
| Airline routes | An airport | A directed edge for each flight | Directed multigraph 06:40 |
| Round-robin tournament | A team | (a, b) if team a beats b | Simple directed graph (each pair plays once). In Figure 10, Team 1 is undefeated and Team 3 is winless 07:38 |
| Single-elimination tournament (extra) | A game | Directed from a game to the next game | Directed (tree-like) |
Cities: Boston, Newark, Miami, Detroit, Washington.
- (a) One edge between cities that have any flight between them → simple graph.
- (b) One edge for each flight → multigraph (several flights between the same cities).
- (c) The same as (b) plus a loop for a sightseeing trip that takes off and lands in Miami → pseudograph.
Expect:
- "Define a graph"
- "Explain the Königsberg problem"
- Classifying given drawings (directed? multiple? loops?) and the terminology table
- "What kind of graph models X?" (highway systems, airline routes, parties, influence on a board, round-robin results)
- Drawing acquaintanceship and influence graphs from a description
6Quick revision sheet
| Concept | Remember it as |
|---|---|
| Graph | G = (V, E); V non-empty; edges have 1 or 2 endpoints |
| Königsberg | 4 landmasses, 7 bridges; Euler: impossible (odd degrees) |
| Finite / infinite | Finite V and E / infinite V or E |
| Simple | Undirected, no multi-edges, no loops |
| Multigraph | + multiple edges (multiplicity m) |
| Pseudograph | + loops |
| Digraph | Ordered pairs (u, v): start u, end v |
| Simple directed | Directed, no multi-edges, no loops |
| Directed multigraph | Directed + multi-edges (+ loops) |
| Mixed | Directed and undirected |
| Models | Acquaintance (simple) · influence (directed) · web (directed) · roadmap (simple/directed/mixed) · airline (directed multigraph) · round-robin (simple directed) |
?Self-check quiz
11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.