A Level Further Maths Decision Definitions

Question 1

An algorithm

Answer 1

a finite sequence of step by step instructions carried out to solve a problem

Question 2

Bubble Sort: Pros (2)

Answer 2

• simple to implement
• efficient way to check if list is already in order

Question 3

Bubble Sort: Cons (1)

Answer 3

• extremely inefficient to write

Question 4

Bin Packing: First Fit: Pros (1)

Answer 4

• quick to do

Question 5

Bin Packing: First Fit: Cons (1)

Answer 5

• not likely to lead to a good solution

Question 6

Bin Packing: First Fit Decreasing: Pros (2)

Answer 6

• usually get a fairly good solution
• easy to do

Question 7

Bin Packing: First Fit Decreasing: Cons (1)

Answer 7

• might not get an optimal solution

Question 8

Bin Packing: Full Bin Packing: Pros (1)

Answer 8

• usually get a fairly good solution

Question 9

Bin Packing: Full Bin Packing: Cons (1)

Answer 9

• difficult to do

Question 10

A Minimum Spanning Tree

Answer 10

A spanning tree such that the total length of its arcs is as small as possible

Question 11

Floyd’s Algorithm is used to

Answer 11

Find the shortest path between every pair of vertices in a network

Question 12

Graph

Answer 12

Loads of lines that are put on each other :P

Question 13

A Subgraph

Answer 13

Part of the original graph

Question 14

The number of edges incident to a vertex

Answer 14

Degree/Valency/Order

Question 15

A Walk

Answer 15

A route through a graph along edges from one vertex to the next

Question 16

A Path

Answer 16

A walk in which no vertex is visited more than once

Question 17

A Trail

Answer 17

A walk in which no edge is visited more than once

Question 18

A Cycle

Answer 18

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once

Question 19

A Hamiltonian Cycle

Answer 19

A cycle that includes every vertex

Question 20

A Simple Graph

Answer 20

• A graph in which there are no loops
• and there is a most one edge connecting any pair of vertices

Question 21

Euler’s Handshaking Lemma

Answer 21

• in any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges
• therefore the number of odd vertices must be even

Question 22

A Tree

Answer 22

A connected graph with no cycles

Question 23

A Spanning Tree

Answer 23

A graph is a subgraph including all vertices and is a tree

Question 24

A Complete Graph

Answer 24

A graph in which every vertex is directly connected by a single edge to each of the other vertices

Question 25

Isomorphic Graphs

Answer 25

Graphs which show the same information but are drawn differently

Question 26

A Planar Graph

Answer 26

A graph that can be drawn in a plane such that no two edges meet except at a vertex

Question 27

Eulerian Graph

Answer 27

Any connected graph whose vertices are all even

Question 28

Semi-Eulerian

Answer 28

Any connected graph with exactly 2 odd vertices

Question 29

A Tour

Answer 29

A walk which visits every vertex, returning to its starting vertex

Question 30

The Travelling Salesman Problem involves

Answer 30

finding a tour of minimum total weight

Question 31

The Classical Travelling Salesman Problem

Answer 31

Each vertex is visited exactly once before returning to the start

Question 32

The Practical Travelling Salesman Probblem

Answer 32

Each vertex visited at least once before returning to the start

Question 33

The Feasible Region

Answer 33

A region of the graph that satisfies all the constraints

Question 34

M is an

Answer 34

Arbitrarily large number