Define an adjacency matrix .

An adjacency matrix is a square matrix with the graph's vertices as both its row and its column headings. Each entry gives the number of direct connections between that pair of vertices, and a 0 means there is no direct connection at all.

Define a distance matrix .

A distance matrix has the same square layout, but each entry is the weight of the edge joining that pair of vertices. The weight might be a cost, a distance or a time, and an empty cell means there is no connection.

True or False? The matrix of an undirected network is symmetrical about its leading diagonal.

True. The distance from A to C is the same as the distance from C to A, and that holds for every pair of vertices. A directed network is not symmetrical, which is how the two can be told apart from the matrix alone.

How does an adjacency matrix show a loop, and what value is used?

A loop appears as a non-zero entry in the leading diagonal , the line running from top left to bottom right. In an undirected matrix the value is 2 , because the loop can be travelled either way round, and in a directed matrix it is 1 .

What entries appear in the adjacency matrix of a simple graph?

The only entries are 0 and 1 . A simple graph has no loops, so every leading-diagonal entry is 0, and no multiple edges, so no entry can be greater than 1.

When drawing a network from a distance matrix, when do you draw two edges between a pair of vertices?

When the two cells for that pair hold different values, which means the network is directed . Draw one edge each way, each labelled with its own weight and direction, whereas matching cells need only a single undirected edge.

What can a distance matrix be used to work out about a network?

A distance matrix gives the weight of any walk through the network, found by adding the weights of the edges that walk uses. It is also the form several algorithms need, including Prim's algorithm and Floyd's algorithm.

Define a minimum spanning tree .

A minimum spanning tree is a spanning tree of a network whose total weight is as small as possible. It connects all the vertices, contains no cycles, and is also called a minimum connector .

What are the steps of Kruskal's algorithm?

Sort all the edges into increasing weight , then add them one at a time, always taking the lightest not yet considered. Reject any edge that would form a cycle with those already chosen, and stop once every vertex is connected.

In Kruskal's algorithm, what do you do when two edges have the same weight?

Either one of them may be used. The algorithm does not say which to prefer, so the choice is completely free at that step.

True or False? An edge rejected by Kruskal's algorithm for making a cycle may be reconsidered later.

False. Once an edge is rejected it is gone for good, because the two vertices it joins are already connected and adding further edges cannot undo that. Every edge is considered exactly once, in weight order.

Why must the edges be sorted before Kruskal's algorithm begins?

The algorithm always takes the lightest remaining edge, so it needs them already in increasing weight order to work through. Sorting is a separate job, and a bubble sort or a quick sort would be used to do it.

How do you know that Kruskal's algorithm is complete?

The algorithm stops once every vertex in the network has been connected into the tree. Any edges still left in the sorted list are simply not needed.

What are the steps of Prim's algorithm on a graph?

Start at any vertex, then repeatedly add the lightest edge joining a vertex already in the tree to one not yet in it. Stop once every vertex has been added to the tree.

Why does Prim's algorithm never need to check for cycles?

Every edge it adds joins a vertex already in the tree to one that is not , so it can never close a cycle. The tree therefore stays connected at every stage, growing outwards from the starting vertex.

Does the starting vertex affect the result of Prim's algorithm?

No. Any vertex may be chosen to start from, and the total weight of the finished tree is the same whichever is used. The order the edges are added in will differ, and the tree itself may differ where there are edges of equal weight.

True or False? Prim's algorithm and the nearest neighbour algorithm are the same method.

False. Prim's algorithm builds a minimum spanning tree , taking the lightest edge available from any vertex already in the tree. The nearest neighbour algorithm builds a tour , and may only move on from the vertex it has just reached.

How is Prim's algorithm carried out on a distance matrix?

Label the starting vertex's row 1 and delete its column , then circle the smallest value in any labelled row and add that edge to the tree. Delete the column of the circled entry and label its row with the next number, repeating until every vertex has a labelled row.

In Prim's algorithm on a matrix, what do the labelled rows and the deleted columns represent?

