Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

A Level Further Maths Decision > Chapter 3 Algorithms on Graphs > Flashcards

Chapter 3 Algorithms on Graphs Flashcards

1
Q

What is a MST?

A

Minimum spanning tree

A MST is a spanning tree such that the total lengths of all its arcs is as small as possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 4 algorithms you need to know?

A

Kruskal’s
Prim’s
Dijkstra’s
Floyd’s

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a tree?

A

A tree is a connected graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is a spanning tree?

A

A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a MST sometimes called?

A

A minimum connector

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

State Kruskal’s algorithm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What can Kruskal’s algorithm be used for?

A

Finding the MST

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is counter intuitive when using Kruskal’s algorithm?

A

It may grow as 2 unconnected graphs but it will always finish as 1 connected spanning tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What can Prim’s algorithm be used for?

A

Finding the MST

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

State Prim’s algorithm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the main difference between Kruskal’s algorithm and Prim’s algorithm?

A

The difference between Prim’s and Kruskal’s algorithm is that Prim’s algorithm considers vertices whereas Krukal’s algorithm considers edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What 2 versions of Prim’s algorithm do you need to know?

A

A normal graph version and a distance matrix version

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

State the distance matrix form of Prim’s algorithm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When using the distance matrix form Prim’s algorithm what workings out do you need to show?

A

The final annotated table
Plus
A list of arcs in the correct order

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a practical application of Dijkstra’s algorithm?

A

Finding the cheapest or fastest way to transport goods

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What can Dijkstra’s algorithm be used to find?
(In terms of graph theory)

A

Dijkstra’s algorithm can be used to find the shortest path through S and T through a network

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

How do you pronounce Dijkstra?

A

Dike-Stra

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

State Dijkstra’s algorithm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the required workings out when using Dijkstra’s algorithm?

A

you only need 1 completed diagram with the answer stated at the end

The order of the working list needs to be correct

20
Q

What are working labels often called?

A

Temporary labels

21
Q

What are final labels often called?

A

Permeant labels

22
Q

What is the correct notation to use when using Dijkstra’s algorithm?

A
23
Q

What is the correct notation to use when using Dijkstra’s algorithm?

A
24
Q

What is the correct notation to use when using Dijkstra’s algorithm?

A
25
Q

What is the 1st key observation about Dijkstra’s algorithm?

A

You can use Dijkstra’s algorithm to work out the shortest route between the start vertex and any other vertex with a final label

26
Q

What is 1 major implication of the 1st observation about Dijkstra’s algorithm?

A

If you have a completed diagram Dijkstra’s algorithm can work out the shortest route between the start variable and any other

27
Q

What is 1 generalisation you can apply to Dijkstra’s algorithm?

What is this the equivalent of in the real world?

A

It can be used with directed graphs (just don’t go the wrong way down an arrow)

1 way roads

28
Q

What can Floyd’s algorithm be used to do?

A

Find the shortest path between any 2 vertices in a network

29
Q

State Floyd’s algorithm?

A
30
Q

Once you have a completed route table how do you find the shortest route?

A

To find the quickest route between C and D you need to: look at row C and column D the letter that is in that stop is the vertex that you need to go to get from C to D. But you then need to check the quickest route from that new vertex (B) to D by doing the same process of looking at row C and column B and so on until that value is D
(You need to write the numbers from the right to the left.

31
Q

Once you have a completed distance table how do you find the weight of the shortest route?

A

The corresponding entry in the final distance table will tell you the distance between the 2 routes

32
Q

What is a distance table?

A

It is essentially a distance table but with infinity signs where there would normally be dashes (except down the leading diagonal

33
Q

What will the initial route table look like?

A
34
Q

How can highlighting be done in exams?

A

Circling the row and column that needs to be highlighted

35
Q
A
36
Q

What is step 1 of Floyd’s algorithm?

A

1) Complete an initial distance table for the network
If there is no direct route from one vertex to another use a infinity sign

37
Q

What is step 2 of Floyd’s algorithm?

A

2) Complete an initial route table by making every element in the 1st column the same
as the label at the top of the column and then doing the same thing for each
subsequent column

38
Q

What is step 3 of Floyd’s algorithm?

A

3) In the first iteration, copy the first row and first column values of the distance table
into a new table as well as all the dashes – highlight these columns and rows

39
Q

What is step 4 of Floyd’s algorithm?

A
40
Q

What is step 5 of Floyd’s algorithm?

A

5) For the second iteration copy the second row and column from the last iteration into a new distance table whilst highlighting these values

41
Q

What is step 6 of Floyd’s algorithm?

A

6) Repeat step 4 with the new unshaded positions but this time any change will result in a detour through B so you should write B in the new route table when necessary

42
Q

What is step 7 of Floyd’s algorithm?

A

7) If there are n vertices then the algorithm will require n iterations

43
Q

What is step 1 of Dijkstra’s algorithm?

A
44
Q

What is step 2 of Dijkstra’s algorithm?

A
45
Q

What is step 3 of Dijkstra’s algorithm?

A
46
Q

What is step 5 of Dijkstra’s algorithm?

A

A Level Further Maths Decision (9 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions