Decision maths definitions

Question 1

algorithm

Answer 1

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

Question 2

bubble sort

Answer 2

compares adjacent items in a list

Question 3

first fit algorithm

Answer 3

Considers items in the order that they were given

Question 4

first fit decreasing algorithm

Answer 4

Considers items in descending order

Question 5

full bin packing algorithm

Answer 5

Uses inspection to select items that will combine to form bins

Question 6

graph

Answer 6

Consists of vertices/nodes which are connected by edges/arcs

Question 7

weighted graph/network

Answer 7

A graph which has numbers associated with each edge/arc

Question 8

degree (of a vertex)

Answer 8

The number of edges incident to a vertex/node

Question 9

vertices/nodes

Answer 9

points on a graph

Question 10

edges/arcs

Answer 10

lines on a graph

Question 11

walk

Answer 11

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

Question 12

path

Answer 12

A walk in which no vertex is visited more than once

Question 13

trail

Answer 13

A walk in which no edge is visited more than once

Question 14

cycle

Answer 14

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

Question 15

Hamiltonian cycle

Answer 15

A cycle which includes every vertex

Question 16

loop

Answer 16

An edge that starts and finishes at the same vertex

Question 17

simple graph

Answer 17

A graph in which there are no loops and not more than one edge connecting any pair of vertices

Question 18

directed edges

Answer 18

Edges of a graph that have a direction associated with them

Question 19

Directed Graph (digraph)

Answer 19

a graph with directed edges

Question 20

Euler’s handshaking lemma

Answer 20

In any undirected graph, the sun of the degrees of the vertices is equal to 2x the number of edges. Only when the number of odd vertices is even.

Question 21

tree

Answer 21

A connected graph with no cycles

Question 22

spanning tree

Answer 22

A subgraph of a graph which includes all the vertices of the original graph and is also a tree.

Question 23

complete graph

Answer 23

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

Question 24

isomorphic graphs

Answer 24

Graphs that show the same information but may be drawn differently

Question 25

adjacency matrix

Answer 25

Each entry describes the number of arcs joining the corresponding vertices.

Question 26

distance matrix

Answer 26

Each entry represent the weight of each arc, not the number of arcs

Question 27

planar graph

Answer 27

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

Question 28

planarity algorithm

Answer 28

An algorithm that can be applied to any graph containing a Hamiltonian cycle. It provides a method of redrawing the graph in such a way that it becomes clear whether or not it is planar

Question 29

Eulerian graph/network

Answer 29

A graph/network that contains a trail that includes every edge and starts and finishes at the same vertex. Any connected graph whose vertices are all even is Eulerian

Question 30

semi-Eulerian graph/network

Answer 30

A graph/network which contains a trail that includes every edge but starts and finishes at different vertices. Any connected graph with exactly two odd vertices is semi-Eulerian

Question 31

feasible region

Answer 31

The region of a graph that satisfies all the constraints of a linear programming problem

Question 32

maximum point

Answer 32

The last point covered by an objective line as it leaves the feasible region

Question 33

minimum point

Answer 33

The first point covered by an objective line as it enters the feasible region

Question 34

precedence/dependance table

Answer 34

A table which shows which activities must be completed before others are started

Question 35

dummy activity

Answer 35

An activity which has no time or cost. Its sole purpose is to show the dependencies between activities

Question 36

early event time

Answer 36

The earliest time of arrival at the event allowing for the completion of all preceding activities

Question 37

late event time

Answer 37

The latest time that the event can be left without extending the time needed for the project.

Question 38

source node

Answer 38

the first node

Question 39

sink node

Answer 39

the final node

Question 40

forward pass/scan

Answer 40

When the early events are calculated staring from zero at the source node and working towards the sink node

Question 41

backward pass/scan

Answer 41

The late event times are calculated starting from the sink node and working backwards towards the source node

Question 42

critical activity

Answer 42

An activity where any increase in its duration results in a corresponding increase in the duration of the whole project

Question 43

critical path

Answer 43

A path from the source node to the sink node which entirely follows critical activities. It is the longest path contained in the network.

Question 44

total float equation

Answer 44

Total float = latest finish time - duration - earliest start time

Question 45

gantt chart

Answer 45

A chart which provides a graphical way to represent the range of possible start and finish times for all activities on a single diagram

Question 46

resource levelling

Answer 46

The process of adjusting the start and finish times of the activities in order to take into account constraints on resources