Topics
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
A graph is a type of diagram made up of vertices which are connected by edges.
An edge can connect any vertex to any vertex, including the same vertex. A self edge is an edge that connects a vertex to itself.
The graph to the right has vertices A,B,C and D, and edges between
A and A
A and B
A and C
B and C
B and D
C and D
Graphs are a powerful representation for understanding the connections or relationships between things.
When two vertices have an edge between them, we say that they are adjacent.
In the graph to the right, the vertices adjacent to D are C and B.
The vertices adjacent to C are all the other vertices: A,B and D.
The vertices adjacent to A are B,C and also A itself because it has a self edge (this sort of depends on convention, so the IB won't ask you this).
If two edges "connect" via a vertex, we say they are adjacent.
In the graph to the right, the edge AB is adjacent to the edges
DB (they share vertex B)
both edges CB (they share vertex B)
AC (they share vertex A)
AA (they share vertex A)
The degree of a vertex is the total number of edges that connect to that vertex. To determine the degree of a vertex, count rhe
In the graph to the right, the vertex C has the incident edges:
CD
AC
CB twice
So the degree of C is 4.
Repeat edges are important, as when they exist the degree of a vertex is not the number of vertices it is connected to.
Self edges are tricky: In the graph above there is an edge between A, so that edge "connects" to A twice. It therefore counts 2 towards the degree of A, which is therefore 4 once we consider AC and AB.
A graph is said to be connected if it is possible to get from any vertex to any other vertex by walking along the edges.
Connected
Not connected
A graph where every vertex is connected by at least one edge to every other vertex is said to be complete.
Complete
Not complete - no edge BE
Weighted graph is one where each edge has a number which we call a weight. In applied settings, these represent important properties of the connection or relation between vertices.
The first graph below shows a weighted graph of bus connections between cities, where weighted graphs represent the driving distance, in kilometers, between the two cities.
The second graph shows a plumbing network between different junctions, with directed edges representing how water can move. Here the edge weights represent the volume of water that can move through the various pipes per second.
A directed graph is a special case where the edges have direction. These directions are represented by arrows on the graph.
For a directed graph, we can count the in-degree and out-degree. Both are similar to degree, but we only count edges pointing in for in-degree, and edges pointing out for out-degree.
On the graph to the right, the vertex C has
The edges D→C, A→C and B→C pointing in, so its in-degree is 3.
The edge C→B pointing out, so its out-degree is 1.
The vertex A has
the edge A→A pointing in, so an in-degree of 1.
the edges A→A,A→C and A→B pointing out, so an out-degree of 3.
Notice that self-edges count towards both the out-degree and in-degree, since they leave and enter the same vertex.
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from C to A.
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from D to A.
A simple graph is one where there are no
directed edges
self edges
repeated edges
Simple graph
Not simple graphs
An adjacency matrix is a matrix or table that shows the possible movements between vertices on a graph.
Each row is a starting vertex, and each column an ending vertex. The nth row and jth column contains
0 if there is no edge from vertex n to vertex j
1 for each edge from n to j.
Note that the rows and columns are usually ordered alphabetically.
The following table shows a few examples of what each cell represents.
An adjacency matrix for an undirected graph is necessarily symmetric long its main diagonal, since every edge is two-way.
In this case, a self edge counts double because it contributes 1 towards both the start and finish.
We can read the degree of a vertex from an adjacency matrix by adding up the values in the relevant row / column.
Undirected graph
An undirected graph is symmetric, so we can look add up a row or column to find the degree.
In the above adjacency matrix, vertex A has degree 1+2+0=3.
Directed graph
Vertices on directed graphs have an in-degree and out-degree.
Since the rows show the source vertex, adding up a row gives the out-degree of a vertex. Adding up a column gives the in-degree of a vertex.
In the above adjacency matrix, vertex A has out-degree 1+0+0=1, and in-degree 1+1+1=3.
A walk is a sequence of valid moves on a graph, going from vertex to vertex along edges that allow movement in that direction.
The walk ACDC is shown on an undirected graph above.
The walk ABBA on a directed graph. Notice how the dashed edges are numbered to indicate the order they are in the walk.
A trail is a special type of walk where no edges are repeated.
There is no restriction on whether vertices can be repeated.
The walk above is a trail because no edge is walked more than once.
The walk above is not a trail because AE is walked twice.
A path is an even more special type of walk where no edges or vertices are repeated.
The walk above is a path.
The walk above is not a path, since A is visited twice.
A circuit is a special type of walk that starts and ends at the same vertex and does not reuse any edges.
Not "closed" so not a circuit.
Valid circuit.
Valid circuit.
Repeats DB so not a circuit.
A cycle is a special case of a circuit where no vertex, except the last one, is repeated.
Every cycle is a circuit, but not every circuit is a cycle.
Valid cycle.
Vertex A repeated in the middle so not a cycle, though it is a circuit.
By raising the adjacency matrix to the power of k, we can find the number of possible walks with length k between any two vertices.
The graph on the left has the adjacency matrix
Let's consider the walks of length 5:
To count the number of length 5 walks that start at A and end at A, we look at the row for A (first row) and the column for D, where we see a 5.
The process is the same for an undirected graph, except that the adjacency matrix will be symmetric.
Taking an existing graph and erasing one or more vertex or edge produces a smaller graph called a subgraph.
Original Graph
Subgraph examples
A tree is a graph that is
connected
simple
has no cycles
A tree with n vertices always has exactly n−1 edges.
To see why this is true imagine starting with no edges (everything is disconnected), and adding edges 1 at a time.
The first edge we add connects 2 vertices, so our tree has 2 vertices and 1 edge
Then, we add an edge connecting one of these two vertices to one we have not connected to yet. This adds 1 new vertex to the tree, so now we have 3 vertices and 2 edges.
We keep going until we stop, and we have n vertices and n−1 edges.
We cannot have any more edges, because now that every vertex is connected, adding another edge would form a loop somewhere!
A minimum spanning tree is a tree with the smallest possible weight that connects every vertex in a graph. It is often given the abbreviation "MST".
Basically, the smallest sum of edges that keep everything connected. The total weight of the minimum spanning tree is then just the sum of the weights of the edges in the tree.
Below you can see a graph and its minimum spanning tree.
The total weight of the minimum spanning tree is 3+3+2+4+5=17.
Note that MSTs are not unique - some graphs have multiple MSTs with the same weight. For example, another MST for the graph above is:
Kruskal's Algorithm is a procedure for finding minimum spanning trees on a graph.
The algorithm works by selecting edges one at a time, starting with the smallest weight edge and working our way up. Any edge that would form a cycle (a loop of vertices) with the edges we've already selected gets skipped. We stop when every vertex is connected.
The following animation shows the process for one particular graph.
Note that there will often be ties for edge weights. This is the reason why minimum spanning trees are not unique, even though they all have the same total weight.. In IB questions, any valid MST will be accepted.
Prim's Algorithm is an algorithm for finding minimum spanning trees.
It works very similar to Kruskal's Algorithm, adding edges one at a time in order of smallest to largest weights, without forming cycles. The differences are that with Prim's algorithm:
We can start at any vertex, often specified in the question
we can only add edges that connect to the tree we've made so far.
Below is a side by side comparison of each step.
Prim's
Kruskal's
The difference is that at every step, all the vertices in Prim's algorithm are connected, while in Kruskal's they can be temporarily disconnected. They both produce trees of the same weight, and often will produce an identical tree.
Prim's algorithm is ideal for finding the minimum spanning tree when we have the adjacency table of a graph, instead of the graph itself.
Consider this example:
Let's start at B.
The 1st vertex we chose was B, so we put a 1 above that column.
For us this is the 9 in row E. If there was a tie, we would just pick randomly.
We just selected row E, so we delete that row, and add a 2 in the column above it.
Now we have columns B and E, so we look for the smallest number in those columns. That number is 8, which connects to A. So now we delete row A, number column A with a 3, and continue.
The next smallest number in a valid column is the 2 in row D. So we delete that row, and number that column with a 4.
Now we have columns A, B, D and E. The smallest remaining edge weight in any of those rows is the 13 in row C. So we circle it, cross out that row, and add a 5 above the column for C.
Now that all the rows are crossed out, we read the tree by looking at the cells we have circled:
BE with weight 9
AE with weight 8
AC with weight 13
AD with weight 2
Track your progress across all skills in your objective. Mark your confidence level and identify areas to focus on.
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
Track your progress:
Don't know
Working on it
Confident
📖 = included in formula booklet • 🚫 = not in formula booklet
A graph is a type of diagram made up of vertices which are connected by edges.
An edge can connect any vertex to any vertex, including the same vertex. A self edge is an edge that connects a vertex to itself.
The graph to the right has vertices A,B,C and D, and edges between
A and A
A and B
A and C
B and C
B and D
C and D
Graphs are a powerful representation for understanding the connections or relationships between things.
When two vertices have an edge between them, we say that they are adjacent.
In the graph to the right, the vertices adjacent to D are C and B.
The vertices adjacent to C are all the other vertices: A,B and D.
The vertices adjacent to A are B,C and also A itself because it has a self edge (this sort of depends on convention, so the IB won't ask you this).
If two edges "connect" via a vertex, we say they are adjacent.
In the graph to the right, the edge AB is adjacent to the edges
DB (they share vertex B)
both edges CB (they share vertex B)
AC (they share vertex A)
AA (they share vertex A)
The degree of a vertex is the total number of edges that connect to that vertex. To determine the degree of a vertex, count rhe
In the graph to the right, the vertex C has the incident edges:
CD
AC
CB twice
So the degree of C is 4.
Repeat edges are important, as when they exist the degree of a vertex is not the number of vertices it is connected to.
Self edges are tricky: In the graph above there is an edge between A, so that edge "connects" to A twice. It therefore counts 2 towards the degree of A, which is therefore 4 once we consider AC and AB.
A graph is said to be connected if it is possible to get from any vertex to any other vertex by walking along the edges.
Connected
Not connected
A graph where every vertex is connected by at least one edge to every other vertex is said to be complete.
Complete
Not complete - no edge BE
Weighted graph is one where each edge has a number which we call a weight. In applied settings, these represent important properties of the connection or relation between vertices.
The first graph below shows a weighted graph of bus connections between cities, where weighted graphs represent the driving distance, in kilometers, between the two cities.
The second graph shows a plumbing network between different junctions, with directed edges representing how water can move. Here the edge weights represent the volume of water that can move through the various pipes per second.
A directed graph is a special case where the edges have direction. These directions are represented by arrows on the graph.
For a directed graph, we can count the in-degree and out-degree. Both are similar to degree, but we only count edges pointing in for in-degree, and edges pointing out for out-degree.
On the graph to the right, the vertex C has
The edges D→C, A→C and B→C pointing in, so its in-degree is 3.
The edge C→B pointing out, so its out-degree is 1.
The vertex A has
the edge A→A pointing in, so an in-degree of 1.
the edges A→A,A→C and A→B pointing out, so an out-degree of 3.
Notice that self-edges count towards both the out-degree and in-degree, since they leave and enter the same vertex.
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from C to A.
A directed graph is strongly connected if you can get from any vertex to any other vertex by following the directed edges of the graph.
Strongly connected
Not strongly connected - no way from D to A.
A simple graph is one where there are no
directed edges
self edges
repeated edges
Simple graph
Not simple graphs
An adjacency matrix is a matrix or table that shows the possible movements between vertices on a graph.
Each row is a starting vertex, and each column an ending vertex. The nth row and jth column contains
0 if there is no edge from vertex n to vertex j
1 for each edge from n to j.
Note that the rows and columns are usually ordered alphabetically.
The following table shows a few examples of what each cell represents.
An adjacency matrix for an undirected graph is necessarily symmetric long its main diagonal, since every edge is two-way.
In this case, a self edge counts double because it contributes 1 towards both the start and finish.
We can read the degree of a vertex from an adjacency matrix by adding up the values in the relevant row / column.
Undirected graph
An undirected graph is symmetric, so we can look add up a row or column to find the degree.
In the above adjacency matrix, vertex A has degree 1+2+0=3.
Directed graph
Vertices on directed graphs have an in-degree and out-degree.
Since the rows show the source vertex, adding up a row gives the out-degree of a vertex. Adding up a column gives the in-degree of a vertex.
In the above adjacency matrix, vertex A has out-degree 1+0+0=1, and in-degree 1+1+1=3.
A walk is a sequence of valid moves on a graph, going from vertex to vertex along edges that allow movement in that direction.
The walk ACDC is shown on an undirected graph above.
The walk ABBA on a directed graph. Notice how the dashed edges are numbered to indicate the order they are in the walk.
A trail is a special type of walk where no edges are repeated.
There is no restriction on whether vertices can be repeated.
The walk above is a trail because no edge is walked more than once.
The walk above is not a trail because AE is walked twice.
A path is an even more special type of walk where no edges or vertices are repeated.
The walk above is a path.
The walk above is not a path, since A is visited twice.
A circuit is a special type of walk that starts and ends at the same vertex and does not reuse any edges.
Not "closed" so not a circuit.
Valid circuit.
Valid circuit.
Repeats DB so not a circuit.
A cycle is a special case of a circuit where no vertex, except the last one, is repeated.
Every cycle is a circuit, but not every circuit is a cycle.
Valid cycle.
Vertex A repeated in the middle so not a cycle, though it is a circuit.
By raising the adjacency matrix to the power of k, we can find the number of possible walks with length k between any two vertices.
The graph on the left has the adjacency matrix
Let's consider the walks of length 5:
To count the number of length 5 walks that start at A and end at A, we look at the row for A (first row) and the column for D, where we see a 5.
The process is the same for an undirected graph, except that the adjacency matrix will be symmetric.
Taking an existing graph and erasing one or more vertex or edge produces a smaller graph called a subgraph.
Original Graph
Subgraph examples
A tree is a graph that is
connected
simple
has no cycles
A tree with n vertices always has exactly n−1 edges.
To see why this is true imagine starting with no edges (everything is disconnected), and adding edges 1 at a time.
The first edge we add connects 2 vertices, so our tree has 2 vertices and 1 edge
Then, we add an edge connecting one of these two vertices to one we have not connected to yet. This adds 1 new vertex to the tree, so now we have 3 vertices and 2 edges.
We keep going until we stop, and we have n vertices and n−1 edges.
We cannot have any more edges, because now that every vertex is connected, adding another edge would form a loop somewhere!
A minimum spanning tree is a tree with the smallest possible weight that connects every vertex in a graph. It is often given the abbreviation "MST".
Basically, the smallest sum of edges that keep everything connected. The total weight of the minimum spanning tree is then just the sum of the weights of the edges in the tree.
Below you can see a graph and its minimum spanning tree.
The total weight of the minimum spanning tree is 3+3+2+4+5=17.
Note that MSTs are not unique - some graphs have multiple MSTs with the same weight. For example, another MST for the graph above is:
Kruskal's Algorithm is a procedure for finding minimum spanning trees on a graph.
The algorithm works by selecting edges one at a time, starting with the smallest weight edge and working our way up. Any edge that would form a cycle (a loop of vertices) with the edges we've already selected gets skipped. We stop when every vertex is connected.
The following animation shows the process for one particular graph.
Note that there will often be ties for edge weights. This is the reason why minimum spanning trees are not unique, even though they all have the same total weight.. In IB questions, any valid MST will be accepted.
Prim's Algorithm is an algorithm for finding minimum spanning trees.
It works very similar to Kruskal's Algorithm, adding edges one at a time in order of smallest to largest weights, without forming cycles. The differences are that with Prim's algorithm:
We can start at any vertex, often specified in the question
we can only add edges that connect to the tree we've made so far.
Below is a side by side comparison of each step.
Prim's
Kruskal's
The difference is that at every step, all the vertices in Prim's algorithm are connected, while in Kruskal's they can be temporarily disconnected. They both produce trees of the same weight, and often will produce an identical tree.
Prim's algorithm is ideal for finding the minimum spanning tree when we have the adjacency table of a graph, instead of the graph itself.
Consider this example:
Let's start at B.
The 1st vertex we chose was B, so we put a 1 above that column.
For us this is the 9 in row E. If there was a tie, we would just pick randomly.
We just selected row E, so we delete that row, and add a 2 in the column above it.
Now we have columns B and E, so we look for the smallest number in those columns. That number is 8, which connects to A. So now we delete row A, number column A with a 3, and continue.
The next smallest number in a valid column is the 2 in row D. So we delete that row, and number that column with a 4.
Now we have columns A, B, D and E. The smallest remaining edge weight in any of those rows is the 13 in row C. So we circle it, cross out that row, and add a 5 above the column for C.
Now that all the rows are crossed out, we read the tree by looking at the cells we have circled:
BE with weight 9
AE with weight 8
AC with weight 13
AD with weight 2