The labelled rows are the vertices already in the tree, numbered in the order they joined it. The deleted columns are the vertices already used up, which is what stops a vertex being added to the tree twice.

True or False? Prim's algorithm on a matrix can be set up with the columns labelled and the rows crossed out.

True. Some versions of the method label the columns and cross out the rows , which is simply the mirror image of the usual layout. The algorithm itself is unchanged, provided you stay consistent about which one marks the vertices already in the tree.

Which minimum spanning tree algorithm suits information given as a matrix?

Prim's algorithm , which can be applied to a matrix directly. Kruskal's algorithm needs the edges as a list or as a graph, so a matrix would have to be drawn out as a graph first.

True or False? Prim's and Kruskal's algorithms always produce exactly the same spanning tree.

False. They may produce different trees, particularly where a network has edges of equal weight. Both trees will be minimal, so they will always have the same total weight.

How does the tree being built differ between Kruskal's and Prim's algorithms?

Kruskal's algorithm may add edges anywhere, so its tree can be in several unconnected pieces partway through. Prim's algorithm always adds an edge onto what it already has, so its tree stays connected at every stage.

Why is Prim's algorithm sometimes considered more efficient than Kruskal's?

Prim's algorithm needs no initial sort of the edges, and it never has to check for cycles . Kruskal's algorithm requires both of those, which is extra work before and during the run.

Some edges must be included in a spanning tree. How is a minimum spanning tree then found?

Draw in the required edges first, then complete the tree using Kruskal's algorithm on what remains. Any edge that would form a cycle with what is already drawn is rejected, exactly as in the ordinary method.

A LevelFurther MathsEdexcelDecision 1FlashcardsAlgorithms on GraphsMinimum Spanning Trees

Minimum Spanning Trees (Edexcel A Level Further Maths: Decision 1): Flashcards

Exam code: 9FM0

1/26

0Still learning

Know0

FrontNetworks & Matrices
Define an adjacency matrix.

Was this flashcard helpful?

Cards in this collection (26)

Define an adjacency matrix.
An adjacency matrix is a square matrix with the graph's vertices as both its row and its column headings.
Each entry gives the number of direct connections between that pair of vertices, and a 0 means there is no direct connection at all.
Define a distance matrix.
A distance matrix has the same square layout, but each entry is the weight of the edge joining that pair of vertices.
The weight might be a cost, a distance or a time, and an empty cell means there is no connection.
True or False?
The matrix of an undirected network is symmetrical about its leading diagonal.
True.
The distance from A to C is the same as the distance from C to A, and that holds for every pair of vertices.
A directed network is not symmetrical, which is how the two can be told apart from the matrix alone.
How does an adjacency matrix show a loop, and what value is used?
A loop appears as a non-zero entry in the leading diagonal, the line running from top left to bottom right.
In an undirected matrix the value is 2, because the loop can be travelled either way round, and in a directed matrix it is 1.
What entries appear in the adjacency matrix of a simple graph?
The only entries are 0 and 1.
A simple graph has no loops, so every leading-diagonal entry is 0, and no multiple edges, so no entry can be greater than 1.
When drawing a network from a distance matrix, when do you draw two edges between a pair of vertices?
When the two cells for that pair hold different values, which means the network is directed.
Draw one edge each way, each labelled with its own weight and direction, whereas matching cells need only a single undirected edge.
What can a distance matrix be used to work out about a network?
A distance matrix gives the weight of any walk through the network, found by adding the weights of the edges that walk uses.
It is also the form several algorithms need, including Prim's algorithm and Floyd's algorithm.
Define a minimum spanning tree.
A minimum spanning tree is a spanning tree of a network whose total weight is as small as possible.
It connects all the vertices, contains no cycles, and is also called a minimum connector.
Complete the number of edges in a minimum spanning tree of a network with $n$ vertices:
$number of edges = n -______$
The completed result is:
$number of edges = n - 1$
A tree joining $n$ vertices always has exactly $n - 1$ edges, which is a useful check that the algorithm has finished.
What are the steps of Kruskal's algorithm?
Sort all the edges into increasing weight, then add them one at a time, always taking the lightest not yet considered.
Reject any edge that would form a cycle with those already chosen, and stop once every vertex is connected.
In Kruskal's algorithm, what do you do when two edges have the same weight?
Either one of them may be used.
The algorithm does not say which to prefer, so the choice is completely free at that step.
True or False?
An edge rejected by Kruskal's algorithm for making a cycle may be reconsidered later.
False.
Once an edge is rejected it is gone for good, because the two vertices it joins are already connected and adding further edges cannot undo that.
Every edge is considered exactly once, in weight order.
Why must the edges be sorted before Kruskal's algorithm begins?
The algorithm always takes the lightest remaining edge, so it needs them already in increasing weight order to work through.
Sorting is a separate job, and a bubble sort or a quick sort would be used to do it.
How do you know that Kruskal's algorithm is complete?
The algorithm stops once every vertex in the network has been connected into the tree.
Any edges still left in the sorted list are simply not needed.
What are the steps of Prim's algorithm on a graph?
Start at any vertex, then repeatedly add the lightest edge joining a vertex already in the tree to one not yet in it.
Stop once every vertex has been added to the tree.
Why does Prim's algorithm never need to check for cycles?
Every edge it adds joins a vertex already in the tree to one that is not, so it can never close a cycle.
The tree therefore stays connected at every stage, growing outwards from the starting vertex.
Does the starting vertex affect the result of Prim's algorithm?
No. Any vertex may be chosen to start from, and the total weight of the finished tree is the same whichever is used.
The order the edges are added in will differ, and the tree itself may differ where there are edges of equal weight.
True or False?
Prim's algorithm and the nearest neighbour algorithm are the same method.
False.
Prim's algorithm builds a minimum spanning tree, taking the lightest edge available from any vertex already in the tree.
The nearest neighbour algorithm builds a tour, and may only move on from the vertex it has just reached.
How is Prim's algorithm carried out on a distance matrix?
Label the starting vertex's row 1 and delete its column, then circle the smallest value in any labelled row and add that edge to the tree.
Delete the column of the circled entry and label its row with the next number, repeating until every vertex has a labelled row.
In Prim's algorithm on a matrix, what do the labelled rows and the deleted columns represent?
The labelled rows are the vertices already in the tree, numbered in the order they joined it.
The deleted columns are the vertices already used up, which is what stops a vertex being added to the tree twice.
True or False?
Prim's algorithm on a matrix can be set up with the columns labelled and the rows crossed out.
True.
Some versions of the method label the columns and cross out the rows, which is simply the mirror image of the usual layout.
The algorithm itself is unchanged, provided you stay consistent about which one marks the vertices already in the tree.
Which minimum spanning tree algorithm suits information given as a matrix?
Prim's algorithm, which can be applied to a matrix directly.
Kruskal's algorithm needs the edges as a list or as a graph, so a matrix would have to be drawn out as a graph first.
True or False?
Prim's and Kruskal's algorithms always produce exactly the same spanning tree.
False.
They may produce different trees, particularly where a network has edges of equal weight.
Both trees will be minimal, so they will always have the same total weight.
How does the tree being built differ between Kruskal's and Prim's algorithms?
Kruskal's algorithm may add edges anywhere, so its tree can be in several unconnected pieces partway through.
Prim's algorithm always adds an edge onto what it already has, so its tree stays connected at every stage.
Why is Prim's algorithm sometimes considered more efficient than Kruskal's?
Prim's algorithm needs no initial sort of the edges, and it never has to check for cycles.
Kruskal's algorithm requires both of those, which is extra work before and during the run.
Some edges must be included in a spanning tree. How is a minimum spanning tree then found?
Draw in the required edges first, then complete the tree using Kruskal's algorithm on what remains.
Any edge that would form a cycle with what is already drawn is rejected, exactly as in the ordinary method.

Sign up to unlock flashcards

By signing up you agree to our Terms and Privacy Policy

Previous:GraphsNext:Shortest Path Algorithms